Optimal Binary Search Tree

The shape of binary search trees has a significant impact on their worst$-$case

execution time. We have $n$ keys a$1,..,$ an in order, ai $$ ai$+1,$ that we want to store in a

binary search tree. It is given that queries for the keys occur with frequency fi such

that if $f1$ is high, then it pays to store it higher in the tree. If key ai is stored at height

hi$,$ then the average time

${\displaystyle \underset{i=1}{\overset{n}{}}}{f}_i*h_i$

The tree that results can be quite unbalanced. Therefore, we demand that the

resulting tree is an AVL tree, not just any binary search tree. The cost function is the

same as before, but we want to find the AVL tree that minimizes the sum.

Modify the OptCost function by requiring that the tree is an AVL tree of a specific

height. Follow the schema for solving dynamic optimization problems that were

given in homework $4.$

Here, it can be assumed that

$F(j,k)={\displaystyle \underset{i=j}{\overset{k}{}}}{f}_j$

has already been calculated.