“Optimal binary search tree”的意思、由来-开放百科全书

In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree,^[1] is a binary search tree which provides the smallest possible search time (or expected search time) for a given sequence of accesses (or access probabilities). Optimal BSTs are generally divided into two types: static and dynamic.

In the static optimality problem, the tree cannot be modified after it has been constructed. In this case, there exists some particular layout of the nodes of the tree which provides the smallest expected search time for the given access probabilities. Various algorithms exist to construct or approximate the statically optimal tree given the information on the access probabilities of the elements.

In the dynamic optimality problem, the tree can be modified at any time, typically by permitting tree rotations. The tree is considered to have a cursor starting at the root which it can move or use to perform modifications. In this case, there exists some minimal-cost sequence of these operations which causes the cursor to visit every node in the target access sequence in order. The splay tree is conjectured to have a constant competitive ratio compared to the dynamically optimal tree in all cases, though this has not yet been proven.

Static optimality

Definition

In the static optimality problem as defined by Knuth,^[2] we are given a set of {{mvar|n}} ordered elements and a set of

probabilities. We will denote the elements

through

and the probabilities

through

and

through

is the probability of a search being done for element

. For

is the probability of a search being done for an element between

and

is the probability of a search being done for an element strictly less than

, and

is the probability of a search being done for an element strictly greater than

. These

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

probabilities. As the number of possible trees on a set of {{mvar|n}} elements is

,^[2] which is exponential in {{mvar|n}}, brute-force search is not usually a feasible solution.

Knuth's dynamic programming algorithm

In 1971, Knuth published a relatively straightforward dynamic programming algorithm capable of constructing the statically optimal tree in only O(n²) time.^[2] Knuth's primary insight was that 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.

To see this, consider what Knuth calls the "weighted path length" of a tree. The weighted path length of a tree on n elements is the sum of the lengths of all

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, {{mvar|E_L}} be the weighted path length of its left subtree, and {{mvar|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:

This recurrence leads to a natural dynamic programming solution. Let

be the weighted path length of the statically optimal search tree for all values between {{mvar|a_i}} and {{mvar|a_j}}, let

be the total weight of that tree, and let

be the index of its root. The algorithm can be built using the following formulas:

Mehlhorn's approximation algorithm

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 that a much simpler algorithm could be used to closely approximate the statically optimal tree in only {{tmath|O(n)}} time.^[3] In this algorithm, the root of the tree is chosen so as to most closely balance the total weight (by probability) of the left and right subtrees. This 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

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

Hu–Tucker and Garsia–Wachs algorithms

In the special case that all of the

values are zero, the optimal tree can be found in time

. 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.^[4]

Dynamic optimality

Definition

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

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 can use the pointer to perform any of the following operations:

Our BST algorithm can 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 BST algorithm which performs all accesses using the fewest total operations.

This model defines the fastest possible tree for a given sequence of accesses, but calculating the optimal tree in this sense therefore requires foreknowledge of exactly what the access sequence will be. If we let OPT(X) be the number of operations performed by the strictly optimal tree for an access sequence X, we can say that a tree is dynamically optimal as long as, for any X, it performs X in time O(OPT(X)) (that is, it has a constant competitive ratio).^[5]

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.

Splay trees

The splay tree is a form of binary search tree invented in 1985 by Daniel Sleator and Robert Tarjan on which the standard searchtree operations run in

amortized time.^[7] 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)).^[6]

Tango trees

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

. While this is not dynamically optimal, the competitive ratio of

is still very small for reasonable values of n.^[5]

Other results

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.^[8] Nodes are interpreted as points in two dimensions, and the optimal access sequence is the smallest arborally satisfied superset of those points.

See also

Notes

1. ^{{cite book |first1=Jean-Paul |last1=Tremblay |first2=Grant A. |last2=Cheston |title=Data Structures and Software Development in an object-oriented domain |publisher=Eiffel Edition/Prentice Hall |year=2001 |isbn=978-0-13-787946-5}}
2. ^¹²{{Citation |first1=Donald E. |last1=Knuth |title=Optimum binary search trees |journal=Acta Informatica |volume=1 |issue=1 |pages=14–25 |year=1971 |doi=10.1007/BF00264289 }}
3. ^¹{{Citation |first1=Kurt |last1=Mehlhorn |title=Nearly optimal binary search trees |journal=Acta Informatica |volume=5 |issue=4 |pages=287–295 |year=1975 |doi=10.1007/BF00264563 }}
4. ^{{citation | last = Knuth | first = Donald E. | author-link = Donald Knuth | contribution = Algorithm G (Garsia–Wachs algorithm for optimum binary trees) | edition = 2nd | pages = 451–453 | publisher = Addison–Wesley | title = The Art of Computer Programming, Vol. 3: Sorting and Searching | year = 1998| title-link = The Art of Computer Programming }}. See also History and bibliography, pp. 453–454.
5. ^¹²³{{Citation |first1=Erik D. |last1=Demaine |first2=Dion |last2=Harmon |first3=John |last3=Iacono |first4=Mihai |last4=Patrascu |title=Dynamic optimality - almost |booktitle=Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science |isbn=978-0-7695-2228-9 |pages=484–490 |year=2004 |doi=10.1109/FOCS.2004.23 |chapter=Dynamic Optimality — Almost |citeseerx=10.1.1.99.4964 }}
6. ^¹{{Citation |first1=Daniel |last1=Sleator |first2=Robert |last2=Tarjan |title=Self-adjusting binary search trees |journal=Journal of the ACM |volume=32 |issue=3 |pages=652–686 |year=1985 |doi=10.1145/3828.3835 }}
7. ^{{cite book|last1=Cormen|first1=Thomas H.|last2=Leiserson|first2=Charles E.|last3=Rivest|first3=Ronald|last4=Stein|first4=Clifford|title=Introduction to algorithms|date=2009|publisher=The MIT Press|isbn=978-0-262-03384-8|page=503|edition=Third|url=http://ressources.unisciel.fr/algoprog/s00aaroot/aa00module1/res/%5BCormen-AL2011%5DIntroduction_To_Algorithms-A3.pdf|accessdate=31 October 2017}}
8. ^{{cite arxiv |first1=John |last1=Iacono |title=In pursuit of the dynamic optimality conjecture |eprint=1306.0207 |year=2013 |mode=cs2 |class=cs.DS }}