Witam!
Napisałem implementacje wyważania drzewa w Delphi - algorytm DSW.
Jednak wyważając w pętli l:=1…10 drzewa o ilości węzłów l*100000
doczekam się przeważnie tylko wyniku dla 100tys.,200tys., ewentualnie 300tys. elementów w drzewie.
Potem następuje tzw. EStackOverflow - przepełnienie stosu.
Podaję zawodny kod źródłowy:
procedure rotacjaright(var p:drzewo);
var tmp1,tmp2:drzewo;
begin
if p=nil then exit;
tmp1:=p^.lewy;
tmp2:=p;
while tmp1^.prawy<>nil do
begin
tmp2:=tmp1;
tmp1:=tmp1^.prawy;
end;
if tmp2<>p then
begin
tmp2^.prawy:=tmp1^.lewy;
tmp1^.lewy:=p^.lewy;
end;
tmp1^.prawy:=p;
p^.lewy:=nil;
p:=tmp1;
end;
procedure rotacjaleft(var p:drzewo);
var tmp3,tmp4:drzewo;
begin
if p=nil then exit;
tmp3:=p^.prawy;
tmp4:=p;
while tmp3^.lewy<>nil do
begin
tmp4:=tmp3;
tmp3:=tmp3^.lewy;
end;
if tmp4<>p then
begin
tmp4^.lewy:=tmp3^.prawy;
tmp3^.prawy:=p^.prawy;
end;
tmp3^.lewy:=p;
p^.prawy:=nil;
p:=tmp3;
end;
function Licz(p : drzewo) : integer;
begin
if p=nil then licz:=0
else licz:=licz(p^.lewy)+licz(p^.prawy)+1;
end;
procedure wywaz(var p:drzewo);
var ileL, ileP : integer;
begin
if p=nil then exit;
ileP:=licz(p^.prawy);
ileL:=licz(p^.lewy);
repeat
if ileP-ileL>1 then
begin
dec(ileP);
inc(ileL);
rotacjaleft(p);
end
else if ileL-ileP>1 then
begin
dec(ileL);
inc(ileP);
rotacjaright(p);
end
else break;
until false;
wywaz(p^.lewy);
wywaz(p^.prawy);
end;
Proszę fachowców o pomoc.
Pozdrawiam.
