Binary search tree#Optimal binary search trees

The algorithm of Bellman constructed from a given list of keys and a corresponding probability of search an optimal binary search tree. The algorithm is based on the set 1957 found by Richard Bellman on optimal average seek times in binary search trees and uses the method of dynamic programming.

Algorithm

Search keys that are ordered in a sequence. In addition, the search probability is given for each key. For each is the probability that, after a non-existent key used for, or for, searched for.

Here and chances are, the sum of all and one must give:

The minimum expected search time in an optimal binary search tree for the set of keys and the optimal search tree under which the minimum expected search time is achieved.

However, if there geometrically decreasing probabilities, then the search time to the associated very rare keys can not be logarithmic limited.

With the search time of a key search and the search cost for a key search, the number of visited nodes is called on a path from the root to the key nodes in a binary search tree. Thus, when a key has a depth of the tree, then its search costs.

To model the search time for non-existent keys, each leaf receives two children nodes and. When a leaf is reached in the search, then the node is not included in the binary search tree.

For a given search tree, the expected search time can be calculated:

The Bellman - algorithm calculates the expected search time at an optimum binary search tree recursively to the sequence of the search key. The specification of the algorithm is performed by matrix recurrences.

Initialization:

Recursion:

In each cell, the minimum search term is at an optimum search tree for the sub- sequence of the search key sequence, the sum of all the probabilities of the search key identified in the tree to the part-sequence. Thus, the minimum search time for the whole sequence in the cell is stored.

In the recursion every election for the selection of a root of the tree corresponds to the partial sequence. The generation of the root increases the depth of each node in this tree by 1 So the expected search time must be increased in this tree down.

Is defined as

And can be computed efficiently with a matrix recurrence.

Must be traced in backtracking to construct an optimal search tree with the minimum expected search time, the calculation of the optimum value. Alternatively, an additional auxiliary matrix can be used in an implementation of the algorithm, which is filled in the calculation of the optimal values ​​for each of the completed and evaluated according to calculation.

Complexity

The term of the calculation of the matrix for the values ​​is. The matrix contains entries and any entry elements must be optimized. So the runtime complexity of the algorithm and the storage requirement is.

The iteration over the recursion can be restricted further, so that the total running time of all iterations is. So then, the total duration of the thus modified algorithm.