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.

Step by step solution

01

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.

02

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.

03

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)$.

Unlock Step-by-Step Solutions & Ace Your Exams!

• Full Textbook Solutions

  Get detailed explanations and key concepts

• Unlimited Al creation

  Al flashcards, explanations, exams and more...

• Ads-free access

  To over 500 millions flashcards

• Money-back guarantee

  We refund you if you fail your exam.

Start your free trial

Over 30 million students worldwide already upgrade their learning with Vaia!