Optimal binary search tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a> which provides the smallest possible search time (or <a href="/facts/Expected_value/1XV0JKL8">expected search time</a>) 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 <a href="/facts/Tree_rotation/R3SlGyI0">tree rotations</a>. 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 <a href="/facts/Splay_tree/DHKCdoST">splay tree</a> is conjectured to have a constant <a href="/facts/Competitive_ratio/ocEpTvXG">competitive ratio</a> compared to the dynamically optimal tree in all cases, though this has not yet been proven.

Optimal binary search tree open-in-new

Optimal binary search tree