|
<![CDATA[
function MakeBalTree( S : SetOfKeys; lev : integer ) : tree;
var med : typekey;
median : KDKey;
A : SetOfKeys;
i, n : integer;
SubKey : array [1..Max] of typekey;
begin
if S=[] then MakeBalTree := nil
else begin
n := SizeOf(S);
{*** Select subkeys to find median ***}
for i:=1 to n do SubKey[i] := element(i,S)[lev];
{*** find median of subkeys ***}
med := select( n div 2 + 1, SubKey, 1, n );
A := [];
for i:=1 to n do
if element(i,S)[lev] > med then
A := A + element(i,S)
else if element(i,S)[lev] = med then
median := element(i,S);
MakeBalTree := NewNode( median,
MakeBalTree( S-A-[median], (lev+1) mod K ),
MakeBalTree( A, (lev+1) mod K ) )
end
end;
]]> |
Pascal source (352.opt.p) 