Optimal Binary
Search Tree
Learning Objectives
At the end of this session, you will be able to:
• Define the optimal binary search tree
• Explain the weight balanced binary tree
• Explain the calculation of optimal binary search tree
Optimal Binary Search Tree(OBST)
An optimal binary search tree,
sometimes called a weight-
balanced binary tree, is a
binary search tree which
provides the smallest possible
search time for a given
sequence of accesses.
Optimal Binary Search Tree(OBST)
The frequency and key-value determine
the overall cost of searching a node. The
cost of searching is a very important
factor in various applications. The
overall cost of searching a node should
be less. The time required to search a
node in BST is more than the balanced
binary search tree as a balanced binary
search tree contains a lesser number of
levels than the BST. So how do we
organize a binary search tree so as to
minimize the number of nodes visited in
all searches, given that we know how
often each key occurs. Optimal binary
search tree can reduce the cost of
search in a binary search tree.
OBST
• Keys with Frequency: Keys 10 20 30
• Cost based on freq. Frequency 3 2 5
With 3 keys we have 5 BST
Cost of 1st BST
cost=1x3+2x2+3x5
=3+4+15
=22
OBST
• Keys with Frequency: Keys 10 20 30
• Cost based on freq. Frequency 3 2 5
With 3 keys we have 5 BST
Cost of 2nd BST
cost=1x3+2x5+3x2
=19
OBST
• Keys with Frequency: Keys 10 20 30
• Cost based on freq. Frequency 3 2 5
With 3 keys we have 5 BST
Cost of 3rd BST
cost=1x2+2x3+2x5
=18
OBST
• Keys with Frequency: Keys 10 20 30
• Cost based on freq. Frequency 3 2 5
With 3 keys we have 5 BST
Cost of 4th BST
cost=1x5+2x3+3x2
=17
On the basis of frequencies and
arrangement of nodes
This BST gives us minimum cost
OBST
• Keys with Frequency: Keys 10 20 30
• Cost based on freq. Frequency 3 2 5
With 3 keys we have 5 BST
Cost of 5th BST
cost=1x5+2x2+3x3
=18
The above trees have different frequencies. The
tree with the lowest frequency would be
considered the optimal binary search tree. The
tree with the frequency 17 is the lowest, so it
would be considered as the optimal binary
search tree.
Optimal Binary Search Tree
For example we take a problem and solve
it using dynamic programming method
First, we will calculate the values
• where j-i is equal to zero.
• When i = 0, j=0, then j-i = 0
• When i = 1, j=1, then j-i = 0
• When i = 2, j=2, then j-i = 0
• When i = 3, j=3, then j-i = 0
• When i = 4, j=4, then j-i = 0
• Therefore, c[0, 0] = 0, c[1 , 1] = 0, c[2,2]
= 0, c[3,3] = 0, c[4,4] = 0
Optimal Binary Search Tree
Now we will calculate the values where j-i equal to 1.
When j=1, i=0 then j-i = 1
When j=2, i=1 then j-i = 1
When j=3, i=2 then j-i = 1
When j=4, i=3 then j-i = 1
Now to calculate the cost, we will consider only the jth value.
The cost of c[0,1] is 4 (The key is 10, and the cost corresponding to key 10 is
4).
The cost of c[1,2] is 2 (The key is 20, and the cost corresponding to key 20 is
2).
The cost of c[2,3] is 6 (The key is 30, and the cost corresponding to key 30 is
6)
Optimal Binary Search Tree
Now we will calculate the values where j-i =
2
When j=2, i=0 then j-i = 2
When j=3, i=1 then j-i = 2
When j=4, i=2 then j-i = 2
In this case, we will consider two keys.
When i=0 and j=2, then keys 10 and 20.
There are two possible trees that can be
made out from these two keys shown
below:
Optimal Binary Search Tree
In the first binary tree, cost would be: 4*1 + 2*2 = 8
In the second binary tree, cost would be: 4*2 + 2*1 =
10
The minimum cost is 8; therefore, c[0,2] = 8
Optimal Binary Search Tree
When i=1 and j=3, then keys 20 and 30.
There are two possible trees that can be made
out from these two keys shown below:
In the first binary tree, cost would be: 1*2 + 2*6
= 14
In the second binary tree,
cost would be: 1*6 + 2*2 = 10
The minimum cost is 10; therefore, c[1,3] = 10
In the second binary
When i=2 and j=4, we will consider the keys at 3 tree,
and 4, i.e., 30 and 40.
cost would be: 1*3 +
There are two possible trees that can be made 2*6 = 15
out from these two keys shown as below:
The minimum cost is 12,
In the first binary tree, cost would be: 1*6 + 2*3 therefore, c[2,4] = 12
= 12
Optimal Binary Search Tree
Now we will calculate the values when j-i =
3
• When j=3, i=0 then j-i = 3
• When j=4, i=1 then j-i = 3
• When i=0, j=3 then we will consider three
keys, i.e., 10, 20, and 30.
• The following are the trees that can be
made if 10 is considered as a root node.
In the above tree, 10 is the root node, 20 is
the right child of node 10, and 30 is the
right child of node 20.
Cost would be: 1*4 + 2*2 + 3*6 = 26
Optimal Binary Search Tree
In the above tree, 10 is the In the above tree, 20 is the
root node, 30 is the right root node, 30 is the right
child of node 10, and 20 is child of node 20, and 10 is
the left child of node 20. the left child of node 20.
Cost would be: 1*4 + 2*6 + Cost would be: 1*2 + 4*2 +
3*2 = 22 6*2 = 22
Optimal Binary Search Tree
In the above tree, 30 is the root node, 20 is
the left child of node 30, and 10 is the left
child of node 20. Cost would be: 1*6 + 2*2 +
3*4 = 22
In the above tree, 30 is the root node, 10 is
the left child of node 30 and 20 is the right
child of node 10.
Cost would be: 1*6 + 2*4 + 3*2 = 20
Therefore, the minimum cost is 20 which is
the 3rd root. So, c[0,3] is equal to 20.
Optimal Binary Search Tree
When i=1 and j=4 then we will
consider the keys 20, 30, 40
c[1,4] = min{ c[1,1] + c[2,4], c[1,2] +
c[3,4], c[1,3] + c[4,4] } + 11
= min{0+12, 2+3, 10+0}+ 11
= min{12, 5, 10} + 11
The minimum value is 5; therefore,
c[1,4] = 5+11 = 16
Optimal Binary Search Tree
Now we will calculate the values
when j-i = 4When j=4 and i=0 then j-i
=4
In this case, we will consider four
keys, i.e., 10, 20, 30 and 40. The
frequencies of 10, 20, 30 and 40 are
4, 2, 6 and 3 respectively.
w[0, 4] = 4 + 2 + 6 + 3 = 15
Optimal Binary Search Tree
If we consider 10 as the root node
then
C[0, 4] = min {c[0,0] + c[1,4]}+
w[0,4]
= min {0 + 16} + 15= 31
If we consider 20 as the root node
then
C[0,4] = min{c[0,1] + c[2,4]} +
w[0,4]
= min{4 + 12} + 15
= 16 + 15 = 31
Optimal Binary Search Tree
If we consider 30 as the root node
then,
C[0,4] = min{c[0,2] + c[3,4]}
+w[0,4]
= min {8 + 3} + 15
= 26
If we consider 40 as the root node
then,
C[0,4] = min{c[0,3] + c[4,4]} +
w[0,4]
= min{20 + 0} + 15
= 35
Optimal Binary Search Tree
The optimal binary tree can be created
as:
Optimal Binary Search Tree
General formula for
calculating the
minimum cost is:
C[i,j] = min{c[i, k-
1] + c[k,j]} + w(i,j)
Summary
In this session, we have discussed
about:
• Optimal binary search tree
• Weight balanced binary tree
• Calculation of optimal binary search tree
MCQ
Q.1. Find optimal binary search tree cost for given
keys with frequency
Keys 10 20 30
Frequency 3 2 5
a)22
b)19
c)17
d)15
Answer: c
MCQ
Q.2. How many optimal binary search tree can be created for given keys
with frequency
Keys 10 20 30
Frequency 3 2 5
a)5
b)1
c)3
d)9
Answer: b
