Question

Optimal binary search trees. Suppose we know the frequency with which keywords occur in programs of a certain language, for instance:

$\begin{array}{l}\mathbf{begin}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{5}\mathbf{\%}\\ \mathbf{do}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{40}\mathbf{\%}\\ \mathbf{else}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{8}\mathbf{\%}\\ \mathbf{end}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{4}\mathbf{\%}\end{array}$

$\begin{array}{l}\mathbf{if}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{10}\mathbf{\%}\\ \mathbf{then}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{10}\mathbf{\%}\\ \mathbf{while}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{}\mathbf{23}\mathbf{\%}\end{array}$

We want to organize them in a binary search tree, so that the keyword in the root is alphabetically bigger than all the keywords in the left subtree and smaller than all the keywords in the right subtree (and this holds for all nodes). Figure 6.12 has a nicely-balanced example on the left. In this case, when a keyword is being looked up, the number of comparisons needed is at most three: for instance, in finding “while”, only the three nodes “end”, “then”, and “while” get examined. But since we know the frequency 196 Algorithms with which keywords are accessed, we can use an even more fine-tuned cost function, the average number of comparisons to look up a word. For the search tree on the left, it is

$\mathbf{cost}\mathbf{=}\mathbf{1}\left(0.04\right)\mathbf{+}\mathbf{2}\left(0.40+0.10\right)\mathbf{+}\mathbf{3}\left(0.05+0.08+0.10+0.23\right)\mathbf{=}\mathbf{2}\mathbf{.}\mathbf{42}$

By this measure, the best search tree is the one on the right, which has a cost of Give an efficient algorithm for the following task. Input: n words (in sorted order); frequencies of these words: ${\mathit{p}}_{\mathbf{1}}\mathbf{,}{\mathit{p}}_{\mathbf{2}}\mathbf{,}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{,}{\mathit{p}}_{\mathbf{n}}\mathbf{.}$

Output: The binary search tree of lowest cost (defined above as the expected number of comparisons in looking up a word).

Figure 6.12 Two binary search trees for the keywords of a programming language.

Short answer

To obtain minimum cost binary search tree, we need to calculate the cost of each possible binary search tree which can be obtain from main tree. This problem can be easily solve using dynamic programming paradigm because we have subproblem as each subtree at root node will be a problem itself to calculate minimum cost of subtree.

Step-by-step solution

Binary Search Tree (BST) and Dynamic programming approach.

A binary search tree has following properties:

• The left subtree of a node contains nodes with keys having lesser value
• The right subtree of a node contains node with keys having greater value.
• The left and the right subtree must also be a binary search tree.

In dynamic programming there are all possibilities and more time as compared to greedy programming. and the Dynamic programming approach always gives the accurate or correct answer. In dynamic programming have to compute only distinct function call because as soon as compute and store in one data structure so that after this reuse afterward if it is needed.

Defining Recurrence Relation

Here we need to define two functions:

• $\mathrm{W}\left(\mathrm{i},\mathrm{j}\right):$It is the sum of all probabilities of all the nodes within that tree or subtree.
• $E\left(i,j\right):$It will pick the ’r’ root node that will create further two subtrees.

Our recurrence relations are:

$\begin{array}{l}E\left(i,j\right)=min\left\{E\left(i,r-1\right)+w\left(i,j\right)\right\};fori\le r\le j\\ \\ w\left(i,j\right)=W\left(i,j-1\right)+p\end{array}$

In $E\left(i,j\right):$, Left Subtree is from$‘i’to\left(r-1\right)$ and Right Subtree is from $\left(r+1\right)to‘j’.$

$W\left(i,j\right):$will merge these two subtrees: Left Subtree and Right subtree.

Algorithm

$p\left[1\dots .n\right]i$s array of words frequencies of n

$\begin{array}{l}for\left(s=1ton\right)\\ \begin{array}{l}\\ for\left(i=0ton-s\right)\end{array}\\ \begin{array}{l}\\ j=i+s\end{array}\\ \begin{array}{l}\\ if\left(i=j\right)\end{array}\end{array}$

data-custom-editor="chemistry" $\begin{array}{l}T\left(i,j\right)=p\left[i\right]\\ \begin{array}{l}\\ for\left(k=itoj+1\right)\end{array}\\ \begin{array}{l}\\ T\left(i,j\right)=T\left(i,j\right)+p\left[k\right]\end{array}\\ \begin{array}{l}\\ returnT\left(0,n-1\right)\end{array}\end{array}$

It will return minimum cost binary tree.

The runtime of above algorithm will be$\mathrm{O}\left({\mathrm{n}}^2\right)$ as two nested loops are running for n and $n-1$times which give combined $\mathrm{O}\left({\mathrm{n}}^2\right)$.