Optimal Binary Search using Dynamic Programming

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

If the probabilities of searching for elements of a set are known from accumulated data from past searches, then Binary Search Tree (BST) should be such that the average number of comparisons in a search should be minimum.

eg. Lets the elements to be searched are A, B, C, D and probabilities of searching these items are 0.1, 0.2, 0.4 and 0.3 respectively.

Lets consider 2 out of 14 possible BST containing these keys.

Figure 1

Figure 2

Average number of comparison is calculated as sum of level*probability(key element) for each element of the tree.

Lets the level of tree start from 1.

Therefore, for figure 1 -

Average number of comparison = 1*0.1 +2*0.2 +3*0.4 +4*0.3 = 2.9

For figure 2 -

Average number of comparison= 2*0.1 +1*0.2 +2*0.4 +3*0.3 = 2.1

Since, both the examples are not optimal. So, how to find the Optimal Binary Search Tree.

In this example, we can find the optimal BST by generating all 14 BST with these keys. i.e. exhaustive search approach, which is not possible for larger value of keys. Because total number of BSTs with n keys is equal to nth Catalan number. So, the alternate method is to use the Dynamic Programming.

Notes for OBST using Dynamic Programming are attached below.