Optimal binary search trees

Optimal binary search trees (Dynamic programming)

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

Suppose “n” keys k₁, k₂, …, k _n are stored at the internal nodes of a binary search tree. It is assumed that the keys are given in sorted order, so that k₁< k₂ < … < k_n. For each key k_i , we have a probability p_i that a search will be for k_i. Some searches may be for values not in K, and so we also have n + 1 “dummy keys” d₀, d₁, d₂, . . . ,d_n representing values not in K. For each dummy key d_i , we have a probability q_i that a search will correspond to d_i. 

Figure shows binary search tree for a set of n = 5 keys. Each key k_i is an internal node, and each dummy key d_i is a leaf. Every search is either successful (finding some key k_i ) or unsuccessful (finding some dummy key d_i), and so we have

Because binary search tree has probabilities of searches for each key and each dummy key, the expected cost of a search can be determined.

For a given set of probabilities, a binary search tree whose expected search cost is smallest can be constructed. And such a tree is called an optimal binary search tree.

The number of binary trees with n nodes is Ω(4ⁿ / n^3/2), and to examine an exponential number of binary search trees in an exhaustive search.

Solving this problem with dynamic programming:

Step 1: The structure of an optimal binary search tree

If an optimal binary search tree T has a sub tree T^l containing keys k_i . . . . .k_j , then this sub tree T^l must be optimal as well for the sub problem with keys k_i . . . . ,k_j and dummy keys d_i-1, . . . ,d_j. 

The optimal substructure is used to show that an optimal solution can be constructed to the problem from optimal solutions to sub problems.

Step 2: A recursive solution

Pick subproblem domain as finding an optimal binary search tree containing the keys k_i , . . . ,k_j, where i ≥ 1, j ≤ n, and j = i - 1.

Let e[ i, j ] as the expected cost of searching an optimal binary search tree containing the keys k_i , . . . ,k_j .

The easy case occurs when j = i - 1. Then we have just the dummy key d_i-1. The expected search cost is e[i, i – 1] = q_i-1.

When j ≥ i , there is a need to select a root k_r from k_i , . . . ,k_j and then make an optimal binary search tree with keys k_i , . . . ,k_r-1 as its left sub tree and an optimal binary search tree with keys k_r+1, . . . ,k_j as its right sub tree.

For a sub

tree with keys k_i , . . . ,k_j , let us denote this sum of probabilities as

Thus, if k_r is the root of an optimal subtree containing keys k_i , . . . ,k_j, then

Choose the root that gives the lowest expected search cost, giving final recursive formulation:

Step 3: Computing the expected search cost of an optimal binary search tree

The pseudo code that follows takes as inputs the probabilities p₁, . . . ,p_n and q₀, . . . ,q_n and the size n, and it returns the tables e and root.

The OPTIMAL-BST procedure takes θ (n³) time

Example: