Trees and recursion 0/36

Lesson 3 of 5

Binary search trees

Use the search-tree ordering rule to search, insert, delete and validate along a single path.

5,352 words · 24 min read

Part 1 of 10 Binary search trees

Binary search trees

Binary search finds values quickly in a sorted array, as long as the array does not change. In this lesson the collection changes while we use it: new values arrive between lookups. We keep a set of distinct numbers and want three operations:

  • add a number to the set;
  • say whether a number xx is in the set;
  • find the smallest number in the set that is at least xx.

Suppose the set holds 1, 3, 6, 8, 10 and 14. Then 6 is in the set and 7 is not, and the smallest number that is at least 7 is 8. A booking calendar uses the third operation whenever it looks up the next booking that starts at or after a given time.

A sorted array does the second and the third operation by binary search, in about log⁡2n\log_2 n comparisons for nn numbers. Adding is the slow one. The new number has to go in its sorted place, and every larger number moves one cell to the right to make room for it:

Adding 2 moves the five highlighted numbers one cell to the right.

In the worst case the numbers arrive in decreasing order. Each one then goes to the front and moves all the numbers that are already there, so nn numbers take 0+1+⋯+(n−1)0 + 1 + \dots + (n - 1) moves. For 200,000 numbers that is

199,999×200,0002≈2×1010 moves.\frac{199{,}999 \times 200{,}000}{2} \approx 2 \times 10^{10} \text{ moves.}

A computer copies a block of neighbouring numbers much faster than it runs the separate steps of a program: on our machine bisect.insort made these moves in about 5 seconds. That is still too slow for a typical time limit, and the moves grow with the square of nn: a million numbers make 25 times as many.

A hash set adds a number and looks one up in O(1)O(1) expected time. It keeps its numbers in no particular order, though, so the only way to find the smallest one that is at least xx is to read them all.

A third structure, the binary search tree, does all three in time that depends on its height hh:

Cost of each operation on a set of n numbers
Stored asAddIs xx in the set?Smallest value at least xx
Sorted arrayO(n)O(n)O(log⁡n)O(\log n)O(log⁡n)O(\log n)
Hash setO(1)O(1) expectedO(1)O(1) expectedO(n)O(n)
Binary search tree of height hhO(h)O(h)O(h)O(h)O(h)O(h)

A search tree keeps the numbers in the nodes of a binary tree, placed so that each of the three operations only has to walk down one path from the root. So an operation visits at most hh nodes, where hh is the height of the tree, the number of nodes on its longest path from the root down. For 200,000 numbers the height can be as small as 18, and the last part of the lesson shows when it is.

Definition

A binary search tree (BST) is a binary tree in which, at every node, every value in the left subtree is smaller than the node's value and every value in the right subtree is larger.

We call this condition the ordering rule.

A search tree of six numbers

Here is a binary search tree that holds our six numbers.

13681014

The left subtree of the root holds 3, 1 and 6, which are all smaller than 8, and the right subtree holds 10 and 14, which are larger. The same is true one level down, at 3 and at 10.

The rule is about everything below a node. The 6 is the right child of 3, and it is also in the left subtree of 8, so it has to be larger than 3 and smaller than 8.