Binary Search Tree Optimization

For simplicity, lets assume all searches are successful

Search cost of a key ki in BST T is 1 + sum(i=1 to n) depthT(ki)*pi, where p_i is the probability that we want i

Observations:

• Optimal BST may not have smallest height, based on probability
• Optimal BST may not have highest-probability key at the root

Build by exhaustive checking?

• Construct each n-node BST
• Then compute expected search cost
• But there are (4^n / n^(3/2))... options

Build by using Optimal Substructures!

Optimal substructure

• Consider an optimal BST T with a subtree T' with keys in a contiguous range ki,....kj for some 1 <= i <= j <= n
• Then T' must be an optimal BST for keys ki,...,kj

Proof: easily done with cut-and-paste

BST- Dynamic Programming

• Direct recursive implementation of the above recurrence is ineffective
• Use dynamic programming approach