5 /* See Knuth Volume 3, 6.2.3 */
8 avlcreate(int (*cmp)(Avl*, Avl*))
12 t = malloc(sizeof(*t));
15 return avlinit(t, cmp);
19 avlinit(Avltree *t, int (*cmp)(Avl*, Avl*))
27 avllookup(Avltree *t, Avl *k, int d)
53 static int insert(int (*)(Avl*, Avl*), Avl*, Avl**, Avl*, Avl**);
56 avlinsert(Avltree *t, Avl *k)
61 insert(t->cmp, nil, &t->root, k, &old);
65 static int insertfix(int, Avl**);
68 insert(int (*cmp)(Avl*, Avl*), Avl *p, Avl **qp, Avl *k, Avl **oldp)
95 fix = insert(cmp, q, q->c + (c+1)/2, k, oldp);
97 return insertfix(c, qp);
101 static Avl *singlerot(int, Avl*);
102 static Avl *doublerot(int, Avl*);
105 insertfix(int c, Avl **t)
110 if(s->balance == 0) {
114 if(s->balance == -c) {
118 if(s->c[(c+1)/2]->balance == c)
126 static int delete(int (*cmp)(Avl*, Avl*), Avl**, Avl*, Avl**);
127 static int deletemin(Avl**, Avl**);
128 static int deletefix(int, Avl**);
131 avldelete(Avltree *t, Avl *k)
138 delete(t->cmp, &t->root, k, &old);
143 delete(int (*cmp)(Avl*, Avl*), Avl **qp, Avl *k, Avl **oldp)
153 c = c > 0 ? 1 : c < 0 ? -1: 0;
162 fix = deletemin(q->c+1, &e);
170 return deletefix(-1, qp);
173 fix = delete(cmp, q->c + (c+1)/2, k, oldp);
175 return deletefix(-c, qp);
180 deletemin(Avl **qp, Avl **oldp)
193 fix = deletemin(q->c, oldp);
195 return deletefix(1, qp);
199 static Avl *rotate(int, Avl*);
202 deletefix(int c, Avl **t)
208 if(s->balance == 0) {
212 if(s->balance == -c) {
217 if(s->c[a]->balance == 0) {
223 if(s->c[a]->balance == c)
232 singlerot(int c, Avl *s)
241 doublerot(int c, Avl *s)
248 s->c[a] = rotate(-c, s->c[a]);
253 if(p->balance == c) {
256 } else if(p->balance == -c) {
260 s->balance = r->balance = 0;
266 rotate(int c, Avl *s)
273 s->c[a] = n = r->c[a^1];
282 static Avl *walk1(int, Avl*);
305 for(q = q->c[a]; q->c[a^1] != nil; q = q->c[a^1])
309 for(p = q->p; p != nil && p->c[a] == q; p = p->p)
314 static Avl *bottom(Avltree*,int);
329 bottom(Avltree *t, int d)
338 for(n = t->root; n->c[d] != nil; n = n->c[d])