Definition edit

In the static optimality problem as defined by Knuth,^[2] we are given a set of n ordered elements and a set of ${\displaystyle 2n+1}$  probabilities. We will denote the elements ${\displaystyle a_{1}}$  through ${\displaystyle a_{n}}$  and the probabilities ${\displaystyle A_{1}}$  through ${\displaystyle A_{n}}$  and ${\displaystyle B_{0}}$  through ${\displaystyle B_{n}}$ . ${\displaystyle A_{i}}$  is the probability of a search being done for element ${\displaystyle a_{i}}$  (or successful search).^[3] For ${\displaystyle 1\leq i<n}$ , ${\displaystyle B_{i}}$  is the probability of a search being done for an element between ${\displaystyle a_{i}}$  and ${\displaystyle a_{i+1}}$ (or unsuccessful search),^[3] ${\displaystyle B_{0}}$  is the probability of a search being done for an element strictly less than ${\displaystyle a_{1}}$ , and ${\displaystyle B_{n}}$  is the probability of a search being done for an element strictly greater than ${\displaystyle a_{n}}$ . These ${\displaystyle 2n+1}$  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 ${\displaystyle 2n+1}$  probabilities. As the number of possible trees on a set of n elements is ${\displaystyle {2n \choose n}{\frac {1}{n+1}}}$ ,^[2] which is exponential in n, brute-force search is not usually a feasible solution.

Knuth's dynamic programming algorithm edit

In 1971, Knuth published a relatively straightforward dynamic programming algorithm capable of constructing the statically optimal tree in only O(n²) time.^[2] In this work, Knuth extended and improved the dynamic programming algorithm by Edgar Gilbert and Edward F. Moore introduced in 1958.^[4] Gilbert's and Moore's algorithm required ${\displaystyle O(n^{3})}$  time and ${\displaystyle O(n^{2})}$  space and was designed for a particular case of optimal binary search trees construction (known as optimal alphabetic tree problem^[5]) that considers only the probability of unsuccessful searches, that is, ${\textstyle \sum _{i=1}^{n}A_{i}=0}$ . Knuth's work relied upon the following insight: the static optimality problem exhibits optimal substructure; that is, if a certain tree is statically optimal for a given probability distribution, then its left and right subtrees must also be statically optimal for their appropriate subsets of the distribution (known as monotonicity property of the roots).

To see this, consider what Knuth calls the "weighted path length" of a tree. The weighted path length of a tree of n elements is the sum of the lengths of all ${\displaystyle 2n+1}$  possible search paths, weighted by their respective probabilities. The tree with the minimal weighted path length is, by definition, statically optimal.

But weighted path lengths have an interesting property. Let E be the weighted path length of a binary tree, E_L be the weighted path length of its left subtree, and E_R be the weighted path length of its right subtree. Also let W be the sum of all the probabilities in the tree. Observe that when either subtree is attached to the root, the depth of each of its elements (and thus each of its search paths) is increased by one. Also observe that the root itself has a depth of one. This means that the difference in weighted path length between a tree and its two subtrees is exactly the sum of every single probability in the tree, leading to the following recurrence:

${\displaystyle E=E_{L}+E_{R}+W}$ 

This recurrence leads to a natural dynamic programming solution. Let ${\displaystyle E_{ij}}$  be the weighted path length of the statically optimal search tree for all values between a_i and a_j, let ${\displaystyle W_{ij}}$  be the total weight of that tree, and let ${\displaystyle R_{ij}}$  be the index of its root. The algorithm can be built using the following formulas:

${\displaystyle {\begin{aligned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\operatorname {for} 1\leq i\leq n+1\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\\E_{i,j}&=\min _{i\leq r\leq j}(E_{i,r-1}+E_{r+1,j}+W_{i,j})\operatorname {for} 1\leq i\leq j\leq n\end{aligned}}}$ 

The naive implementation of this algorithm actually takes O(n³) time, but Knuth's paper includes some additional observations which can be used to produce a modified algorithm taking only O(n²) time.

In addition to its dynamic programming algorithm, Knuth proposed two heuristics (or rules) to produce nearly (approximation of) optimal binary search trees. Studying nearly optimal binary search trees was necessary since Knuth's algorithm time and space complexity can be prohibitive when ${\displaystyle n}$  is substantially large.^[6]

Knuth's rules can be seen as the following:

• Rule I (Root-max): Place the most frequently occurring name at the root of the tree, then proceed similarly on the subtrees.
• Rule II (Bisection): Choose the root so as to equalize the total weight of the left and right subtree as much as possible, then proceed similarly on the subtrees.

Knuth's heuristics implements nearly optimal binary search trees in ${\displaystyle O(n\log n)}$  time and ${\displaystyle O(n)}$  space. The analysis on how far from the optimum Knuth's heuristics can be was further proposed by Kurt Mehlhorn.^[6]

Mehlhorn's approximation algorithm edit

While the O(n²) time taken by Knuth's algorithm is substantially better than the exponential time required for a brute-force search, it is still too slow to be practical when the number of elements in the tree is very large.

In 1975, Kurt Mehlhorn published a paper proving important properties regarding Knuth's rules. Mehlhorn's major results state that only one of Knuth's heuristics (Rule II) always produces nearly optimal binary search trees. On the other hand, the root-max rule could often lead to very "bad" search trees based on the following simple argument.^[6]

Let

${\textstyle {\begin{aligned}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~~\operatorname {with} ~~\sum _{i=1}^{n}\varepsilon _{i}=2^{-k}\end{aligned}}}$ 

and

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {for} ~~1\leqq i\leqq n~~\operatorname {and} ~~B_{j}=0\operatorname {for} ~~0\leqq j\leqq n.\end{aligned}}}$ 

Considering the weighted path length ${\displaystyle P}$  of the tree constructed based on the previous definition, we have the following:

${\textstyle {\begin{aligned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_{j}\\&=\sum _{i=1}^{n}A_{i}i\\&\geqq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1)}{2}}\geqq {\frac {n}{2}}.\end{aligned}}}$ 

Thus, the resulting tree by the root-max rule will be a tree that grows only on the right side (except for the deepest level of the tree), and the left side will always have terminal nodes. This tree has a path length bounded by ${\textstyle \Omega ({\frac {n}{2}})}$  and, when compared with a balanced search tree (with path bounded by ${\textstyle O(2\log n)}$ ), will perform substantially worse for the same frequency distribution.^[6]

In addition, Mehlhorn improved Knuth's work and introduced a much simpler algorithm that uses Rule II and closely approximates the performance of the statically optimal tree in only ${\displaystyle O(n)}$  time.^[6] The algorithm follows the same idea of the bisection rule by choosing the tree's root to balance the total weight (by probability) of the left and right subtrees most closely. And the strategy is then applied recursively on each subtree.

That this strategy produces a good approximation can be seen intuitively by noting that the weights of the subtrees along any path form something very close to a geometrically decreasing sequence. In fact, this strategy generates a tree whose weighted path length is at most

${\displaystyle 2+(1-\log({\sqrt {5}}-1))^{-1}H=2+{\frac {H}{1-\log({\sqrt {5}}-1)}}}$ 

where H is the entropy of the probability distribution. Since no optimal binary search tree can ever do better than a weighted path length of

${\displaystyle (1/\log 3)H={\frac {H}{\log 3}}}$ 

this approximation is very close.^[6]

Hu–Tucker and Garsia–Wachs algorithms edit

In the special case that all of the ${\displaystyle A_{i}}$  values are zero, the optimal tree can be found in time ${\displaystyle O(n\log n)}$ . This was first proved by T. C. Hu and Alan Tucker in a paper that they published in 1971. A later simplification by Garsia and Wachs, the Garsia–Wachs algorithm, performs the same comparisons in the same order. The algorithm works by using a greedy algorithm to build a tree that has the optimal height for each leaf, but is out of order, and then constructing another binary search tree with the same heights.^[7]

The following code snippet determines an optimal binary search tree when given a set of keys and probability values that the key is the search key:

public static float calculateOptimalSearchTree(int numNodes, float[] probabilities, int[][] roots) {
       float[][] costMatrix = new float[numNodes + 2][numNodes + 1];
       for (int i = 1; i <= numNodes; i++) {
           costMatrix[i][i - 1] = 0;
           costMatrix[i][i] = probabilities[i];
           roots[i][i] = i;
           roots[i][i - 1] = 0;
       }
       for (int diagonal = 1; diagonal <= numNodes; diagonal++) {
           for (int i = 1; i <= numNodes - diagonal; i++) {
               int j = i + diagonal;
               costMatrix[i][j] = findMinCost(costMatrix, i, j) + sumProbabilities(probabilities, i, j);
               // Note: roots[i][j] assignment is missing, this needs to be fixed if you want
               // to reconstruct the tree.
           }
       }
       return costMatrix[1][numNodes];
}

Do splay trees perform as well as any other binary search tree algorithm?