Ruby实现的最优二叉查找树算法
算法导论上的伪码改写而成，加上导论的课后练习第一题的解的构造函数。
#encoding:utf-8 =begin author:xujin date:Nov11,2012 OptimalBinarySearchTree tofindbyusingEditDistancealgorithm referto<<introductiontoalgorithms>> exampleoutput: "k2istherootofthetree." "k1istheleftchildofk2." "d0istheleftchildofk1." "d1istherightchildofk1." "k5istherightchildofk2." "k4istheleftchildofk5." "k3istheleftchildofk4." "d2istheleftchildofk3." "d3istherightchildofk3." "d4istherightchildofk4." "d5istherightchildofk5."
Theexpectedcostis2.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)}
defoptimalBST(p,q,n,e,root) w=Array.new(p.size+1){Array.new(p.size+1)} foriin(1..n+1) e[i][i-1]=q[i-1] w[i][i-1]=q[i-1] end forlin(1..n) foriin(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] forrin(i..j) t=e[i][r-1]+e[r+1][j]+w[i][j] ift<e[i][j] e[i][j]=t root[i][j]=r end end end end end
defprintBST(root,i,j,signal) returnifi>j ifsignal==0 p"k#{root[i][j]}istherootofthetree." signal=1 end r=root[i][j] #leftchild ifr-1<i p"d#{r-1}istheleftchildofk#{r}." else p"k#{root[i][r-1]}istheleftchildofk#{r}." printBST(root,i,r-1,1) end #rightchild ifr>=j p"d#{r}istherightchildofk#{r}." else p"k#{root[r+1][j]}istherightchildofk#{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"\nTheexpectedcostis#{e[1][a.size-1]}."