Better Balanced Binary Search Trees
So far, we have seen …
- randomised trees … make poor performance unlikely
- occasional rebalance … fix balance periodically
- splay trees … reasonable amortized performance
- but both types still have O(n) worst case
Ideally, we want both average/worst case to be O(log n)
- AVL trees … fix imbalances as soon as they occur
- 2-3-4 trees … use varying-sized nodes to assist balance
- red-black trees … isomorphic to 2-3-4, but binary nodes
|