Binary search trees

How would you file numbers so that finding one is quick and adding one is cheap? Watch where each new key goes.

⋯22struct tnode *bst_insert(struct tnode *root, struct tnode *n)23{24    if (root == NULL)25        return n;26    struct tnode *parent = NULL;27    struct tnode *cur = root;28    while (cur != NULL) {29        parent = cur;30        if (n->key < cur->key)31            cur = cur->left;32        else33            cur = cur->right;34    }35    if (n->key < parent->key)36        parent->left = n;37    else38        parent->right = n;39    return root;40}⋯42int bst_search(const struct tnode *root, int key)43{44    const struct tnode *cur = root;45    while (cur != NULL && cur->key != key) {46        if (key < cur->key)47            cur = cur->left;48        else49            cur = cur->right;50    }51    return cur != NULL;52}⋯54int main(void)55{56    int keys[N] = { 50, 30, 70, 20, 40, 60, 80 };57    struct tnode *nodes[N];58    struct tnode *root = NULL;59    for (int i = 0; i < N; i++) {60        nodes[i] = new_node(keys[i]);61        root = bst_insert(root, nodes[i]);62    }63    printf("search 40: %d\n", bst_search(root, 40));64    printf("search 65: %d\n", bst_search(root, 65));

Smaller to the left, larger to the right

Each key goes into a node, a struct with the key and two pointers:

struct tnode {
    int key;
    struct tnode *left, *right;
};

From Binary trees (12.1): each node has a left and a right child, either of which may be NULL; the node at the top is the root, a node with no children is a leaf, and the height of a tree counts the edges on its longest path down from the root, so a single node has height 0. A node is 24 bytes here: key at 0, 4 bytes of padding, left at 8 and right at 16.

Now the clip. The program inserts seven keys in the order 50, 30, 70, 20, 40, 60, 80. Each new key starts at the root and is compared with every node on its way down: smaller goes left, larger or equal goes right. Where the walk reaches an empty slot, a NULL, the new node is linked in.

• 50 arrives first and becomes the root.
• 30 < 50, so it goes left; 50’s left is NULL, and 30 becomes 50’s left child.
• 70 ≥ 50 goes right and becomes 50’s right child.
• 20 goes left at 50 and left at 30. 40 goes left at 50, then right at 30, since 40 ≥ 30.
• 60 goes right at 50 and left at 70; 80 goes right at both.

Each insertion draws exactly one new arrow, from the new node’s parent. The heap strip under the tree shows the blocks in the order they were allocated, 0x1000 for 50 up to 0x10c0 for 80, and none of them moves when a later key arrives. The tree’s shape lives in the left and right pointers, not in where the blocks sit.

Seven keys passed 0 + 1 + 1 + 2 + 2 + 2 + 2 = 10 nodes on their way down, and the tree has height 2. Then the program searches twice. A search for 40 visits 50, 30 and 40 and finds it; a search for 65 visits 50, 70 and 60, and stops when 60’s right is NULL. The output is search 40: 1 and search 65: 0, where 1 means found.

Now a prediction, before you touch the control. The same seven keys arrive sorted: 20, 30, 40, 50, 60, 70, 80. What shape do you expect?

Set “Insertion order” to “sorted”. The tree clears and grows again. Every key is larger than all the keys before it, so each one goes right at every node and becomes the right child of the key before it. The tree is a chain leaning down to the right, of height 6, and the insertions pass 0 + 1 + 2 + … + 6 = 21 nodes. The search for 65 now visits six nodes, 20 up to 70, before it falls off.

The code and its cost

The rule

A binary search tree keeps one rule at every node: every key in its left subtree is smaller than its key, and every key in its right subtree is larger or equal. The rule covers whole subtrees, not just a node’s two children. In the listed tree, 40 sits in 50’s left subtree, so 40 < 50 as well as 40 ≥ 30. Equal keys go right in this program; the examples have none.

Searching

int bst_search(const struct tnode *root, int key)
{
    const struct tnode *cur = root;
    while (cur != NULL && cur->key != key) {
        if (key < cur->key)
            cur = cur->left;
        else
            cur = cur->right;
    }
    return cur != NULL;
}

cur starts at the root. At each node the rule says which side the key must be on, if it is in the tree at all, so the search goes that way and never looks at the other side. It stops at the key, and returns 1, or at NULL, and returns 0. When the tree is bushy, each step leaves behind about half of the keys still in play, as binary search on a sorted array does (Binary search, 5.4).

Inserting

struct tnode *bst_insert(struct tnode *root, struct tnode *n)
{
    if (root == NULL)
        return n;
    struct tnode *parent = NULL;
    struct tnode *cur = root;
    while (cur != NULL) {
        parent = cur;
        if (n->key < cur->key)
            cur = cur->left;
        else
            cur = cur->right;
    }
    if (n->key < parent->key)
        parent->left = n;
    else
        parent->right = n;
    return root;
}

bst_insert takes a node n that new_node has already made: a 24-byte block from malloc holding the key, with left and right both NULL. The loop is the search again, with one addition. cur walks down until it falls off, and parent stays one node behind it, on the last node passed. When cur is NULL, parent is the node whose empty slot the new key belongs in, and lines 35 to 38 compare once more to choose left or right.

That one write, parent->left = n or parent->right = n, is the only pointer the insertion changes. The new node always arrives as a leaf. No other node moves and no other arrow changes.

An empty tree is the one special case: root is NULL, there is no parent, and the new node becomes the root. That is why bst_insert returns the root and main stores it: root = bst_insert(root, nodes[i]);. When the tree is not empty, it returns the same root.

What it costs

A search or an insertion visits the nodes on one path from the root: at most height + 1 of them. So the cost is the tree’s height, and the height depends on the order the keys arrived in.

For n keys, the height is at least ⌊log₂ n⌋, when every level is as full as it can be, and at most n − 1, when the keys arrive sorted and make a chain. For the seven keys those are ⌊log₂ 7⌋ = 2 and 6, the two trees of the clip.

Running it yourself

The code pane shows bst_insert, bst_search and main as far as the searches. The full program, bst.c, is those with the struct, new_node and the loop that frees the nodes. main keeps every node’s address in an array, nodes, so that it can free them one by one; giving back a tree without such an array needs recursion, the subject of Recursion (4.1). keys and nodes are in main’s frame but stay off the picture. Build and run it with:

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

Worked example

Start from the listed tree: 50 at the root; 30 and 70 under it; 20, 40, 60 and 80 as leaves.

Insert 45. The walk compares 45 with each node it passes:

The walk falls off under 40, so 45 becomes 40’s right child. Line 38, parent->right = n;, writes 0x10e0, the new node’s address, into 40’s right field. That is the one pointer written. 45 sits three edges below the root, so the height is now 3.

Insert 65. 65 ≥ 50, so right to 70; 65 < 70, so left to 60; 65 ≥ 60, so right, and 60’s right is NULL. 65 becomes 60’s right child, at 0x1100. The height stays 3.

Read the keys across the tree from left to right and they come out in order: 20 30 40 45 50 60 65 70 80. That is no accident, and Tree traversals (12.3) shows why.

Before you play the replay: how many arrows does inserting 65 add, and which node’s pointer does it change? (One arrow, from 60’s right.) And where would 35 go? (Left at 50, right at 30, left at 40: 40’s left child.)

⋯22struct tnode *bst_insert(struct tnode *root, struct tnode *n)23{24    if (root == NULL)25        return n;26    struct tnode *parent = NULL;27    struct tnode *cur = root;28    while (cur != NULL) {29        parent = cur;30        if (n->key < cur->key)31            cur = cur->left;32        else33            cur = cur->right;34    }35    if (n->key < parent->key)36        parent->left = n;37    else38        parent->right = n;39    return root;40}⋯42int main(void)43{44    int keys[N] = { 50, 30, 70, 20, 40, 60, 80, 45, 65 };45    struct tnode *nodes[N];46    struct tnode *root = NULL;47    for (int i = 0; i < N; i++) {48        nodes[i] = new_node(keys[i]);49        root = bst_insert(root, nodes[i]);50    }51    for (int i = 0; i < N; i++)52        free(nodes[i]);53    return 0;54}

A trap. Here is a tree in which every parent and child are in the right order:

        50
       /
     30
       \
        55

30 < 50, so 30 may be 50’s left child; 55 ≥ 30, so 55 may be 30’s right child. But 55 is in 50’s left subtree, and 55 > 50. The tree breaks the rule. A search for 55 compares at 50, goes right, finds NULL and reports 0, although 55 is in the tree. The rule is about whole subtrees, which is why checking each parent against its children is not enough.

The cost. With 1,000,000 keys, a tree with every level full has height ⌊log₂ 1,000,000⌋ = 19, so its longest path has 20 nodes, and a search visits at most 20. Insert the same keys in sorted order and the tree is a chain: a search for the largest key visits all 1,000,000 nodes.

Where it’s used

Ordered maps and sets. Standard libraries store keys in order, with fast search, insertion and the next key up, in binary search trees. They use balanced forms, which reshape the tree as keys arrive so that it never becomes a chain; Balanced trees (13.3 to 13.5) builds them.

Database indexes. A database finds a row by its key through an index, a search tree with many keys in each node so that the tree stays shallow on disk; B-trees (13.6) builds one.

Finding every key in a range. The rule says where all the keys between 40 and 65 must be, so a search can skip every subtree that lies outside the range.

A tree of questions. A decision tree in machine learning is also a tree of yes-or-no questions walked from the root, but its questions split data rather than keys: Decision trees.

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.