Binary Search Trees
The BST invariant
A binary search tree (BST) is a binary tree where each branch node holds a (key, value) pair, and the keys satisfy:
- All keys in the left subtree are less than the node’s key.
- All keys in the right subtree are greater than the node’s key.
- This property holds recursively at every node.
BSTs require a total ordering on keys (e.g., numeric or lexicographic order). This is a stronger requirement than association lists, which need only equality.
Balanced vs. unbalanced
| Tree shape | Lookup time | Example cause |
|---|---|---|
| Balanced | O(log n) | Random insertion order |
| Unbalanced (degenerate) | O(n) | Insertions in sorted order |
Building a BST by repeatedly inserting elements in increasing or decreasing order produces a degenerate tree that is essentially a linked list. This is analogous to quicksort’s worst case: the pivot (root key) does not divide the data evenly.
Treesort
If we insert all elements into a BST and then perform an inorder traversal, the result is a sorted list. This algorithm is called treesort. Its complexity mirrors that of quicksort: O(n log n) average case, O(_n_²) worst case.
Self-balancing trees
Self-balancing trees (e.g., Red-Black trees, AVL trees) maintain the O(log n) guarantee in the worst case by automatically restructuring the tree after insertions and deletions. They are more complex to implement but are the standard choice for production dictionary data structures. The course mentions them but does not cover their implementation.