Card 01/ 09
Binary Search Trees: Ordered for One Descent
Every key on the left is smaller and every key on the right is larger, at every node.
A binary search tree is a binary tree that keeps its keys in order: at every node, every key in the left subtree is smaller than the node's key, and every key in the right subtree is larger. This card covers that ordering rule, why it lets a search follow a single path down from the root, and what each operation costs.
A key is the value the tree is ordered by, such as a number, a name or a date, and the tree may store other data alongside it. The rule applies to whole subtrees, not only to a node's two children. A key anywhere below the left child of 4 must be smaller than 4, so each position in the tree allows a range of keys. In the tree below, each note gives the range that the node's position allows.
4, root: any key
2, below 4
1, below 2
3, between 2 and 4
6, above 4
5, between 4 and 6
7, above 6
The rule turns a search into one descent. Compare the key you want with the root's key: if they are equal, it is found; if the key is smaller, it can only be in the left subtree, and if larger, only in the right. Each comparison discards one whole subtree, so the search visits one node per level. A run searched this tree for 5 and compared 4, 6 and 5. Its search for 8 compared 4, 6 and 7, then met an empty link to the right of 7, and that empty link proves 8 is absent.
A game of higher or lower works the same way. Each answer rules out every number on one side of the guess. The likeness breaks at the halving. A good guesser always picks the middle of what is left, as binary search does when it finds a value in a sorted array by comparing with the middle element and discarding half. A tree's node may sit anywhere in its range, and if every node has only a right child, each comparison rules out one key.
So every operation costs time in proportion to the tree's height, h. The table gives the costs for a tree of n keys. Average means over keys inserted in a random order, which gives a height that grows in proportion to log n; the worst case is a tree shaped like a chain.
| Operation | Cost | Case | Why |
|---|---|---|---|
| Search for a key | O(log n) | Average | One comparison per level on a single path down |
| Insert a key | O(log n) | Average | A search that ends at an empty link, where the new key is placed |
| Delete a key | O(log n) | Average | A search, then at most one further descent to find a replacement |
| Find the smallest key | O(log n) | Average | Follow left links until there are none |
| Any of these on a tree shaped like a chain | O(n) | Worst | Every node lies on the one path |
| Visit every key in sorted order | O(n) | Every case | An in-order traversal visits each node once |
The last row is the property a hash table cannot offer. An in-order traversal, which visits a node's left subtree, then the node, then its right subtree, lists the keys of a binary search tree from smallest to largest. The run listed the keys from 2 to 5 by visiting only the subtrees whose ranges overlap that interval.
← → move through sections and cards