[prev] 17 [next]

Balanced Binary Search Trees

Goal: build binary search trees which have
  • minimum depth ⇒ minimum worst case search cost
Perfectly balanced tree with N nodes has
  • abs(size(LeftSubtree) - size(RightSubtree)) < 2, for every node
  • depth of log2N ⇒ worst case search O(logN)
Three approaches to improving worst case search in BSTs:
  • randomize  -  reduce chance of worst-case scenario occuring
  • amortize  -  do more work at insertion to make search faster
  • optimize  -  implement all operations with performance bounds