- if(node)
- avl_unlink_node(tree, node);
-
- return node;
-}
-
-void avl_unlink_node(avl_tree_t *tree, avl_node_t *node)
-{
- avl_node_t *parent;
- avl_node_t **superparent;
- avl_node_t *subst, *left, *right;
- avl_node_t *balnode;
-
- if (node->prev)
- node->prev->next = node->next;
- else
- tree->head = node->next;
- if (node->next)
- node->next->prev = node->prev;
- else
- tree->tail = node->prev;
-
- parent = node->parent;
-
- superparent = parent ? node == parent->left ? &parent->left : &parent->right : &tree->root;
-
- left = node->left;
- right = node->right;
- if (!left)
- {
- *superparent = right;
- if (right)
- right->parent = parent;
- balnode = parent;
- } else if (!right)
- {
- *superparent = left;
- left->parent = parent;
- balnode = parent;
- } else
- {
- subst = node->prev;
- if (subst == left)
- {
- balnode = subst;
- } else
- {
- balnode = subst->parent;
- balnode->right = subst->left;
- if (balnode->right)
- balnode->right->parent = balnode;
- subst->left = left;
- left->parent = subst;
- }
- subst->right = right;
- subst->parent = parent;
- right->parent = subst;
- *superparent = subst;
- }
-
- avl_rebalance(tree, balnode);