Answers · Making it fast enough
Why does inserting already sorted numbers turn a binary search tree into a linked list?
In shortBecause each new number is bigger than every number already stored, so it is always attached down the right side, and the tree becomes a chain as deep as the number of items.
Every number arrives larger than all the numbers already in the tree, so every comparison sends it right and it comes to rest as the right child of the deepest node. The finished tree has no left branch anywhere and a depth equal to the number of items, so a search that was meant to halve now walks.
| inserted | comparisons made | where it lands | depth after |
|---|---|---|---|
| 1 | 0 | the root | 1 |
| 2 | 1 | right of 1 | 2 |
| 3 | 2 | right of 2 | 3 |
| 4 | 3 | right of 3 | 4 |
| 5 | 4 | right of 4 | 5 |
| 6 | 5 | right of 5 | 6 |
| 7 | 6 | right of 6 | 7 |
| all seven | 21 | 7 |
Read the last column downwards: it climbs by one every time. Nothing in the insertion procedure chose that. The procedure only ever asks whether the new item is smaller or larger than the node in front of it, and with sorted input the answer is always larger, so the walk turns right at every node it meets and the new node hangs off the end of the right spine. A tree of seven items that had been filled level by level would be three deep, because is the first power of two at least as large as seven.
What it costs
Scale that to a million items. Sorted arrivals give a depth of ; the best any binary tree of a million nodes can do is , because is too few to hold them and is enough. Searching the chain for the largest item walks all million nodes. Searching for an average item is no better than half of that, since the items sit at depths through in equal numbers and the mean of those depths is the middle of the range.
Building it is quadratic rather than merely slow to search. Inserting a million items one at a time into a chain performs comparisons, because each insertion first walks the whole chain it has already built. At twenty thousand items the same effect shows up as a shuffled build finishing in seconds while the sorted build takes seconds, which is times longer for identical work and identical memory.
Sorted input is the worst case, not the tidy one
The natural guess is that handing a structure its data in order is helpful, since it is the order you would use for a scan or a printout. A search tree never sees the order of the whole set. It sees one item at a time and compares it only against the items already stored, so what matters is each item's rank among its predecessors, not among the full collection. Sorted data makes every item extreme relative to everything before it, and extreme items are exactly the ones that lengthen a spine; a random order mixes ranks, so most items land somewhere in the middle and the two sides grow together. The same twenty thousand items shuffled produce a tree deep against the sorted tree's , a factor of , and the build time differs by the factor of worked out above.
Reversing the sorted list does not rescue it: every item is then smaller than all its predecessors and the chain grows down the left instead, to the same depth. Nor is a lucky arrival order a plan, because random insertion at a million items gives a longest path of about rather than the ideal , which is times worse, so even the good case pays a premium. The depth stops depending on arrival order only when the insertion procedure itself intervenes, for instance by rearranging whenever the two sides of a node differ in depth by more than one; sorted arrivals then cost extra rotations during insertion while the depth stays near . Without such a rule the structure keeps the memory footprint of a tree and the behaviour of a list.
Worth keeping
- Inserting items in increasing order makes every comparison turn right, so the tree becomes a right spine whose depth equals the item count.
- A chain of a million nodes answers a typical search in about 500,000 steps where a balanced tree needs 20, and costs about 500 billion comparisons to build.
- Reversing a sorted list produces the mirror image, a left spine of the same depth, so neither increasing nor decreasing order is safe.
Where this goes next
This question is one step of Keeping Things in Order, a course that works through its subject from the beginning. The page that teaches this part of it is When a Tree Degenerates Into a List, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- Why do databases use B-trees rather than binary search trees for indexes?Because a database index pays for disk blocks read, not comparisons made, and a wide shallow tree needs only a few block reads per lookup.
- How does a heap know the smallest item without keeping the whole collection sorted?A heap only keeps each parent no larger than its children, so the top is always the smallest even though the rest is not sorted.
- How does merge sort get n log n by splitting and merging?Splitting halves the number of runs each round, so there are about log base 2 of n rounds; merging every item once per round gives n log n.
- Why does binary search only work if the list is sorted?Because only in a sorted list does one comparison against the middle tell you that half the items cannot be the one you want.
- Why doesn't breadth-first search give the cheapest path once the links have different costs?Breadth-first search counts links rather than costs, so it can return a route with fewer links that is more expensive than a longer route.
- Why is O(2n) treated the same as O(n)?Because it describes how cost grows rather than exact cost, doubling every cost does not change the growth class.