Given a fixed set of identifiers, the goal is to create a binary search tree. Different binary trees for the same identifier set have different performance characteristics.

• Fig (a) requires four comparisons in the worst case, and the average is $\frac{1+2+2+3+4}{5}=\frac{12}{5}$.
• Fig (b) requires three comparisons in the worst case, and the average is $\frac{11}{5}$ comparisons.

• The average number of comparisons is calculated assuming that each identifier is searched for with equal probability and that no unsuccessful searches are made.
• But in a practical situation, different identifiers are searched for with different frequencies or probabilities. Also, unsuccessful searches are present.

Probabilities

Assume the given set of identifiers is {a₁, a₂, …, a_n} with a₁ < a₂ < … < a_n.

• Let $p\left(i\right)$ be the probability with which we search for a_i.
• Let $q\left(i\right)$ be the probability that the identifier x being searched for satisfies $a_i<x<a_{i+1}$, 0 ≤ i ≤ n.

Assume $a_0=-\infty$ and $a_{n+1}=+\infty$.

is the probability of an unsuccessful search, and

External nodes

Add a fictitious (external) node in place of every empty subtree.

• If a binary search tree represents n identifiers, then there will be exactly n internal nodes and n + 1 external nodes.
• An internal node represents a point where a successful search terminates.
• An external node represents a point where an unsuccessful search terminates.

The identifiers not in the BST can be partitioned into n + 1 equivalence classes E_i, 0 ≤ i ≤ n:

• E₀ contains all identifiers x such that x < a₁.
• E_i contains all identifiers x such that a_i < x < a_i+1, 1 ≤ i < n.
• E_n contains all identifiers x such that x > a_n.

Cost of a binary search tree

The goal is to define an OBST for the identifier set {a₁, a₂, …, a_n}: a BST for which the cost is minimum.

Example

The number of possible BSTs for n nodes is

Solution: Given equal probabilities, i.e. $p\left(i\right)=q\left(i\right)=\frac{1}{7}$ for every i. The possible trees are:

Tree b is optimal.

Changed probabilities

If the probabilities are changed to p(1) = 0.5, p(2) = 0.1, p(3) = 0.05 and q(0) = 0.15, q(1) = 0.1, q(2) = 0.05, q(3) = 0.05, the cost of tree a is:

With the changed probabilities, tree c has the least cost (1.5), so it is the optimal tree.

The handwritten page gives 2.05 for tree d. Computing it with the same formula gives 2.15, so 2.15 is shown here.

Applying dynamic programming to OBST

Make a decision as to which of the a_i's should be assigned to the root node of the tree. If we choose a_k, then the internal nodes for a₁, a₂, …, a_k−1 and the external nodes for E₀, E₁, …, E_k−1 lie in the left subtree l of a_k. The remaining nodes will be in the right subtree r of a_k.

and

If w(i, j) is the sum

then the expected cost of the search tree is

If the tree is optimal, then its cost should be minimum, i.e. Cost(l) and Cost(r) should be minimum.

Let $c(i,j)$ be the cost of an OBST t_ij containing a_i+1, …, a_j and E_i, …, E_j. Then

In addition, k must be chosen such that the following is minimum:

⇒ The recurrence is:

$r(i,j)$ is the value of k that minimizes c(i, j) in (1). Compute c(i, j) such that j − i = 2, then for all c(i, j) with j − i = 3, and so on. (The cases j − i = 0 and j − i = 1 are set directly, as in the algorithm below.)

Example: n = 4, (a₁, a₂, a₃, a₄) = (do, if, int, while)

The probabilities are multiplied by 16 for convenience, so the actual values are P = (3/16, 3/16, 1/16, 1/16) and q = (2/16, 3/16, 1/16, 1/16, 1/16). If probabilities are given in this form, multiply them by their LCM.

There are two parts: (1) table construction and (2) OBST construction. Initially, for the first row:

For all other entries:

The completed table

Step-by-step calculations

w, c, r for (0, 1)

w, c, r for (1, 2)

w, c, r for (2, 3)

w, c, r for (3, 4)

w, c, r for (0, 2)

w, c, r for (1, 3)

w, c, r for (2, 4)

w, c, r for (0, 3)

w, c, r for (1, 4)

w, c, r for (0, 4)

Building the tree

$c_{04}=32$ is the minimum cost of a BST for (a₁, a₂, a₃, a₄).

• As r₀₄ = 2, the root is a₂, i.e. the left subtree is t₀₁ and the right subtree is t₂₄.
• As r₀₁ = 1, a₁ is the root of t₀₁, with subtrees t₀₀ and t₁₁.
• As r₂₄ = 3, a₃ is the root of t₂₄, with subtrees t₂₂ and t₃₄.
• As r₃₄ = 4, a₄ is the root of t₃₄.

The total time to evaluate all the c(i, j)'s and r(i, j)'s is $O\left(n^3\right)$.

Algorithm OBST(P, q, n)

Algorithm OBST(P, q, n)
/* Given n distinct identifiers a1 < a2 < ... < an and probabilities
   P[i], 1 ≤ i ≤ n, and q[i], 0 ≤ i ≤ n, this algorithm computes c[i,j]
   of OBSTs t_ij for identifiers a_{i+1}, ..., a_j. It also computes
   r[i,j], the root of t_ij, and w[i,j], the weight of t_ij. */
{
    for i := 0 to n-1 do
    {
        // Initialize
        w[i,i] := q[i];  r[i,i] := 0;  c[i,i] := 0.0;
        // OBSTs with one node
        w[i,i+1] := q[i] + q[i+1] + P[i+1];
        r[i,i+1] := i + 1;
        c[i,i+1] := q[i] + q[i+1] + P[i+1];
    }
    w[n,n] := q[n];  r[n,n] := 0;  c[n,n] := 0.0;
    for m := 2 to n do          // Find optimal trees with m nodes
        for i := 0 to n-m do
        {
            j := i + m;
            w[i,j] := w[i,j-1] + P[j] + q[j];
            k := Find(c, r, i, j);
            c[i,j] := w[i,j] + c[i,k-1] + c[k,j];
            r[i,j] := k;
        }
    write(c[0,n], w[0,n], r[0,n]);
}

Algorithm Find(c, r, i, j)

Algorithm Find(c, r, i, j)
{
    min := ∞;
    for m := r[i,j-1] to r[i+1,j] do
        if (c[i,m-1] + c[m,j]) < min then
        {
            min := c[i,m-1] + c[m,j];  l := m;
        }
    return l;
}