/*% cc -Wall -c % * avl * A trivial implementation of * AVL trees in C. */ #include /* Perform error checking on allocation by defining * a new xalloc and xfree function. */ #define xalloc malloc #define xfree free struct Tree { int (*cmp)(void *, void *); struct N { void *p; signed char bal; struct N *n[2]; } *root; }; /* avlnew - Create an empty AVL tree and return it. * A comparison function must be provided, elements of the * tree will be compared with this function. */ struct Tree * avlnew(int (*cmp)(void *, void *)) { struct Tree *t=xalloc(sizeof *t); t->cmp=cmp; t->root=0; return t; } /* avlfree - Free the memory allocated by a search * tree. Works by successive rotations, as explained * in http://www.stanford.edu/~blp/avl/libavl.html. */ void avlfree(struct Tree *t) { struct N *p, *n=t->root; for (; n; n=p) { for (; (p=n->n[0]); n=p) { n->n[0]=p->n[1]; p->n[1]=n; } p=n->n[1]; xfree(n); } xfree(t); } /* avlget - Get an element from the AVL tree. */ void * avlget(void *p, struct Tree *t) { struct N *n=t->root; while (n) { int c=t->cmp(p, n->p); if (c==0) return n->p; n=n->n[c>0]; } return 0; } /* internal ins - Insert one data into the AVL tree, * keeping the tree balanced using the usual rotating * algoritm. * Returns 1 if the size of the subtree grew, * 0 otherwise. */ static int ins(void *p, struct N **pn, int (*cmp)(void *, void *)) { int c; struct N *n=*pn; if (!n) { /* We found an appropriate location * to insert the element, in this case * the subtree is no longer empty, hence * we return 1 to signal it. */ struct N *node=xalloc(sizeof *node); node->p=p; node->n[0]=node->n[1]=0; node->bal=0; *pn=node; return 1; } c=cmp(p, n->p); if (c<0) { if (!ins(p, &n->n[0], cmp)) return 0; else if (n->bal-->-1) return n->bal!=0; else { /* Here the size of the left subtree * is too big, we correct this by * performing some local rotations. */ struct N *a=n->n[0]; if (a->bal==-1) { /* In this case we simply need * a right rotation to correct * the balances. * n a * / \ / \ * a 3 -> 1 n * / \ / \ * 1 2 2 3 */ *pn=a; n->n[0]=a->n[1]; a->n[1]=n; a->bal=n->bal=0; } else { /* This case is trickier, we * need two rotations to pull * the longest branch on top. * n b * / \ / \ * a 4 a \ * / \ -> / \ n * 1 b 1 2 / \ * / \ 3 4 * 2 3 */ struct N *b=a->n[1]; *pn=b; a->n[1]=b->n[0]; n->n[0]=b->n[1]; b->n[0]=a; b->n[1]=n; if (b->bal<0) a->bal=0, n->bal=1; else if (b->bal>0) a->bal=-1, n->bal=0; else a->bal=0, n->bal=0; b->bal=0; } return 0; } } if (c>0) { if (!ins(p, &n->n[1], cmp)) return 0; else if (n->bal++<+1) return n->bal!=0; else { /* The symetric case. */ struct N *a=n->n[1]; if (a->bal==1) { *pn=a; n->n[1]=a->n[0]; a->n[0]=n; a->bal=n->bal=0; } else { struct N *b=a->n[0]; *pn=b; a->n[0]=b->n[1]; n->n[1]=b->n[0]; b->n[1]=a; b->n[0]=n; if (b->bal>0) a->bal=0, n->bal=-1; else if (b->bal<0) a->bal=1, n->bal=0; else a->bal=0, n->bal=0; b->bal=0; } return 0; } } /* If c is 0 then the tree is left * unchanged and 0 is returned. */ return 0; } /* avlins - Public interfarce for ins. */ void avlins(void *p, struct Tree *t) { ins(p, &t->root, t->cmp); }