an element strictly greater than . These probabilities cover all possible searches, and therefore add up to one.

The static optimality problem is the optimization problem of finding the binary search tree that minimizes the expected search time, given the probabilities. As the number of possible trees on a set of elements is , which is exponential in , brute-force search is not usually a feasible solution.

Knuth's dynamic programming algorithm

1.Previous
3.Next