Skip to main content

Optimal Binary Search using Dynamic Programming

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

If the probabilities of searching for elements of a set are known from accumulated data from past searches, then Binary Search Tree (BST) should be such that the average number of comparisons in a search should be minimum.

eg. Lets the elements to be searched are A, B, C, D and probabilities of searching these items are 0.1, 0.2, 0.4 and 0.3 respectively.

Lets consider 2 out of 14 possible BST containing these keys.
Figure 1
Figure 2

Average number of comparison is calculated as sum of level*probability(key element) for each element of the tree.

Lets the level of tree start from 1.

Therefore, for figure 1 -
   
  • Average number of comparison = 1*0.1 +2*0.2 +3*0.4 +4*0.3  = 2.9                                             
For figure 2 -
  •    Average number of comparison= 2*0.1 +1*0.2 +2*0.4 +3*0.3 = 2.1

Since, both the examples are not optimal. So, how to find the Optimal Binary Search Tree.

In this example, we can find the optimal BST by generating all 14 BST with these keys. i.e. exhaustive search approach, which is not possible for larger value of keys. Because total number of BSTs with n keys is equal to nth Catalan number. So, the alternate method is to use the Dynamic Programming.

Notes for OBST using Dynamic Programming are attached below.

Page1

page2

page3

page4

page5

page6

page7

page8

page9

page10

page11

Labels:

Comments

Post a Comment

Popular posts from this blog

Knapsack Problem and Solution using Dynamic Programming

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible Given a knapsack of capacity m and number of items n of weight w1, w2, w3 ... , wn with profits p1, p2, p3..., pn. Let x1,x2,...,xn is an array that represents the items has been selected or not. If the item i is selected, then xi = 1 If the item i is not selected then x i = 0 In 0/1 knapsack, the item can be selected or completely rejected. The items are not allowed to be broken into smaller parts. The main objective is to place the items into the knapsack so that maximum profit is obtained or find the most valuable subset of items that fits into the knapsack. Constraints: The weight of the items chosen should not exceed the capacity of knapsack. Obj...
Post a Comment
Read more

Important points on Classes and Methods in Java as per Java Language Specification

Class Declarations: A class declaration specifies a new named reference type. There are two kinds of class declarations: normal class declarations and enum declarations. It is a compile-time error if a class has the same simple name as any of its enclosing classes or interfaces. Class Modifiers: A class declaration may include class modifiers. The access modifier public pertains only to top level classes and member classes, not to local classes or anonymous classes. The access modifiers protected and private pertain only to member classes within a directly enclosing class declaration. The modifier static pertains only to member classes, not to top level or local or anonymous classes. It is a compile-time error if the same keyword appears more than once as a modifier for a class declaration. abstract Classes: An abstract class is a class that is incomplete, or to be considered incomplete. It is a compile-time error if an attempt is made to create an instance o...
Post a Comment
Read more