Optimal Binary Search Trees

A binary search tree is a special kind of binary tree in which the nodes are arranged in such a way that the smaller values fall in the left subnode, and the larger values fall in the right subnode.

So now, what is an optimal binary search tree, and how are they different than normal binary search trees. The cost of searching a node in a tree plays a very big role, and it is decided by the frequency and a key value of the node. Often, our goal is to reduce the cost of searching, and that is done through an optimal binary tree. 

For our better understanding, we can take the following example, 

let us assume the binary tree has the following keys:

11, 22, 33, 44, 55, 66, 77. 

So the binary tree will be arranged in the following manner:

As we can see the root node is 44, and the smaller values with respect to the root value, are placed in the left subtree, and the larger values with respect to the root value are placed in the right subtree. 

Now moving on, we will check how many binary search trees can be made by using the keys we have taken in our example:

The formula for it is

2n Cn / n+1 

Therefore, the total number of binary search trees that can be created with the keys mentioned is 5. 

Now to calculate the cost for the operation will depend on how many comparisons it needs to make, so we will find that by the following method:

As we can see in the tree mentioned above, we will need to make 3 comparisons, so the average number of comparisons will be:

1+2+3/3 = 2. 

Similarly, 

We will find the comparisons for various other forms of BST using the same keys. 

After having done the comparisons we see that the tree mentioned below has the least number of comparisons, and hence the least cost, and qualifies as a balanced binary search tree, or the optimal binary search tree. 

Dynamic method

Let us understand the same problem using the dynamic approach.

We can consider the table mentioned below with the frequencies and the keys.

We will then go on to form a matrix with i and j, 

Let us start by calculating the values for when j-i =0.

When j-i is 0,

i=0, j=0

i=1, j=1

i=2, j=2

i=3, j=3

i=4, j=4 

Hence, c[0,0] = 0, and same for c[1,1], c[2,2], c[3,3], c[4,4]. 

Then, we calculate for when j-i=1,

When j-i=1,

i=0, j=1

i=1, j=2

i=2, j=3

i=3, j=4

Hence, c[0,1] = 4, c[1,2] = 2, c[2,3]= 6, c[3,4]=3. 

 Then, we calculate for when j-i=,

When j-i=2,

i=0, j=2

i=1, j=3

i=2, j=4

Hence, c[0,2] = 8. 

Here, only two binary trees will be possible out of which cost of [0,2] is the smallest one, so we choose it. 

Following the same method, we keep on testing for different values of j-i, and find the minimum cost in each case. 

The general formula for finding the minimal cost is:

C[i,j] = min{c[i, k-1] + c[k,j]} + w(i,j)

Reference

Optimal Binary Search Trees