Optimal Binary Search Trees

Instead of hoping the incremental construction yields a shallow tree, we can construct the tree that minimizes the search time. We consider the common problem in which items have different probabilities to be the target of a search. For example,some words in the English dictionary are more commonly searched than others and are therefore assigned a higher probability. Let a₁ < a ₂ < . . . < a_n be the items and p_i is the corresponding probabilities. To simplify the discussion, we only consider successful searches and thus assume ⁿΣ_i=1   p_i = 1. The expected number of comparisons for a successful search in a binary search tree T storing the n item is

1+ C(T) = n Σi=1   pi.(δi + 1)
    = 1 + nΣi=1   pi.δi,

where δ i is the depth of the node that stores a_i . C(T ) is the weighted path length or the cost of T . We study the problem of constructing a tree that minimizes the cost. To develop an example, let n = 3 and p₁ = 2/1 , p₂ =1/3, p₃ =1/6 .

number of different binary trees with n nodes is 1/(n+1)(²ⁿ_n)  n , which is exponential in n. This is far too large to try all possibilities, so we need to look for a more efficient way to construct an optimum tree.