Trees and Ordered Search

Find fast and insert fast

A library's returns desk files books by call number, about a million of them. All day, two things happen at once: returned books are filed, and readers ask for the first call number at or after one they have in mind, because that is where their shelf begins.

Module 11 showed why order matters: in sorted data, one comparison can discard half of what is left. This module builds the structure that keeps data sorted while it changes, shows that its cost is decided by one number, its height, and opens up std::set and std::map, which are this structure kept in balance. In C++ it is also an ownership structure: every node owns its children, and destroying the root frees everything.

Two containers that each do half the job

A sorted std::vector answers "first at or after X" with a halving search: about ${\log }_{2}n$ comparisons, 20 for a million call numbers. Filing is the problem: every number after the new one moves one slot right, half a million on average.

A linked list, or an unsorted vector with new numbers appended, files a return in one step. Now lookup is the problem: without order, finding "first at or after X" means looking at every number.

Both waste work in the same place: they treat the collection as one long line, where keeping order means shifting. We want a shape where an insertion touches only a few elements and a comparison still discards a large part of what is left.

A tree that keeps keys in order

A binary search tree stores each key in a node. A node has up to two children, a left one and a right one, and each child is the root of a smaller tree, its subtree. The node at the top is the root; a node with no children is a leaf. The number of nodes on the longest path from the root down to a leaf is the tree's number of levels, which we will also call its height.

In C++ the shape is also an ownership structure, and module 8 gave us the words for it. Each node owns its two children through std::unique_ptr. The tree owns its root. Code that only looks at the tree borrows a node with a plain const Node*, which owns nothing and frees nothing.

#include <memory>

struct Node {
    int key;
    std::unique_ptr<Node> left;   // owns every key smaller than `key` in this subtree
    std::unique_ptr<Node> right;  // owns every key larger than `key` in this subtree
    explicit Node(int k) : key(k) {}
};

int main() {
    std::unique_ptr<Node> root = std::make_unique<Node>(41);
    root->left = std::make_unique<Node>(20);
    root->right = std::make_unique<Node>(65);
    // Leaving main destroys root, which destroys its two children first: no delete anywhere.
}

When root is destroyed, its Node's members are destroyed in reverse order of declaration: first right, then left. Each unique_ptr destroys the node it owns, which destroys its own children the same way. One destruction frees the whole tree, every child before its parent, with no cleanup code: module 7's RAII, applied to a shape.

What makes it a search tree is one rule about where keys may sit.

The rule is about whole subtrees, not just the two children. A tree whose root is 41 with a left child 20, where 20 has a right child 50, satisfies "each child is on the correct side of its parent" and still breaks the invariant: 50 sits in 41's left subtree.

Searching follows one path

Here is the lesson's tree. Ten call numbers were filed in the order 41, 65, 20, 29, 91, 11, 50, 32, 99, 72. The figure shows the search for 32.

A search compares the key it wants with the node it is at. Equal means found. Smaller means the key, if present, is in the left subtree, so the search moves left; larger means it moves right. When the search needs to move to a child that does not exist, the key is not in the tree. Searching for 70 visits 41, 65, 91 and 72, then wants 72's left child, which is empty, and stops.

Why is it safe to stop? Suppose the search is at a node and the key it wants is smaller. By the invariant, every key in the node's right subtree is larger than the node's key, so larger than the wanted key too. The right subtree cannot contain it, and neither can the node. Everything that could still hold the key is in the left subtree. Applying that at every step, the search never leaves the only subtree that could hold its key, and an empty child means that subtree is empty.

The search needs no ownership, so it borrows. It walks with a const Node* that starts at the root and follows left or right; get() lends the raw pointer a unique_ptr holds without giving up ownership.

#include <memory>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int k) : key(k) {}
};

bool contains(const Node* node, int key) {
    while (node != nullptr) {
        if (key == node->key) return true;
        node = key < node->key ? node->left.get() : node->right.get();
    }
    return false;
}

int main() {
    auto root = std::make_unique<Node>(41);
    root->left = std::make_unique<Node>(20);
    root->left->right = std::make_unique<Node>(29);
    root->left->right->right = std::make_unique<Node>(32);
    return contains(root.get(), 32) && !contains(root.get(), 70) ? 0 : 1;
}

The cost of a search is the number of nodes on its path: at most the number of levels. Here that is 4, against 10 for a scan.

Inserting is a search that ends at an empty place

Filing a new call number starts exactly like a search for it. If the number is already there, there is nothing to file. Otherwise the search ends by wanting a child that does not exist, and that empty place is the only position where the new key keeps the invariant: it is larger than every node where the search went right, and smaller than every node where it went left. A new node goes there, as a leaf. Nothing else moves.

That is the whole difference from the sorted vector. Inserting 32 visited four nodes and created one; nothing was shifted or copied. In C++, "the empty place" is a std::unique_ptr<Node> that holds nullptr, and filling it is one assignment of a freshly made node. Which unique_ptr to fill, and how to reach it so that the assignment changes the tree and not a copy, is the first thing the lab asks you to write.

Order of arrival decides the shape. The lesson tree has 4 levels and took 19 comparisons to build; the same keys in sorted order give 10 levels and 45 comparisons. We will come back to this, because it is the central fact about search trees.

Four ways to walk a tree

Many questions need every node, not one path. A walk that visits every node once is a traversal, and a binary tree has four standard ones. The first three are recursive: visit the root and walk the two subtrees, in some order. They differ only in when the root is visited.

• In-order: left subtree, then the node, then the right subtree. On the lesson tree: 11, 20, 29, 32, 41, 50, 65, 72, 91, 99.
• Pre-order: the node first, then left, then right: 41, 20, 11, 29, 32, 65, 50, 91, 72, 99.
• Post-order: left, right, then the node: 11, 32, 29, 20, 50, 72, 99, 91, 65, 41.
• Level order: by distance from the root, left to right within a level: 41, 20, 65, 11, 29, 50, 91, 32, 72, 99.

The in-order walk prints the keys sorted, and that is no accident. Here is the argument, by induction on the size of the tree. An empty tree prints nothing, which is sorted. For a larger tree, the in-order walk prints the left subtree's keys (sorted, by induction, since that subtree is smaller), then the root, then the right subtree's keys (sorted, by induction). By the invariant every key in the first part is smaller than the root and every key in the last part is larger, so the whole output is sorted. That is why iterating over a std::set from begin() to end() gives its elements in order: an iterator's ++ moves to the next node of an in-order walk.

Pre-order lists a parent before its children, so filing keys in pre-order rebuilds the same shape. Post-order finishes both children before their parent: the order to free a tree in, and the order the destructors above run in. Level order is module 11's breadth-first search, with a std::queue of nodes waiting to be visited.

# The lesson's own numbers, checked without any tree code. Two facts about
# binary search trees stand in for insertion and traversal:
# 1. A new key's parent is whichever of its two sorted-order neighbours (among the
#    keys already filed) was filed later.
# 2. Every walk is a sort of the nodes by their path from the root.
import bisect

def paths(order):
    """Root path of each key, as a tuple of 'L'/'R' steps."""
    filed, when, path = [], {}, {}
    for t, key in enumerate(order):
        i = bisect.bisect_left(filed, key)
        neighbours = filed[max(0, i - 1):i + 1]
        if neighbours:
            parent = max(neighbours, key=lambda k: when[k])
            path[key] = path[parent] + ('L' if key < parent else 'R',)
        else:
            path[key] = ()
        filed.insert(i, key)
        when[key] = t
    return path

lesson = [41, 65, 20, 29, 91, 11, 50, 32, 99, 72]
p = paths(lesson)
levels = 1 + max(len(v) for v in p.values())
comparisons = sum(len(v) for v in p.values())   # one comparison per ancestor
assert (levels, comparisons) == (4, 19)

chain = paths(sorted(lesson))
assert 1 + max(len(v) for v in chain.values()) == 10
assert sum(len(v) for v in chain.values()) == 45

# Searching for 32 visits its ancestors, root first, then 32 itself.
ancestors = [k for k in p if p[k] == p[32][:len(p[k])]]
assert sorted(ancestors, key=lambda k: len(p[k])) == [41, 20, 29, 32]

L, R = 'L', 'R'
in_order = sorted(p, key=lambda k: tuple(0 if s == L else 2 for s in p[k]) + (1,))
pre_order = sorted(p, key=lambda k: tuple(0 if s == L else 1 for s in p[k]))
post_order = sorted(p, key=lambda k: tuple(0 if s == L else 1 for s in p[k]) + (2,))
level_order = sorted(p, key=lambda k: (len(p[k]), tuple(0 if s == L else 1 for s in p[k])))
assert in_order == sorted(lesson)
assert pre_order == [41, 20, 11, 29, 32, 65, 50, 91, 72, 99]
assert post_order == [11, 32, 29, 20, 50, 72, 99, 91, 65, 41]
assert level_order == [41, 20, 65, 11, 29, 50, 91, 32, 72, 99]

Recursion on a tree

A tree is either empty or a root with two smaller trees, and that shape suggests the shape of the code: a function of a tree handles the empty case, then combines its answers for the two subtrees. Counting nodes is the smallest example.

#include <memory>

struct Node {
    int key;
    std::unique_ptr<Node> left, right;
    explicit Node(int k) : key(k) {}
};

int size(const Node* node) {
    if (node == nullptr) return 0;                 // an empty tree has no nodes
    return 1 + size(node->left.get()) + size(node->right.get());
}

int main() {
    auto root = std::make_unique<Node>(41);
    root->left = std::make_unique<Node>(20);
    root->right = std::make_unique<Node>(65);
    root->right->right = std::make_unique<Node>(91);
    return size(root.get()) == 4 ? 0 : 1;
}

Each call is answered from two smaller ones, so the recursion ends, and induction on size proves it right. Levels, the largest key, and whether the invariant holds are written the same way; the invariant check also passes down the range of keys a subtree may hold, since "each child is on the correct side of its parent" is not enough.

There is a hidden cost. Every recursive call keeps a frame on the call stack until it returns, and the lab's runtime gives a program 1 MiB of stack. A million keys filed in sorted order form a chain a million levels deep. Walking it recursively, or simply destroying it (each unique_ptr's destructor calls the next one's), nests a million calls and crashes the program, though nothing is wrong with the logic. Shape is not only a matter of speed.

Removing a key

Removing a key has to leave a tree that still satisfies the invariant, and there are three cases, by how many children the node has.

1. No children. The node is a leaf. The unique_ptr that owns it is reset, and the node is freed.
2. One child. The node's only subtree takes its place: the unique_ptr that owned the node takes ownership of that subtree instead, and the node is freed. The subtree's keys were already on the correct side of everything above, so the invariant holds.
3. Two children. Neither subtree can simply move up, since there is only one place for two subtrees. Instead the node keeps its place and takes a new key: the in-order successor, the smallest key in its right subtree. That key is larger than everything on the left and smaller than everything else on the right, so it can sit at the node without breaking the invariant. The successor's own node is then removed from the right subtree, and it is always case 1 or 2: the smallest key of a subtree has no left child, or something smaller would sit there.

Cost is height

Search, insert and remove all follow one path from the root, so each costs at most one comparison per level. Everything about a search tree's speed is therefore about its height, and height depends only on the order in which keys arrived.

The best case is a tree whose levels are all full except perhaps the last. Level $d$ (counting the root as level 1) holds at most $2^{d-1}$ nodes, so $L$ levels hold at most $2^L-1$ keys, and $n$ keys need at least $L=\lceil {\log }_2(n+1)\rceil$ levels. For a million keys that is 20. The worst case is the chain, $n$ levels, produced by sorted or reverse-sorted arrival. That is not a contrived input: call numbers often arrive in order.

Between the two is the average. If every one of the $n!$ arrival orders of $n$ distinct keys is equally likely, the average number of comparisons to file all of them is

$$2(n+1)H_n-4n,H_n=1+\frac{1}{2}+\cdots +\frac{1}{n},$$

which grows like $2n\ln n\approx 1.39n{\log }_{2}n$. A typical order is close to the best case, but this average is over arrival orders; it says nothing about the order your data actually arrives in, and nothing in a plain tree prevents the worst one.

Measure the claim

The tables count the comparisons needed to file the keys $0,1,\dots ,n-1$ into an empty tree. The first compares the worst arrival order, sorted, with the best possible: a tree with every level full but the last. That column comes from a formula rather than a construction: in such a tree, the $i$-th key in level order sits at depth $\lfloor {\log }_{2}i\rfloor$, counting the root as depth 0, and costs that many comparisons.

The second compares one random shuffle with the average over all arrival orders.

import random
from fractions import Fraction

def build_cost(order):
    return sum(len(v) for v in paths(order).values())

def average_cost(n):
    harmonic = sum(Fraction(1, i) for i in range(1, n + 1))
    return round(2 * (n + 1) * harmonic - 4 * n)

table = {}
for n in (100, 1000, 10000):
    keys = list(range(n))
    shuffled = keys[:]
    random.Random(13).shuffle(shuffled)
    sorted_cost = n * (n - 1) // 2          # key i is compared with all i keys before it
    best = sum(i.bit_length() - 1 for i in range(1, n + 1))
    table[n] = (sorted_cost, build_cost(shuffled), best, average_cost(n))
assert table[100] == (4950, 650, 480, 648)
assert table[1000] == (499500, 10966, 7987, 10986)
assert table[10000] == (49995000, 158017, 113631, 155772)
assert build_cost(list(range(1000))) == 499500   # the stand-in agrees with the formula

Sorted arrival grows 100-fold when n grows 10-fold: quadratic. Every other column grows a little more than 10-fold, the $n\log n$ shape. One shuffle lands within about 1.5% of the average here, but a single sample is not a guarantee. Only the best-possible column can be relied on, and reaching it requires controlling the shape.

Keeping the height down: what std::set and std::map are

A balanced search tree restructures itself so that its height stays $O(\log n)$ for every arrival order. The step is a rotation: a parent and child swap vertical positions while the in-order sequence, and so the invariant, is unchanged. A red-black tree colours nodes red or black and rotates whenever one path could become more than twice as long as another, which caps its height at $2{\log }_2(n+1)$. An AVL tree keeps every node's two subtrees within one level of each other. Either way, every operation is logarithmic in the worst case.

The C++ standard does not say how std::set and std::map are built, only what they cost: find, insert, erase and the member lower_bound are logarithmic in the size. libc++ (this course's library) meets that with a red-black tree in its __tree, and libstdc++ (GCC's) in its _Rb_tree. Three consequences follow:

• Iteration is the in-order walk, so a set always iterates sorted, and ++ on an iterator usually takes a few steps, occasionally up to the height.
• Nodes do not move. Inserting into a set never invalidates iterators, pointers or references to its other elements; removing an element invalidates only those to that element. Module 9's vector could promise neither.
• Searching is a member's job. s.lower_bound(x) follows one path from the root. The free std::lower_bound(s.begin(), s.end(), x) from module 10 makes a logarithmic number of comparisons but can only move an iterator one step at a time, so it walks a linear number of nodes. With a tree inside, always ask the container.

A problem that looks different

A file system is a tree of folders. Each folder holds some files and some subfolders, and its size is the total of its files plus the sizes of all its subfolders. A disk-usage tool must report every folder's size, reading each folder's listing only once. It is not a search tree and has no order invariant, but one of this lesson's four walks is exactly the order in which those sizes can be computed. Which one, and why does any other order force the tool to read some listing twice?

Practise

The lab has you build this structure yourself, on its own keys. You will write insertion into a tree of unique_ptr nodes and watch your tree grow one frame per key, then write the four walks and check your predictions against them. You will remove keys in all three cases while a counter confirms that exactly one node is freed each time. Then you will measure, at sizes the checks choose, how arrival order changes what filing costs, and construct an arrival order with the best possible shape. The final challenge tells a story and does not say which technique it needs.

Recap

You can now: build a binary search tree from unique_ptr nodes, search it by borrowing, walk it in four orders, remove keys in all three cases, and say what its shape costs.

Invariant: for every node, every key in its left subtree is smaller and every key in its right subtree is larger; the in-order walk is therefore sorted.

Complexity achieved: search, insert and remove make at most one comparison per level, so $O(h)$ for height $h$. Height is between $\lceil {\log }_2(n+1)\rceil$ and $n$ levels. Sorted arrival costs $n(n-1)/2$ comparisons to build; the average over all arrival orders is $2(n+1)H_n-4n$; a balanced tree guarantees $O(\log n)$ per operation in the worst case.

Failure mode: trusting average-case shape for data that arrives sorted, and recursing as deep as a degenerate tree, including through a chain of destructors.

In real software: std::set and std::map are red-black trees in libc++ and libstdc++; the standard requires logarithmic member searches and keeps references to other elements valid across insertions.

Retrieval: from module 8, which owns a node here, and what does a const Node* taken with get() promise about that node's lifetime?

Check yourself

1. State the order invariant, and prove by induction that the in-order walk of any search tree is sorted.
2. A search for an absent key stops at an empty child. Why is it safe to conclude the key is nowhere else in the tree?
3. Give an arrival order of the keys 1 to 7 that builds a tree of three levels, and one that builds seven. How many comparisons does a search for 7 make in each?

Original SciMigo course material. C++ examples target C++17.