[prev] 38 [next]

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