-/* Remove an element a from the AVL tree t
- * returns -1 if the depth of the tree has shrunk
- * Warning: if the element is not present in the tree,
- * returns 0 as if it had been removed succesfully.
- */
-int _avl_remove(avl_tree* t, avl* a) {
- int b;
- if (t->root == a)
- return _avl_removeroot(t);
- b = t->compar(t->root, a);
- if (b >= 0) {
- /* remove from the left subtree */
- int ch;
- avl_tree left_subtree;
- if ((left_subtree.root = t->root->left)) {
- left_subtree.compar = t->compar;
- ch = _avl_remove(&left_subtree, a);
- t->root->left = left_subtree.root;
- if (ch) {
- switch (t->root->balance++) {
- case -1:
- return -1;
- case 0:
- return 0;
- }
- switch (t->root->right->balance) {
- case 0:
- avl_swl(&(t->root));
- t->root->balance = -1;
- t->root->left->balance = 1;
- return 0;
- case 1:
- avl_swl(&(t->root));
- t->root->balance = 0;
- t->root->left->balance = 0;
- return -1;
- }
- avl_swr(&(t->root->right));
- avl_swl(&(t->root));
- avl_nasty(t->root);
- return -1;
- }
- }
- }
- if (b <= 0) {
- /* remove from the right subtree */
- int ch;
- avl_tree right_subtree;
- if ((right_subtree.root = t->root->right)) {
- right_subtree.compar = t->compar;
- ch = _avl_remove(&right_subtree, a);
- t->root->right = right_subtree.root;
- if (ch) {
- switch (t->root->balance--) {
- case 1:
- return -1;
- case 0:
- return 0;
- }
- switch (t->root->left->balance) {
- case 0:
- avl_swr(&(t->root));
- t->root->balance = 1;
- t->root->right->balance = -1;
- return 0;
- case -1:
- avl_swr(&(t->root));
- t->root->balance = 0;
- t->root->right->balance = 0;
- return -1;
- }
- avl_swl(&(t->root->left));
- avl_swr(&(t->root));
- avl_nasty(t->root);
- return -1;
- }
- }
- }
- return 0;
+/* Deletes from |tree| and returns an item matching |item|.
+ Returns a null pointer if no matching item found. */
+avl *avl_remove(avl_tree *tree, avl *item) {
+ /* Stack of nodes. */
+ avl *pa[AVL_MAX_HEIGHT]; /* Nodes. */
+ unsigned char da[AVL_MAX_HEIGHT]; /* |avl_link[]| indexes. */
+ int k; /* Stack pointer. */
+
+ avl *p; /* Traverses tree to find node to delete. */
+ int cmp; /* Result of comparison between |item| and |p|. */
+
+ // assert (tree != NULL && item != NULL);
+
+ k = 0;
+ p = (avl *) &tree->root;
+ for(cmp = -1; cmp != 0; cmp = tree->compar(item, p)) {
+ int dir = (cmp > 0);
+
+ pa[k] = p;
+ da[k++] = dir;
+
+ p = p->avl_link[dir];
+ if(p == NULL) return NULL;
+ }
+
+ item = p;
+
+ if (p->avl_link[1] == NULL)
+ pa[k - 1]->avl_link[da[k - 1]] = p->avl_link[0];
+ else {
+ avl *r = p->avl_link[1];
+ if (r->avl_link[0] == NULL) {
+ r->avl_link[0] = p->avl_link[0];
+ r->avl_balance = p->avl_balance;
+ pa[k - 1]->avl_link[da[k - 1]] = r;
+ da[k] = 1;
+ pa[k++] = r;
+ }
+ else {
+ avl *s;
+ int j = k++;
+
+ for (;;) {
+ da[k] = 0;
+ pa[k++] = r;
+ s = r->avl_link[0];
+ if (s->avl_link[0] == NULL) break;
+
+ r = s;
+ }
+
+ s->avl_link[0] = p->avl_link[0];
+ r->avl_link[0] = s->avl_link[1];
+ s->avl_link[1] = p->avl_link[1];
+ s->avl_balance = p->avl_balance;
+
+ pa[j - 1]->avl_link[da[j - 1]] = s;
+ da[j] = 1;
+ pa[j] = s;
+ }
+ }
+
+ // assert (k > 0);
+ while (--k > 0) {
+ avl *y = pa[k];
+
+ if (da[k] == 0) {
+ y->avl_balance++;
+ if (y->avl_balance == +1) break;
+ else if (y->avl_balance == +2) {
+ avl *x = y->avl_link[1];
+ if (x->avl_balance == -1) {
+ avl *w;
+ // assert (x->avl_balance == -1);
+ w = x->avl_link[0];
+ x->avl_link[0] = w->avl_link[1];
+ w->avl_link[1] = x;
+ y->avl_link[1] = w->avl_link[0];
+ w->avl_link[0] = y;
+ if (w->avl_balance == +1)
+ x->avl_balance = 0, y->avl_balance = -1;
+ else if (w->avl_balance == 0)
+ x->avl_balance = y->avl_balance = 0;
+ else /* |w->avl_balance == -1| */
+ x->avl_balance = +1, y->avl_balance = 0;
+ w->avl_balance = 0;
+ pa[k - 1]->avl_link[da[k - 1]] = w;
+ }
+ else {
+ y->avl_link[1] = x->avl_link[0];
+ x->avl_link[0] = y;
+ pa[k - 1]->avl_link[da[k - 1]] = x;
+ if (x->avl_balance == 0) {
+ x->avl_balance = -1;
+ y->avl_balance = +1;
+ break;
+ }
+ else x->avl_balance = y->avl_balance = 0;
+ }
+ }
+ }
+ else
+ {
+ y->avl_balance--;
+ if (y->avl_balance == -1) break;
+ else if (y->avl_balance == -2) {
+ avl *x = y->avl_link[0];
+ if (x->avl_balance == +1) {
+ avl *w;
+ // assert (x->avl_balance == +1);
+ w = x->avl_link[1];
+ x->avl_link[1] = w->avl_link[0];
+ w->avl_link[0] = x;
+ y->avl_link[0] = w->avl_link[1];
+ w->avl_link[1] = y;
+ if (w->avl_balance == -1)
+ x->avl_balance = 0, y->avl_balance = +1;
+ else if (w->avl_balance == 0)
+ x->avl_balance = y->avl_balance = 0;
+ else /* |w->avl_balance == +1| */
+ x->avl_balance = -1, y->avl_balance = 0;
+ w->avl_balance = 0;
+ pa[k - 1]->avl_link[da[k - 1]] = w;
+ }
+ else {
+ y->avl_link[0] = x->avl_link[1];
+ x->avl_link[1] = y;
+ pa[k - 1]->avl_link[da[k - 1]] = x;
+ if (x->avl_balance == 0) {
+ x->avl_balance = +1;
+ y->avl_balance = -1;
+ break;
+ }
+ else x->avl_balance = y->avl_balance = 0;
+ }
+ }
+ }
+ }
+
+ // tree->avl_count--;
+ // tree->avl_generation++;
+ return item;