Deleting from a binary search tree

Taking a key out of a search tree must leave every smaller key on the left. Watch what happens when the root goes.

⋯62void bst_remove(struct tnode **link, int key)63{64    while (*link != NULL && (*link)->key != key) {65        if (key < (*link)->key)66            link = &(*link)->left;67        else68            link = &(*link)->right;69    }70    struct tnode *t = *link;71    if (t == NULL)72        return;73    if (t->left == NULL) {74        *link = t->right;75        free(t);76    } else if (t->right == NULL) {77        *link = t->left;78        free(t);79    } else {80        struct tnode **s = &t->right;81        while ((*s)->left != NULL)82            s = &(*s)->left;83        struct tnode *succ = *s;84        t->key = succ->key;85        *s = succ->right;86        free(succ);87    }88}⋯96    bst_remove(&root, KEY);97    inorder(root);

Find the link, then re-aim it

A search tree keeps one promise at every node: smaller keys in the left subtree, larger in the right. Removing a key must keep it. In memory, a node is in the tree because one pointer points to it, the root pointer or its parent’s left or right. So removing comes down to one question: which pointer should change, and what should it point to now?

Press the leaves first: 20, 40, 65 or 80. The search walks down to the node, the pointer that led there becomes NULL, and the node is freed. Nothing else moves; the readout says one link re-aimed.

Now press 60. It has one child, 65. The pointer that led to 60 (70’s left) is aimed at 65 instead, and 60 is freed. 65 moves up into 60’s place, and the order still holds: everything under 60 was already between 50 and 70, as 60 was.

Now 50, the root, which the clip plays. Its two children can’t both hang from one pointer. The trick is to leave the node where it is and change its key: copy in the successor, the smallest key larger than 50, which is 60. Then remove the old 60 node instead, and that node is easy to remove, because it has no left child. Only one key moves, and one link is re-aimed: 70’s left, from the old 60 to 65.

The code and its cost

The program

The full program, bst-remove.c, starts with the two #include lines, struct tnode, new_node and bst_insert copied from bst.c (Binary search trees), and inorder and free_tree from traversals.c (Tree traversals). Its main inserts the eight keys 50 30 70 20 40 60 80 65, removes KEY, prints the tree in order and frees it. The new function is this:

void bst_remove(struct tnode **link, int key)
{
    while (*link != NULL && (*link)->key != key) {
        if (key < (*link)->key)
            link = &(*link)->left;
        else
            link = &(*link)->right;
    }
    struct tnode *t = *link;
    if (t == NULL)
        return;
    if (t->left == NULL) {
        *link = t->right;
        free(t);
    } else if (t->right == NULL) {
        *link = t->left;
        free(t);
    } else {
        struct tnode **s = &t->right;
        while ((*s)->left != NULL)
            s = &(*s)->left;
        struct tnode *succ = *s;
        t->key = succ->key;
        *s = succ->right;
        free(succ);
    }
}

A pointer to the link

link is not a pointer to a node. It holds the address of a pointer: first main’s root, then a node’s left or right field. This is the idea of Removing from a linked list: walk with a pointer to the link, so that when the node is found, *link = … changes exactly the pointer that leads to it. The root needs no special case. If the root itself is removed and has one child, *link is main’s root, and the child becomes the new root.

The call passes &root for that reason: bst_remove may need to change main’s root, so it is given the address of it.

The three cases

t is the node found. If it has no left child, *link = t->right covers two cases at once: a leaf (t->right is NULL, so the link becomes NULL) and a node whose one child is on the right. If it has a left child but no right, the link takes the left child. Either way the child keeps its whole subtree, and every key in that subtree was already on the correct side of every node above.

The successor

With two children, bst_remove finds the successor: one step right, then left until there is no left child. The right subtree holds every key larger than t’s, and its leftmost node holds the smallest of them. s makes the walk as link did, as a pointer to a link, so that afterwards *s is the pointer that leads to the successor.

The successor can’t have a left child. A left child would be smaller than the successor and still in t’s right subtree, so it would be the successor instead. With at most one child, on the right, the successor is removed by the one-child rule: *s = succ->right.

Why the successor? The node’s new key must be larger than everything left of it and smaller than everything right of it. The successor is: it is the smallest key on the right. The predecessor, the largest key on the left (one step left, then right to the end), works the same way. Any other key would break the order somewhere.

What it costs

The walk to the node and the walk on to its successor go down one path from the root, so a removal visits at most h + 1 nodes, where h is the tree’s height (counted in edges), and does a fixed amount of work at each. Like a search, a removal costs the height: about log₂ n steps in a bushy tree, up to n in a chain. Removing 50 here visits 50, 70 and 60; the tree’s height is 3.

Running it yourself

KEY is a macro, 50 unless the build says otherwise, so one file removes any key:

gcc -std=c11 -Wall -Wextra -pedantic bst-remove.c -o bst-remove
./bst-remove
gcc -std=c11 -Wall -Wextra -pedantic -DKEY=30 bst-remove.c -o bst-remove
./bst-remove

The first prints 20 30 40 60 65 70 80, the second 20 40 50 60 65 70 80. Whatever key is removed, the line is the other seven keys in order, which is the quickest check that the tree is still a search tree.

Worked example

Start from the eight-key tree and remove 50, then 20, then 30.

Each inorder list is the one before it minus the key. The preorder shows the shape: the root is 60 from the first removal on, and after the third, 60 has 40 on its left and 70 (with 65 and 80) on its right.

Two checks. What is the successor of 30 in the eight-key tree? (40: one step right, to 40, which has no left child.) Why can’t the successor have a left child? (A left child would be smaller and still in the right subtree, so it would be the successor.)

Where it’s used

Ordered maps. Every ordered map or set built on a search tree supports removal, and starts with exactly this: find the link, then one of the three cases.

Balanced trees. AVL trees and red–black trees begin their deletions the same way, then repair the balance on the way back up.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, pointers 8, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.