| <![CDATA[
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;
]]> |
![[Home]](../../images/home_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next
Algorithm]](../../images/nextalg_g.gif)
Pascal source
(3417.const.p) 