[prev] 61 [next]

Balanced BSTs

Reminder …
  • Goal: build binary search trees which have
    • minimum height ⇒ minimum worst case search cost
  • Best balance you can achieve for tree with N nodes:
    • tree height of log2N ⇒ worst case search O(log N)

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