The cost of a search tree is fixed by the order the keys arrived in, not by the keys. Fifteen keys inserted in sorted order give a path of height 14; the same fifteen in a shuffled order give height 6, and middle-first gives 3. A uniformly random order gives expected height O(log n) — stated here, and the recurrence behind it is the one Sorting and Selection solves for randomised quicksort.
Core ideas
One idea and two things it is constantly confused with. The idea is that the order is the whole story; the confusions are between height and mean depth, and between either of them and an asymptotic formula.
Insertion has no choices: the new key goes where the search for it failed. So the order fixes the tree, and the same key set can produce anything from a path of height n − 1 to a tree of height ⌊log₂ n⌋. “These keys are badly distributed” is almost never the problem; the keys arriving sorted is, and sorted input is the single commonest way real data arrives.
The height is the longest path, and it is what a worst-case search costs. The mean depth is the average over all nodes, and it is what a search for a uniformly chosen key costs. At n = 15 the shuffled tree has height 6 and mean depth 44/15 ≈ 2.93 — the two differ by a factor of two, and a page that printed one number would be ambiguous about which claim it was making.
Insert n distinct keys in a uniformly random order and the expected height is O(log n). The randomness is in the arrival order; the keys themselves can be anything. This is why the fix for the shape problem in the two randomised trees later on is to inject randomness deliberately rather than to hope the input has some.
The material
Why sorted input is the worst case, what a shuffle actually buys, and how to read the asymptote printed beside the measurements.
Insertion into a search tree is deterministic given the order. Each new key walks from the root to the empty position where a search for it would have failed, and there is exactly one such position. So the tree is a function of the sequence, and asking “how tall is the tree for these keys” is not a well-posed question.
Insert 10, 20, 30, …, 150. Every key is larger than everything present, so every key becomes the right child of the previous one: a path of height 14 on fifteen keys. Reversed input does the same thing leftwards. Sorted arrival is what you get from a database dump ordered by primary key, a log replayed by timestamp, or an identifier that increments — so the worst case for this structure is also one of the most common inputs in practice.
Read the last line carefully, because it is the one number on this page that was not counted. 2 ln n is the asymptotic expected depth of a node in a tree built from a uniformly random order. At n = 15 it evaluates to 5.416, and the lab draws it as a dashed reference curve and labels its readout asymptotic. It is not the height of any of the trees above — the shuffled tree’s height is 6 and the balanced tree’s is 3 — and it is not the measured mean depth either, which is 2.93 on the shuffle.
So there are three numbers on screen and they are three different quantities: the measured height, the longest path in the tree drawn; the measured mean depth, an exact fraction over the nodes of that tree; and the asymptote, a formula about the limit of an average over orders. At n = 15 the asymptote is about 85% above the measured mean depth, which is what an asymptotic formula does at small n. Push the size up and the gap narrows; it does not close from above or below in any tidy way, because one shuffle is one sample.
Insert n distinct keys in an order chosen uniformly at random from all n! orders. The expected height of the resulting tree is O(log n), and the expected depth of a node is 2 ln n + O(1).
This is stated here and proved elsewhere. The recurrence it comes from is the one produced by choosing a uniformly random root and recursing on the two pieces — which is exactly the recurrence “Randomised Quicksort” solves on the Sorting and Selection course, because a random pivot and a random root are the same object looked at twice. “Treaps”, on the Randomised Algorithms course, closes the loop by building a tree whose shape is random no matter what order the keys arrive in.
The shuffled order above gives height 6 where sorted gives 14: a factor of more than two, and 44 comparisons to build rather than 105. That is a real and large improvement, and it is one sample. Run a different seed and the height moves. The theorem is about the average over all orders, and no single shuffle establishes it — which is the same caution as everywhere else on this course, sharpened by the fact that here the quantity in question is itself an average.
And a shuffle is not always available. It requires having all the keys before inserting any of them, which defeats the point of an online structure. If keys arrive one at a time from a sorted stream there is nothing to shuffle, and the tree degenerates as it grows. That is the gap the rest of this course closes: instead of hoping the order is random, enforce a shape condition on every insertion, which is what “Rotations and the AVL Invariant” begins.
One last measurement worth having. The bisect order — middle key first, then the middle of each half, recursively — gives height 3 at n = 15, which is ⌊log₂ 15⌋: the shortest a tree on fifteen nodes can be. It costs 34 comparisons to build. It is also useless as a strategy, for the same reason a shuffle often is: you have to know all the keys and their order in advance, which is to say you have to have sorted them already.
Interactive
Height and mean depth counted, with 2 ln n drawn dashed as the asymptote it is
Method
Predict before running. A prediction that turns out wrong is the only cheap way to find out which of the three numbers you were thinking of.
Ask what happens to each arriving key relative to the ones already there. Monotone in either direction gives a path of height n − 1. Alternating between extremes gives a path too. The keys’ values matter only through their relative order.
The height is the longest path; the mean depth is the average over nodes. Write both predictions down. Getting the height right and the mean depth wrong is the normal outcome the first few times, and it is the thing worth finding out.
Sorted for the first. Middle-first, recursively, for the second — and notice while doing it that you needed the sorted key list to build it, which is why it is a diagnostic rather than a strategy.
Measured height, measured mean depth, 2 ln n. Say aloud which is which before drawing any conclusion. The asymptote is about an average over orders in the limit, and at n = 15 it sits well above the measured mean depth of a shuffled tree.
The first few insertions of each order, far enough to see the shape being decided, with the finished measurements underneath.
Every insertion in the sorted case goes to the right of everything, because it is larger than everything, and there is no decision to make anywhere. That is the whole of the degeneracy: the structure is doing exactly what it is defined to do and the order is doing all the damage.
The shuffle’s height is 6 against the balanced 3 and the degenerate 14. Its mean depth, 44/15, is much closer to the balanced tree’s 34/15 than to the path’s 7 — which is the useful way to summarise what randomness buys: it makes the typical search nearly optimal while leaving the worst search a constant factor worse.
For a faded rehearsal, run n = 31 with each order. The supplied observation is that sorted must give height 30 and mean depth 15, by the same argument as above. Predict the shuffle’s height before looking — the lab reports 9, with mean depth 139/31 ≈ 4.48 against 2 ln 31 = 6.868 — and then say which of the three numbers on your screen would change if you changed nothing but the seed.
You should be able to predict the height and the mean depth of a tree from a stated insertion order, construct an order that degenerates a key set and one that balances it, and say of each number on the lab’s panel whether it was counted from the tree drawn or evaluated from an asymptotic formula.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.