Optimal Cost Binary Search Trees
A Binary Search Tree (BST) is a tree where the key values are stored in the internal nodes. The external nodes are null nodes. The keys are ordered lexicographically, i.e. for each internal node all the keys in the left sub-tree are less than the keys in the node, and all the keys in the right sub-tree are greater.
When we know the frequency of searching each one of the keys, it is quite easy to compute the expected cost of accessing each node in the tree. An optimal binary search tree is a BST, which has minimal expected cost of locating each node
Search time of an element in a BST is O(n), whereas in a Balanced-BST search time is O(log n). Again the search time can be improved in Optimal Cost Binary Search Tree, placing the most frequently used data in the root and closer to the root element, while placing the least frequently used data near leaves and in leaves.
Here, the Optimal Binary Search Tree Algorithm is presented. First, we build a BST from a set of provided n number of distinct keys < k1, k2, k3, ... kn >. Here we assume, the probability of accessing a key Ki is pi. Some dummy keys (d0, d1, d2, ... dn) are added as some searches may be performed for the values which are not present in the Key set K. We assume, for each dummy key di probability of access is qi.
Optimal-Binary-Search-Tree(p, q, n)
e[1…n + 1, 0…n],
w[1…n + 1, 0…n],
root[1…n + 1, 0…n]
for i = 1 to n + 1 do
e[i, i - 1] := qi - 1
w[i, i - 1] := qi - 1
for l = 1 to n do
for i = 1 to n – l + 1 do j = i + l – 1 e[i, j] := ∞ w[i, i] := w[i, i -1] + pj + qj for r = i to j do
t := e[i, r - 1] + e[r + 1, j] + w[i, j]
if t < e[i, j]
e[i, j] := t
root[i, j] := r
return e and root
Analysis
The algorithm requires O (n3) time, since three nested for loops are used. Each of these loops takes on at most n values.
Example
For the following set of information, design the matrix required to construct optimal Binary Search Tree, Also draw optimal search tree and Find the cost of tree.
To get an optimal solution, the following tables are generated.
w [i ,j ] = w [ i , j-1 ] + pj + qj
W Matrix
e [i, j] = qi – 1, if j = i – 1
min { e [ i, r-1 ] + e[ r+1,j ] +w[ i ,j ] } if i<=j where i<=r<=j
r=1, e[1,1] = e[1,0]+e[2,1]+w[1,1] = 0.07+0.11+0.30==0.48
e[1,2]= min { e[1,0]+e[2,2]+w[1,2] =0.94 r=1
e[1,1]+e[3,2]+w[1,2] = 1.04 r =2
r=1,2
1 2 3 4 5 6 2.8 2.07 1.32 0.86 0.50 0.10
1.8 1.21 0.62 0.28 0.05 1.32 0.76 0.27 0.05
0.94 0.42 0.05 0.48 0.11
0.07
OBST Tree
[ Ti,m-1, Tm+1,j ] , i= 1, j= 5
------------------------------------------------------------------- 1
K2
0.10 m = 2, i=1, j=5
0.12 0.2--------------------- 2 K1 K5
m=5 , i=3, j=5
0.08 -------------- 3
d0 d1 K4 d5
m= 4, i=3, j=4
0.070.110.10
- ---------------------- 4 K3 d4
0.07 0.05
d2 d3
0.05 0.05
����=1
-------------------------------5 ����=0 ∗ ����������(����)
Cost of OBST = ∑ (����) ∗ ����������(����) + ∑ (����) ={ (0.10)*1+(0.12)*2+(0.2)*2+(0.08)*3+(0.07)*4}+ {(0.07+0.11+0.10)*3+0.05*4+(0.05+0.05)*5 =
Example 2:
Draw OBST for the following .Also generate the matrices for tree construction n=5
To get an optimal solution, the following tables are generated.
w [i ,j ] = w [ i , j-1 ] + pj + qj
W Matrix
e [i, j] = qi – 1, if j = i – 1
min { e [ i, r-1 ] + e[ r+1,j ] +w[ i ,j ] } if i<=j where i<=r<=j
E[1,2] = min { 0.05+0.35+0.33=0.73 r=1
0.38+0.05+0.33= 0.76 r=2
E[2,3] = min{ 0.10+0.44+0.43 = 0.97 r=2
0.35+0.11+0.43= 0.89 r=3
E[3,4] = min 0.05+0.62+0.58=1.25 r=3
0.44+0.10+0.58= 1.12 r=4
E[4,5] = min 0.11+0.38+0.55=1.04 r=4
0.62+0.04+0.55=1.21 r=5
E[1,3]= min 0.05+0.89+0.56=1.50 r=1
0.38+0.44+0.56=1.38 r=2
0.73 + 0.11+0.56 = 1.40 r=3
e[2,4]= min 0.10+1.12+0.73=1.95 r=2
0.35+0.62+0.73 =1.70 r=3
0.89+0.10+0.73 =1.72 r=4
E[3,5]= min 0.05+1.04+0.72 =1.81 r=3
0.44+0.38+0.72=1.54 r=4
1.12+0.04+0.72=1.88 r=5
E[1,4]= min 0.05+1.70 + 0.86 =2.61 r=1
0.38+1.12+0.86=2.36 r=2
0.73 +0.62+0.86= 2.21 r=3
1.38+0.10+0.86 = 2.34 r=4
E[2,5]=min 0.10+1.54+0.87 =2.51 r=2
0.35+1.04+0.87=2.26 r=3
0.89+0.38+0.87=2.14 r=4
1.70 +0.04+0.87 =2.61 r=5
E[1,5]= min 0.05+2.14 +1.0=3.19 r=1
0.38+1.54 +1.0= 2.92 r=2
0.73 +1.04+1.0= 2.77 r=3
1.38+0.38+1.0=2.76 r=4
2.21+0.04+1.0=3.25 r=5
OBST Tree
K4
[ Ti,m-1, Tm+1,j ] , i= 1, j= ------------------------------------------------------------------1
T1,3=2 T5,5
K2 K5
-------------------------------------------------------------------------------------------------------2
----------------------------------------------------------------- ------- ----------------3 K1 K3 D5
D4
0.08
0
d0 d1 D2 D3
0.05
����=1
����=0 ∗ ����������(����)
Cost of OBST = ∑ (����) ∗ ����������(����) + ∑ (����)
Example3:
Draw optimal binary search tree
To get an optimal solution, the following tables are generated.
w [i ,j ] = w [ i , j-1 ] + pj + qj
W Matrix
e [i, j] = qi – 1, if j = i – 1
min { e [ i, r-1 ] + e[ r+1,j ] +w[ i ,j ] } if i<=j where i<=r<=j
Example 4:
Draw optimal binary search tree
Comments
Post a Comment