[prev] 49 [next]

Balanced Binary Search Trees

Goal: build binary search trees which have
  • minimum height ⇒ minimum worst case search cost
Best balance you can achieve for tree with N nodes:
  • abs(#nodes(LeftSubtree) - #nodes(RightSubtree)) ≤ 1, for every node
  • height of log2N ⇒ worst case search O(log N)

[Diagram:Pic/binary-search-trees.png]