A binary search tree is one of the most important data structures in computer science. One of its principal applications is to implement a dictionary, a set of elements with the operations of searching, insertion, and deletion.

**Optimal
Binary Search Trees**

A binary search tree is one
of the most important data structures in computer science. One of its principal
applications is to implement a dictionary, a set of elements with the
operations of searching, insertion, and deletion. If probabilities

of searching for elements of
a set are known—e.g., from accumulated data about past searches—it is natural
to pose a question about an optimal binary search tree for which the average
number of comparisons in a search is the smallest possible. For simplicity, we
limit our discussion to minimizing the average number of comparisons in a
successful search. The method can be extended to include unsuccessful searches
as well.

As an example, consider four
keys ** A, B**,

comparisons in a successful
search in the first of these trees is 0** .**1

Neither of these two trees
is, in fact, optimal. (Can you tell which binary tree is optimal?)

For our tiny example, we
could find the optimal tree by generating all 14 binary search trees with these
keys. As a general algorithm, this exhaustive-search approach is unrealistic:
the total number of binary search trees with ** n** keys is equal to the

which grows to infinity as
fast as 4^{n}*/n*^{1}^{.}^{5} (see Problem 7 in this
section’s exercises). So let *a*_{1}*, . . . , a***_{n}** be distinct keys ordered from the smallest to
the largest and let

contains keys *a*_{k}_{+}_{1}*, . . . , a***_{j}** also optimally arranged. (Note how we are
taking advantage of the principle of optimality here.)

If we count tree levels
starting with 1 to make the comparison numbers equal the keys’ levels, the
following recurrence relation is obtained:

We assume in formula (8.8)
that ** C(i, i** − 1

** C(i, i) **=

as it should be for a
one-node binary search tree containing *a*_{i}*.*

The two-dimensional table in
Figure 8.9 shows the values needed for comput-ing ** C(i, j )** by formula (8.8): they are in row

The algorithm we just
sketched computes ** C(**1

**EXAMPLE
**Let us
illustrate the algorithm by applying it to the four-key set we** **used at the beginning of this
section:

Thus, out of two possible
binary trees containing the first two keys, ** A** and

We will ask you to finish the
computations in the exercises. You should arrive at the following final tables:

Thus, the average number of
key comparisons in the optimal tree is equal to 1.7. Since ** R(**1

Here is pseudocode of the
dynamic programming algorithm.

**ALGORITHM** *OptimalBST**(P** *[1** ..n**]

//Finds an optimal binary
search tree by dynamic programming

//Input: An array ** P** [1

** C**[

** C**[

**for ***d*** **←** **1** to ***n*** **−** **1** do **//diagonal count** for ***i*** **←** **1** to ***n*** **−** ***d*** do**

** j **←

**for ***k*** **←** ***i*** to ***j*** do**

**if **** C**[

*minval *←* *** C**[

** sum **←

**return **** C**[1

The algorithm’s space
efficiency is clearly quadratic; the time efficiency of this version of the
algorithm is cubic (why?). A more careful analysis shows that entries in the
root table are always nondecreasing along each row and column. This limits
values for ** R(i, j )** to the range

**Exercises 8.3**

**
**Finish the computations started in the section’s example of constructing
an optimal binary search tree.

**
****a. **Why is the time efficiency of algorithm** ***OptimalBST*** **cubic?

**b. **Why is the space efficiency of algorithm** ***OptimalBST*** **quadratic?

**
**Write pseudocode for a linear-time algorithm that generates the
optimal binary search tree from the root table.

**4.** Devise a way to compute the
sums _{s}_{=i} *p*_{s}** ,** which are used in the dynamic programming
algorithm for constructing an optimal binary search tree, in constant time (per
sum).

**
**True or false: The root of an optimal binary search tree always
contains the key with the highest search probability?

**
**How would you construct an optimal binary search tree for a set of ** n** keys if all the keys are equally likely to be
searched for? What will be the average number of comparisons in a successful
search in such a tree if

**
****a. **Show that the number of
distinct binary search trees** ***b(n)*** **that can be** **constructed for a set of ** n** orderable keys satisfies the recurrence
relation

**
**It is known that the solution to this recurrence is given by the
Catalan numbers. Verify this assertion for ** n** = 1

**
**Find the order of growth of ** b(n).** What implication does the answer to this
question have for the exhaustive-search algorithm for constructing an optimal
binary search tree?

**
**Design a * (n*^{2}** )** algorithm for finding an optimal binary search
tree.

**
**Generalize the optimal binary search algorithm by taking into
account unsuc-cessful searches.

**
**Write pseudocode of a memory function for the optimal binary search
tree problem. You may limit your function to finding the smallest number of key
comparisons in a successful search.

** Matrix chain multiplication **Consider the problem of
minimizing the total

**
**Give an example of three matrices for which the number of
multiplications in *(A*_{1} ^{.}*A*_{2}*)*^{.}*A*_{3} and *A*_{1} ^{.}*(A*_{2} ^{.}*A*_{3}** )** differ at least by a factor of 1000.

**
**How many different ways are there to compute the product of ** n** matrices?

**
**Design a dynamic programming algorithm for finding an optimal order
of multiplying ** n** matrices.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Dynamic Programming : Optimal Binary Search Trees |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.