Optimal binary search tree

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.

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]

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]

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]

There are several different definitions of dynamic optimality, all of which are effectively equivalent to within a constant factor in terms of running-time.[8] The problem was first introduced implicitly by Sleator and Tarjan in their paper on splay trees,[9] but Demaine et al. give a very good formal statement of it.[8]

In the dynamic optimality problem, we are given a sequence of accesses x₁, ..., x_m on the keys 1, ..., n. For each access, we are given a pointer to the root of our BST and may use the pointer to perform any of the following operations:

1. Move the pointer to the left child of the current node.
2. Move the pointer to the right child of the current node.
3. Move the pointer to the parent of the current node.
4. Perform a single rotation on the current node and its parent.

(It is the presence of the fourth operation, which rearranges the tree during the accesses, which makes this the dynamic optlmality problem.)

For each access, our BST algorithm may perform any sequence of the above operations as long as the pointer eventually ends up on the node containing the target value x_i. The time it takes a given dynamic BST algorithm to perform a sequence of accesses is equivalent to the total number of such operations performed during that sequence. Given any sequence of accesses on any set of elements, there is some minimum total number of operations required to perform those accesses. We would like to come close to this minimum.

While it is impossible to implement this "God's algorithm" without foreknowledge of exactly what the access sequence will be, we can define OPT(X) as the number of operations it would perform for an access sequence X, and we can say that an algorithm is dynamically optimal if, for any X, it performs X in time O(OPT(X)) (that is, it has a constant competitive ratio).[8]

There are several data structures conjectured to have this property, but none proven. It is an open problem whether there exists a dynamically optimal data structure in this model.

The splay tree is a form of binary search tree invented in 1985 by Daniel Sleator and Robert Tarjan on which the standard search tree operations run in ${\displaystyle O(\log(n))}$ amortized time.[10] It is conjectured to be dynamically optimal in the required sense. That is, a splay tree is believed to perform any sufficiently long access sequence X in time O(OPT(X)).[9]

The tango tree is a data structure proposed in 2004 by Erik Demaine and others which has been proven to perform any sufficiently-long access sequence X in time ${\displaystyle O(\log \log n\operatorname {OPT} (X))}$. While this is not dynamically optimal, the competitive ratio of ${\displaystyle \log \log n}$ is still very small for reasonable values of n.[8]

In 2013, John Iacono published a paper which uses the geometry of binary search trees to provide an algorithm which is dynamically optimal if any binary search tree algorithm is dynamically optimal.[11] Nodes are interpreted as points in two dimensions, and the optimal access sequence is the smallest arborally satisfied superset of those points. Unlike splay trees and tango trees, Iacono's data structure is not known to be implementable in constant time per access sequence step, so even if it is dynamically optimal, it could still be slower than other search tree data structures by a non-constant factor.

The interleave lower bound is an asymptotic lower bound on dynamic optimality.