Search Trees
Search trees store ordered keys in a hierarchical structure so that search, insertion and deletion follow a root-to-leaf path; self-balancing variants keep that path short to guarantee logarithmic-time operations.
Definition
A search tree is a tree-structured data structure that maintains keys in sorted order according to a per-node ordering invariant, supporting efficient search, insertion, deletion and order-based queries; a balanced search tree additionally constrains its shape so that height stays logarithmic in the number of keys.
Scope
This topic covers ordered dictionary structures based on trees: the binary search tree and its ordering invariant, the self-balancing schemes that bound height (AVL, red-black, and others), and multiway balanced trees such as B-trees designed for external storage. It addresses the operations these structures support beyond simple lookup — predecessor, successor, range queries and ordered traversal — and contrasts them with hash tables, which do not preserve order.
Core questions
- How does the binary-search-tree ordering invariant make search a root-to-leaf walk?
- Why can an unbalanced tree degrade to linear time, and how does balancing prevent it?
- What rotations or structural rules keep AVL and red-black trees balanced?
- Why are B-trees suited to disk and database storage rather than binary trees?
- When are order-preserving operations worth the extra cost over a hash table?
Key concepts
- binary search tree invariant
- tree rotations
- AVL trees
- red-black trees
- B-trees
- tree height and balance
- in-order traversal
- range and successor queries
Key theories
- Height balancing guarantees logarithmic operations
- By maintaining a balance invariant through rotations or structural rules, self-balancing trees keep height O(log n), guaranteeing worst-case O(log n) search, insertion and deletion regardless of input order.
- Multiway trees for external memory
- B-trees store many keys per node to match disk block sizes, minimizing the number of slow external-memory accesses; this makes them the standard structure for databases and file systems.
Clinical relevance
Search trees are central to systems that need ordered access: red-black trees implement ordered maps and sets in standard libraries, B-trees and their variants are the dominant index structure in relational databases and file systems, and balanced trees support range queries, interval scheduling and geometric search structures.
History
AVL trees, the first self-balancing binary search trees, were introduced by Adelson-Velsky and Landis in 1962. Bayer and McCreight introduced B-trees in 1972 for large ordered indexes, and red-black trees were developed by Guibas and Sedgewick in 1978 as a practical balancing scheme, becoming the basis of many standard library implementations.
Key figures
- Georgy Adelson-Velsky
- Evgenii Landis
- Rudolf Bayer
- Robert Sedgewick
- Robert Tarjan
Related topics
Seminal works
- bayer1972
- cormen2009
Frequently asked questions
- Why not always use a hash table instead of a search tree?
- Hash tables give faster average lookups but no ordering. Search trees keep keys sorted, enabling range queries, ordered iteration, and predecessor/successor lookups in O(log n), which hash tables cannot do efficiently. The choice depends on whether order matters.
- Why do databases use B-trees instead of binary search trees?
- B-trees pack many keys into each node to match the size of a disk block, so a search touches far fewer slow external-memory blocks than a binary tree of the same key count. This minimizes I/O, which dominates performance in databases and file systems.