[prev] 8 [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]

Three strategies to improving worst case search in BSTs:
  • randomise  —  reduce chance of worst-case scenario occuring
  • amortise  —  do more work at insertion to make search faster
  • optimise  —  implement all operations with performance bounds