DATA·II Data structures Chapter 17 of 65
A garden of search trees
We plant keys and watch a search tree grow. It keeps its keys in order and answers “from here to there” questions that leave a hash table helpless. Plant the keys in order and a stick grows instead of a bush, so the gardener learns to prune with rotations. When and how to prune was worked out in 1962 by two Moscow mathematicians.
Data structures
- 13 Complexity
- 14 Arrays
- 15 Stacks, queues
- 16 Hash tables
- 17 Trees you are here
- 18 Heaps
- 19 Graphs
Builds on: 09 · A problem inside a problem 12 · The island of rabbits and foxes 13 · What a program costs
What you will take away
- plant, find and delete keys in a binary search tree, and walk it in four different orders
- why a tree degenerates into a stick, and how the rotations of an AVL tree keep its height near log n
- answer “all keys from here to there” and “the next one in order,” and recognize trees in files, HTML and JSON
The hash table from the last chapter finds a word in one step, but it has no idea which word comes after it in the alphabet, and when asked for “all words from ‘war’ to ‘warm’” it goes through the whole dictionary. A sorted list knows the order, and in it such questions are settled by binary search, the method we used in Chapter 0 to guess a number in twenty questions. The list has a different problem. A new word has to go into the middle, and to make room the whole tail has to move over, as in Chapter 14. The bisect module finds the place by binary search and inserts the word there; a stopwatch will show what the moving costs.
Twice as many numbers take four times as long: each insertion moves half the list on average, and in total that adds up to a square. A hash table would insert quickly, but it doesn’t remember any order. We want both: the keys kept in order, any of them found in a few steps, and a new one set in its place without moving anything. A structure like that is grown, like a plant, and this chapter is a garden.
The seed: a node with two branches
The linked list from Chapter 14 was a chain of nodes, each holding a value and a link to the next one. Give a node two links, a left one and a right one, and forbid the links to form loops or to converge: every node except the top one is reached by one link and no more. The result is a tree. Programmers draw their trees growing downward. The top node, the one without a parent, is the root. Nodes without children are leaves. Every node, together with everything growing beneath it, is a smaller tree in its own right, called a subtree or a branch. Defining a thing in terms of itself is the same recursion as in the folders of Chapter 9, and that is why almost everything to do with trees is done by recursion.
A tree in which every node has at most two children is called binary. To make it searchable, the keys are laid out by one rule.
A binary search tree: at every node, all keys in the left branch are smaller than its key, and all keys in the right branch are larger.
The rule covers all the keys in a branch, the nearest child and everything below it alike, and it holds at every node. This detail will come back in the tasks. In Python the node itself is a small class, as in Chapter 12.
Planting
A new key looks for its place starting from the root. Smaller than the root, it goes into the left branch; larger, into the right one, and there it is compared again. When the branch it needs isn’t there, the place has been found: this is where a new leaf will grow. Into the garden go the characters of War and Peace. Strings are compared alphabetically, as in a dictionary; we saw that in Chapter 6.
Move the slider under the picture. Pierre came first and became the root for good. Natasha comes before Pierre in the alphabet, so she went left. Andrew comes before both Pierre and Natasha: left, and left again. Sonya comes after Pierre: right. Each newcomer goes down from the root, choosing one of two branches on every level, and becomes a leaf.
The line node.left = insert(node.left, key) deserves a second glance. The function returns the root of the subtree, and we write it back into the branch. If the branch was empty, a new node appears in its place; if it wasn’t, the same node comes back and the assignment changes nothing. Forgetting node.left = is the most common mistake: the new node is created and lost at once. Plant some keys of your own in the garden.
Finding a plant
A search takes the same path as planting: compare with the node, go into one branch, repeat. It ends either at the key it wants or in an empty branch, and then the key is not in the tree. There are as many comparisons as levels passed. The number of levels on the longest path from the root to a leaf is called the height of the tree: a single node has height 1, an empty tree 0. The height is the worst case for a search.
Here the search is written as a loop rather than recursion: it goes down one branch and never comes back, so it needs no stack of unfinished business. The expression a if condition else b picks one of two values; it is a short form of if. Of the nine characters, Mary takes longest to find, six comparisons: she is on the sixth level. Napoleon, who isn’t in the tree, takes as many: the path ends under Mary. In a good tree the height grows as the logarithm of the number of keys: a perfect tree of height 20 holds $2^{20} - 1$ nodes, more than a million, and finding any of them costs at most twenty comparisons. There are bad trees too, and we’ll come to them soon.
A walk around the garden
To print or count all the nodes, you have to walk the tree. A list has a single order for that; in a tree every node has three things to attend to: itself, its left branch and its right branch. The order of those three gives different traversals. Pre-order: the node first, then the left branch, then the right. In-order: the left branch, the node, the right branch. Post-order: both branches, then the node. And a breadth-first traversal goes level by level: the root, then its children, then its grandchildren. It needs the queue from Chapter 15.
The second line of the output is why search trees exist at all. An in-order traversal produces the keys in alphabetical order: everything to the left of a node is smaller and comes out earlier, everything to the right is larger and comes out later. The order that the hash table threw away is stored here in the shape of the tree itself, and if you plant keys and then walk the tree in order, you get a sort.
The other traversals are useful in trees of every kind. They are easiest to compare on the tree hidden in every formula of the calculator from Chapter 15: an arithmetic expression. In $(2 + 3) \cdot (7 - 4)$ the last operation is the multiplication, so it sits at the root; its left branch is $2 + 3$, its right branch $7 - 4$. Trace the outline of this tree with a dot, counterclockwise, starting from the root.
Post-order on the expression gives 2 3 + 7 4 - *, the reverse Polish notation that the HP-35 calculator from Chapter 15 evaluates without parentheses. Pre-order gives * + 2 3 - 7 4, Łukasiewicz’s notation with the operator in front. And in-order gives 2 + 3 * 7 - 4, the familiar infix notation, only without the parentheses. That changes the meaning: the tree computes $5 \cdot 3 = 15$, while the string without parentheses computes $2 + 21 - 4 = 19$. The tree remembers that the addition comes first; the string has forgotten. That is why calculators, compilers and Python itself, having read a formula or a program, start by building a tree like this one out of it. We will do the same in Chapter 50.
Cutting a branch
Removing a key is harder than planting one: the hole in the middle of the tree has to be patched so that the search rule still holds. There are three cases. A leaf is cut off, and that’s the end of it. A node with one branch is replaced by that branch: the branch lies wholly on the same side of the parent as the node did, so the rule doesn’t suffer. That leaves a node with two branches. Its place must go to a key that is larger than everything in the left branch and smaller than everything in the right. There is such a key: the next one in order, the successor, which is the leftmost node of the right branch. It has no left child, or it wouldn’t be the leftmost, so cutting it out is easy: it falls under one of the first two cases.
Mary is a leaf, and she disappears without a trace. Andrew has a single branch, and Hélène moves up into his place, bringing Dolokhov with her. Natasha has two branches; her successor in alphabetical order is Nicholas, the leftmost node in her right branch. Nicholas moves into Natasha’s place, and his old node is cut away. The method was described by Thomas Hibbard in 1962, in a paper that was among the first to work out how search trees behave when the keys arrive in random order. Switch the garden above to “Cut” and try all three cases.
A stick instead of a bush
All along we have been saying “in a good tree.” What the tree grows into depends only on the order of planting. Plant keys in increasing order in the garden with the “In order” button. Each new key is larger than all the earlier ones, so it goes right, right and right again. Instead of a bush, a stick grows: a linked list laid on its side, where a search costs $n$ comparisons. And in Python it can get worse.
A hundred thousand shuffled keys give a height of about forty: more than the 17 of a perfect tree, but still a logarithm, with a multiplier in front. Nine hundred keys in order give a height of 900. And two thousand in order end in a RecursionError: the recursive planting goes two thousand levels down the stick and runs into the depth limit from Chapter 9. The trouble is that ordered data turns up all the time: order numbers grow, dates come one after another, files arrive already sorted.
You have met this ailment before. In Chapter 21, quicksort with the first element of the list as its pivot also sank thousands of levels into recursion on sorted input. The resemblance is no accident: a search tree grown from a list and that quicksort make the same comparisons. The first key becomes the root and is compared with all the others, as a pivot is. Smaller keys go left, larger ones right, and in each branch its first key becomes the pivot in turn. A counter settles it.
The numbers agree to the last digit for every $n$. So everything Chapter 21 knew about quicksort holds for the tree as well. On random order both make on average about $2 \ln n \approx 1.39 \log_2 n$ comparisons per key, ignoring the smaller terms; on sorted order, a square. Back then the sort was cured by a random pivot. A tree doesn’t get to choose the order in which its keys arrive, so it is the shape of the tree that needs treating.
Pruning: rotations
Nobody digs up a bush to make it grow straighter; a gardener prunes its branches. A search tree has an operation of that kind: the rotation. Take a node $y$ with a left child $x$. Under them hang three branches: $A$ to the left of $x$, $B$ between $x$ and $y$, $C$ to the right of $y$. A right rotation lifts $x$ into the place of $y$, and $y$ becomes the right child of $x$. Branch $B$, which lay between them, passes to $y$ and hangs on its left.
A rotation keeps the search rule: the in-order traversal before and after it gives the same string $A\ x\ B\ y\ C$. Only the shape changes, and with it the heights: if branch $A$ was a level taller than $B$ and $C$, the rotation lifts it by a level and lowers $C$, and the whole tree becomes a level shorter. In Python a rotation is three assignments.
One rotation helps when the tall branch grows “outward,” on the left of a left child. If it grows “inward,” on the right of a left child, the rotation only shifts the lopsidedness to the other side. Then it takes two rotations: first a left rotation around the child to straighten the zigzag, then a right one around the node itself. What remains is to decide when to prune. That was settled in Moscow in 1962.
Moscow, 1962. The gardeners of ITEP
The rule of Adelson-Velsky and Landis is this: at every node the heights of the left and the right branch differ by at most one. A tree in which it holds is called an AVL tree. Every node remembers the height of its branch. After planting, we go back from the new leaf to the root (recursion does that by itself, on the way back) and at every node update the height and check the rule. If the difference has reached two, we prune with one rotation or two.
A thousand keys in order, which the unpruned tree turned into a stick and the recursion into a crash, now give a height of 10. That is the best there can be: ten levels hold no more than $2^{10} - 1 = 1023$ nodes. On random keys the AVL tree is only a couple of levels taller than the ideal. Turn on the “Gardener” in the garden above and plant keys in order, and you will see the rotations: the node where the rule broke flashes, and the bush turns.
How many levels
The last column of the output is a limit on the height, and it can be proved. The Fibonacci numbers from Chapter 9 turn up in the proof, out of nowhere.
An AVL tree of $n$ nodes has height at most $\log_\varphi (n + 1) \approx 1.44 \log_2 (n+1)$, where $\varphi = \frac{1 + \sqrt5}{2} \approx 1.618$ is the golden ratio.
Ask the question the other way round: what is the smallest number of nodes $N(h)$ an AVL tree of height $h$ can have? An empty tree has $N(0) = 0$, a single node $N(1) = 1$. The skinniest tree of height $h$ has a root, one branch of height $h - 1$, and another branch as short as the rule allows, that is, of height $h - 2$, and both branches are the skinniest possible themselves. Hence $N(h) = N(h-1) + N(h-2) + 1$.
Add one to both sides: $N(h) + 1 = \big(N(h-1) + 1\big) + \big(N(h-2) + 1\big)$. This is the rule of the Fibonacci numbers, and with the starting values $N(0) + 1 = 1 = F_2$, $N(1) + 1 = 2 = F_3$ we get $N(h) + 1 = F_{h+2}$. Induction shows that $F_k \ge \varphi^{k-2}$: it holds for $F_2 = 1$ and $F_3 = 2$, and after that $F_k = F_{k-1} + F_{k-2} \ge \varphi^{k-3} + \varphi^{k-4} = \varphi^{k-4}(\varphi + 1) = \varphi^{k-2}$, because $\varphi + 1 = \varphi^2$.
So any AVL tree of height $h$ has at least $N(h)$ nodes: $n + 1 \ge N(h) + 1 = F_{h+2} \ge \varphi^h$. Taking logarithms, $h \le \log_\varphi (n+1) = \frac{\log_2 (n+1)}{\log_2 \varphi} \approx 1.44 \log_2 (n+1)$.
The skinniest AVL trees are called Fibonacci trees. For a million keys the theorem promises at most 28 levels, which means at most 28 comparisons per search, whatever the order of planting. Pruning is cheap too: a rotation changes three links, and heights need updating only on the path from the leaf to the root, $O(\log n)$ nodes. That gives us what we were after at the start of the chapter: search, insertion and deletion in $O(\log n)$ in the worst case, with the keys always in order.
An answer to the hash table
Back to the questions that defeated the hash table. We plant every word of War and Peace in an AVL tree (the tree skips repeats) and ask which words lie between “war” and “warm” and which word comes right after “napoleon” in the alphabet. The function between is an in-order traversal that stays out of branches where the keys it wants can’t be: if a node is below the lower bound, its whole left branch is smaller still, and there is no point going there.
The answers are the ones the dictionary gave at the end of the last chapter, and the work involved is incomparably smaller. Twenty thousand words grew into a tree of height 17. To find the eleven words from “war” to “warm,” the tree visited 22 nodes, while the dictionary went through all 20,478. Finding “napoleonic,” the word right after “napoleon,” took a single descent from the root. In general a query like this costs $O(\log n + k)$, where $k$ is the number of keys in the answer: the descent to the start of the range, then the steps through the answers themselves. That is how a database answers “all orders in March” or “all products under a thousand” without reading the whole table.
Trees over the fence
Search trees are one species in a large garden. Trees in general, where a node may have any number of children, meet a programmer at every turn. The most familiar of them are folders. In Chapter 9 we walked a folder made of dictionaries by recursion; the function os.walk does the same with the folders on a disk. Here it walks the folder on the course server where Python’s libraries live: the standard one and the installed packages, including the matplotlib and numpy that draw the charts in the cells.
At every step os.walk hands over three things: the path to a folder, the list of folders inside it and the list of its files; it goes down into all the inner folders by itself. The variable os.__file__ holds the path to the file of the os module, and os.path.dirname cuts the file name off a path and leaves the folder. When this chapter was written, the course server had more than six hundred folders and six thousand files here, stacked eight levels deep. The root of this tree is the library folder; its leaves are files.
The second tree is the page you are reading. The browser parses its HTML into a tree of elements: html at the root, head and body under it, under them the sections, paragraphs and code cells, and inside the paragraphs links and formulas. Every tag opened inside another one is its child. The tree of this page has more than four thousand nodes and about thirty levels, and the formulas are nested deepest of all: a fraction or a square root drawn on the page is dozens of elements one inside another. The third tree is the JSON from Chapter 8: dictionaries and lists nested in each other, with numbers and strings for leaves. You can browse all three below.
These trees have no search rule (a folder keeps its files in any order), but the traversals are the same. The size of a folder is computed in post-order: first the sizes of the folders inside, then the sum. A table of contents is printed in pre-order: first the name of a folder, then what is in it. And when a browser looks for an element on the page by a CSS selector, it walks the page’s tree.
Tasks
Five tasks, from a warm-up to two traps. In all of them a node is a Node class with the fields key, left and right, as in the chapter; the tests build the trees themselves and call your functions. Some of the trees in the tests are large, and some are sticks.
Write insert(root, key): plant key in the search tree with root root and return the root (for an empty tree root is None). If the key is already there, the tree doesn’t change. The starter code is almost right, but the tests won’t let it through. Find the mistake.
Plant three keys with the starter and draw the tree with show_tree from cs.viz. Where did the second key go?
When the branch is empty, insert(root.left, key) creates a new node and returns it, but the result isn’t stored anywhere. You need root.left = insert(root.left, key).
The section on planting warned about this mistake: the new node is created, but no old node links to it, and it is lost. In languages without a garbage collector such a node also goes on taking up memory, which is a leak. You can plant with a loop instead of recursion, too, as in the cell twins.py: then even a stick thousands of levels tall holds no terror for the tree.
Write height(root), the height of a binary tree: the number of nodes on the longest path from the root down. An empty tree (None) has height 0, a single node 1. The tree doesn’t have to be a search tree.
The height of a tree is one (the root itself) plus the height of the taller of its two branches.
Don’t forget the base case: an empty branch gives 0. Then a leaf comes out at $1 + \max(0, 0) = 1$.
This is a post-order traversal: first the heights of both branches, then the answer for the node. A stick thousands of levels tall is too much for the recursion; for one of those the height is counted level by level with a breadth-first traversal: a queue holds the nodes of the current level, each step moves on to the next level, and the walk stops when a level comes up empty. The number of steps is the height.
Write inorder(root): the list of keys of a binary tree in in-order, that is, left branch, node, right branch. For a search tree these are the keys in increasing order. The catch: the tests include sticks tens of thousands of levels tall, and recursion in Python runs into a limit of about a thousand. Walk the tree without recursion.
In Chapter 15 we rewrote recursion with a stack of our own: a stack of unfinished business kept in an ordinary list. What does the recursive walk put off for later? “Write down the node, then take care of its right branch.”
Go left, pushing every node you pass onto the stack. When there is nowhere further left to go, pop the top node off the stack, write down its key and move into its right branch, then go left as far as you can again.
Every node goes onto the stack once and comes off once, so the time is $O(n)$, and the stack grows no deeper than the height of the tree. It lives in an ordinary list, though, and its limit is memory rather than a thousand frames. Libraries that must not crash on someone else’s data walk their trees this way, without recursion.
Write is_bst(root): is this binary tree a search tree, that is, at every node are all keys of the left branch smaller than its key and all keys of the right branch larger? A search tree has no equal keys. An empty tree is a search tree. The starter compares each node only with its children and gets it wrong. Find a tree it lies about, and fix it.
Take a root of 10 with a 5 on its left, and a 12 on the right of the 5. Every node is in order with its own children. The tree isn’t: 12 sits in the left branch of 10.
Pass the bounds down: which keys are allowed in this branch at all. The root has no bounds. Going left from a node with key $k$, the upper bound becomes $k$; going right, the lower bound does.
Another way is the in-order traversal: a tree is a search tree if and only if that traversal gives a strictly increasing sequence.
Every node is checked once, time $O(n)$. The bounds travel down and narrow as they go: a key somewhere deep in a left branch must be smaller than its parent and also than every ancestor from which the path to it turned left. The starter checked the rule between neighbors, where checking is easy, although the rule is stated for whole branches. The mistake is common, and it turns up far beyond trees.
Write keys_between(root, lo, hi): the list of keys of a search tree from lo to hi inclusive, in increasing order. If lo > hi, the answer is empty. The tests plant two hundred thousand keys and ask thousands of narrow questions, so walking the whole tree for every question won’t be fast enough: go only into branches where the answer may be.
If a node’s key is smaller than lo, everything in its left branch is smaller still, and there is no point going there. If it is larger than hi, there is no point going right.
This is the function between from the section “An answer to the hash table.” The order of the calls (left branch, the node, right branch) is the same as in an in-order traversal, so the answer comes out sorted.
Two conditions turn a walk around the whole tree into a descent to the start of the range followed by a pass through the answers: $O(h + k)$, where $h$ is the height and $k$ the number of keys found. On a balanced tree of two hundred thousand keys a narrow question costs dozens of steps instead of two hundred thousand. When lo > hi, the function returns an empty list on its own: no key passes the check.
What next
A search tree keeps everything in order. Sometimes, though, the whole order isn’t needed, only the first in line. Patients arrive at a hospital emergency room; the one to treat first is the one in the worst state, not whoever arrived first. The queue from Chapter 15 hands out whoever came first. An AVL tree would hand out the worst case, its rightmost node, in $O(\log n)$, but to answer that one question it keeps the full order, holds two links per node and turns rotations. It would be nice to get by with an ordinary array, with no links and no rotations, and still produce the patient in the worst state quickly while new patients keep arriving. Such a structure exists. It is a tree too, only hidden inside a list, and it is the subject of the next chapter.