Optimal Binary Tree Search

 function OptTree( keys : ArrayKeys; p : ArrayCost; q : ArrayCost ) : tree; var wk, wki, min : cost; i, ik, indxmin, j, k : integer; {*** r[i,j] indicates the root of the optimal tree formed with keys from i to j ***} r : array[0..n,0..n] of integer; {*** c[i,j] indicates the optimal cost of the tree with keys from i to j ***} c : array[0..n,0..n] of cost; function CreateTree( i, j : integer ) : tree; {*** Create optimal tree from information in r[i,j] ***} var t : tree; begin if i=j then CreateTree := nil else begin new(t); t^.k := keys[ r[i,j] ]; t^.left := CreateTree( i, r[i,j]-1 ); t^.right := CreateTree( r[i,j], j ); CreateTree := t end end; begin {*** Initializations ***} c[0,0] := q[0]; for i:=1 to n do begin c[i,i] := q[i]; c[i-1,i] := 2*( q[i-1] + q[i] ) + p[i]; r[i-1,i] := i end; {*** Main loop to compute r[i,j] ***} wk := q[0]; for k:=2 to n do begin wk := wk + q[k-1] + p[k-1]; wki := wk; for i:=0 to n-k do begin ik := i+k; wki := wki + q[ik] + p[ik]; min := maxint; {*** Select root with lowest cost ***} for j:=r[i,ik-1] to r[i+1,ik] do if c[i,j-1]+c[j,ik] < min then begin min := c[i,j-1]+c[j,ik]; indxmin := j end; c[i,ik] := min + wki; r[i,ik] := indxmin; wki := wki - q[i] - p[i+1]; end end; OptTree := CreateTree( 0, n ); end;