Article Preview
Top2. Non-Serial Polyadic Dynamic Programming Algorithm For Constructing A Statically Optimal Binary Search Tree
Ordinarily, a binary search tree contains records that are retrieved according to the values of the keys. Our goal is to organize the keys in a binary search tree so that the average time it takes to locate a key is minimized. A tree that is organized in this fashion is called optimal. A tree in which all the keys have an equal probability of being the search key is said to be balanced if the difference between the height of left and right sub-trees is kept to a minimum e.g. 1 or 2. However, we are concerned with the case where the keys do not have the same probability.
The number of comparisons done by the searching procedure to locate a key is called the search time. We will determine a tree for which the average search time is minimal. Let Key1, Key2… Keyn be the n keys in order, and let Pi be the probability that Keyi is the search key. If Ci is the number of comparisons needed to find Keyi in a given tree, the average search time for that tree is. Once the tree is constructed it cannot be modified hence the term statically optimal binary search tree.
Average Search Time = ∑ (Ci.Pi) where 1 ≤ i ≤ n (a)
This value is to be minimized. We can generalize this for i ≤ k ≤ j instead of only for 1 ≤ i ≤ n.
The Dynamic programming algorithm for the solution of this problem proceeds as follows. Let Ck be the number of comparisons needed to locate Keyk in the tree. We will call such a tree optimal for those keys and denote the optimal value by A[i][j]. Because it takes one comparison to locate a key in a tree which contains a single key hence; A [i][i] = Pi.