#encoding: utf-8 =begin author: xu jin date: Nov 11, 2012 Optimal Binary Search Tree to find by using EditDistance algorithm refer to <<introduction to algorithms>> example output: "k2 is the root of the tree." "k1 is the left child of k2." "d0 is the left child of k1." "d1 is the right child of k1." "k5 is the right child of k2." "k4 is the left child of k5." "k3 is the left child of k4." "d2 is the left child of k3." "d3 is the right child of k3." "d4 is the right child of k4." "d5 is the right child of k5." The expected cost is 2.75.  =end INFINTIY = 1 / 0.0 a = ['', 'k1', 'k2', 'k3', 'k4', 'k5'] p = [0, 0.15, 0.10, 0.05, 0.10, 0.20] q = [0.05, 0.10, 0.05, 0.05, 0.05 ,0.10] e = Array.new(a.size + 1){Array.new(a.size + 1)} root = Array.new(a.size + 1){Array.new(a.size + 1)} def optimalBST(p, q, n, e, root)   w = Array.new(p.size + 1){Array.new(p.size + 1)}   for i in (1..n + 1)     e[i][i - 1] = q[i - 1]     w[i][i - 1] = q[i - 1]   end   for l in (1..n)     for i in (1..n - l + 1)       j = i + l -1       e[i][j] = 1 / 0.0       w[i][j] = w[i][j - 1] + p[j] + q[j]       for r in (i..j)         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         end       end     end   end end def printBST(root, i ,j, signal)   return if i > j   if signal == 0    p "k#{root[i][j]} is the root of the tree."    signal = 1   end   r = root[i][j]   #left child   if r - 1< i     p "d#{r - 1} is the left child of k#{r}."   else     p "k#{root[i][r - 1]} is the left child of k#{r}."     printBST(root, i, r - 1, 1 )   end   #right child   if r >= j      p "d#{r} is the right child of k#{r}."   else     p "k#{root[r + 1][j]} is the right child of k#{r}."     printBST(root, r + 1, j, 1)   end   end optimalBST(p, q, p.size - 1, e, root) printBST(root, 1, a.size-1, 0) puts "nThe expected cost is #{e[1][a.size-1]}."