When data must remain ordered while elements are inserted, removed, searched, or revisited, a priority queue is too restrictive and an array is too inflexible. A self-balancing binary search tree keeps keys ordered while maintaining logarithmic height. section 3.0 section 8.2.4
A binary search tree follows one root-to-leaf path: compare the target with each node, turn left for a smaller key and right otherwise. Its operations take time proportional to tree height. If insertion order creates a skewed tree, height can become linear; balancing keeps it logarithmic. section 4.4.4 section 9.2.2
A balanced tree is useful when ordered operations matter:
- Search, insertion, and removal run in O(log n) time when the tree remains balanced. section 4.4.4 section 8.2.4
- Minimum and maximum retrieval are constant-time with suitable tree references, while predecessor and successor queries take O(log n). section 4.4.4
- An in-order traversal returns all stored keys in sorted order in linear time. section 4.4.4
- Choose a hash table instead when ordering is irrelevant and constant-time amortized core operations are the priority. section 4.4.4
Balancing can be guaranteed by structures such as 2-3 trees and red-black trees. A 2-3 tree splits an overfull leaf and promotes its middle key; a red-black tree encodes 2-3 nodes with colored links and restores invariants through rotations. Treaps offer simpler algorithms and tend toward balance with high probability by combining search-tree and heap properties. section 3.4.1
Nearest-neighbor lookup
Store cities and warehouses by their one-dimensional coordinate in a balanced BST. Search for the target coordinate; with no exact match, compare the failed-search node and its parent to identify the closest entry, reducing a million-point scan to roughly twenty tree levels. section 8.2.4
