[prev] [index] [next]

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