A self-balancing binary search tree keeps its height logarithmic in the number of elements. In a height-balanced tree, each node’s left and right subtree heights differ by at most one, and both subtrees are balanced. section 11.19 section 11.20
With height constrained to O(log(n)), a balanced binary search tree provides predictable performance:
- Search, insertion, deletion, predecessor, successor, minimum, and maximum all take O(log(n)) time. section 11.20
- It offers the same general ordered-data role as a sorted array, while averaging better performance across the full range of operations. section 11.19
- Unlike an ordinary BST, it uses balancing strategies to prevent height from growing too large. section 11.19
Common balancing strategies
Randomized heaps provide nondeterministic balance, while red–black trees and 2–3 trees are among the most-used balanced search trees. section 11.19
