- struct avl_tree_node *child, *parent;
- bool left_deleted;
-
- if (node->left && node->right)
- avl_tree_swap_with_successor(node);
-
- /* Unlink @node */
- child = node->left ? node->left : node->right;
- parent = avl_get_parent(node);
- if (parent) {
- if (node == parent->left) {
- parent->left = child;
- left_deleted = true;
+ struct avl_tree_node *parent;
+ bool left_deleted = false;
+
+ if (node->left && node->right) {
+ /* @node is fully internal, with two children. Swap it
+ * with its in-order successor (which must exist in the
+ * right subtree of @node and can have, at most, a right
+ * child), then unlink @node. */
+ parent = avl_tree_swap_with_successor(root_ptr, node,
+ &left_deleted);
+ /* @parent is now the parent of what was @node's in-order
+ * successor. It cannot be NULL, since @node itself was
+ * an ancestor of its in-order successor.
+ * @left_deleted has been set to %true if @node's
+ * in-order successor was the left child of @parent,
+ * otherwise %false. */
+ } else {
+ struct avl_tree_node *child;
+
+ /* @node is missing at least one child. Unlink it. Set
+ * @parent to @node's parent, and set @left_deleted to
+ * reflect which child of @parent @node was. Or, if
+ * @node was the root node, simply update the root node
+ * and return. */
+ child = node->left ? node->left : node->right;
+ parent = avl_get_parent(node);
+ if (parent) {
+ if (node == parent->left) {
+ parent->left = child;
+ left_deleted = true;
+ } else {
+ parent->right = child;
+ left_deleted = false;
+ }
+ if (child)
+ avl_set_parent(child, parent);