Binary search trees with 5 keys (Actual key starts at index 1 and dummy key starts at index 0) Thus, a recursive formula for forming the OBST is stated below : e[i, j] gives the expected cost in the optimal binary search tree. The algorithm for optimal binary search tree is specified below : It is very simple to derive the complexity of this approach from the above algorithm. It uses three nested loops. Statements in the innermost loop run in Q(1) time. The running time of the algorithm is computed as Thus, the OBST algorithm runs in cubic time Problem: Let p (1 : 3) = (0.5, 0.1, 0.05) q(0 : 3) = (0.15, 0.1, 0.05, 0.05) Compute and construct OBST for above values using Dynamic approach. Solution: Here, given that
Recursive formula to solve OBST problem is Where, Initially,
Now, we will compute e[i, j] Initially,
e[1, 0] = q0 = 0.15 (∵ j = i – 1) e[2, 1] = q1 = 0.1 (∵ j = i – 1) e[3, 2] = q2 = 0.05 (∵ j = i – 1) e[4, 3] = q3 = 0.05 (∵ j = i – 1)
e[1, 1] = min { e[1, 0] + e[2, 1] + w(1, 1) } = min { 0.15 + 0.1 + 0.75 } = 1.0 e[2, 2] = min { e[2, 1] + e[3, 2] + w(2, 2) } = min { 0.1 + 0.05 + 0.25 } = 0.4 e[3, 3] = min { e[3, 2] + e[4, 3] + w(3, 3) } = min { 0.05 + 0.05 + 0.15 } = 0.25
e[1, 3] is minimum for r = 1, so r[1, 3] = 1 e[2, 3] is minimum for r = 2, so r[2, 3] = 2 e[1, 2] is minimum for r = 1, so r[1, 2] = 1 e[3, 3] is minimum for r = 3, so r[3, 3] = 3 e[2, 2] is minimum for r = 2, so r[2, 2] = 2 e[1, 1] is minimum for r = 1, so r[1, 1] = 1
Let us now construct OBST for given data. r[1, 3] = 1, so k1 will be at the root. k2….3 are on right side of k1 r[2, 3] = 2, So k2 will be the root of this sub tree. k3 will be on the right of k2. Thus, finally, we get.
Additional Reading: [Wiki] |