A binary search tree (BST) stores comparable keys in a binary tree. At each node, comparison sends a smaller key left and a larger or equal key right, so a search follows one root-to-leaf path. section 4.4.4
Use a BST when ordered operations matter:
- Search, insertion, and removal take time proportional to tree height. section 4.4.4
- A balanced BST gives logarithmic-time search, insertion, and removal. section 4.4.4 section 8.2.4
- Minimum, maximum, predecessor, and successor operations benefit from the ordering, and an in-order traversal returns keys sorted in linear time. section 4.4.4
- Balance is essential: poorly shaped trees can lose the practical advantage of logarithmic height, especially after ordered insertions. section 3.5.2 section 8.2.4
Nearest-neighbor lookup
Store cities and warehouses by their one-dimensional coordinate. To find the closest entry to coordinate 75, follow BST search; an exact match wins, otherwise compare the failed-search node with its parent. A balanced tree reduces the search from linear scanning to logarithmic descent. section 8.2.4
Figure 8.5 A balanced binary search tree containing cities and warehouses in our example. Note that this is only one of the possible balanced search trees for these values. For this set of values, there are at least 32 valid binary search trees that are also balanced. As an exercise, you can try to enumerate all of them (hint: Which internal nodes can be rotated1 without changing the tree height?)
Inspect how cities and warehouses occupy a balanced BST and how rotations can produce different balanced shapes without changing tree height. section 8.2.4
Figure 8.6 Using search on a binary search tree to find the nearest neighbor (in 1-D) of a target point
Trace the search path used to identify a one-dimensional nearest neighbor when the target is not stored exactly. section 8.2.4
