-avl_node_t *avl_unlink(avl_tree_t *tree, void *data)
-{
- avl_node_t *node;
-
- node = avl_search_node(tree, data);
-
- 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);
+
+ node->next = node->prev = node->parent = node->left = node->right = NULL;