Better Balanced Binary Search Trees
So far, we have seen ...
- randomised trees ... make poor performance unlikely
- splay trees ... reasonable amortized performance
- but both types still have O(N) worst case
Ideally, we want both average/worst case to be O(logN)
- 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
|