[Delphi] Wyważanie drzewa (DSW) - problem


(Venice3000) #1

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.


([alex]) #2

Może użyj jakiś znanych algorytmów: R-B, AVL, Squeeze.

Lub jeżeli chcesz pełne równoważenie to proponuje algorytm Skiping Goat.

Poco wyważać otwarte drzwi?


(Venice3000) #3

Wyważanie algorytmem DSW jest wymagane w moim przypadku.

To jest projekt zaliczeniowy i musi zawierac DSW.

Tyle że nie moge znaleźć w którym miejscu nastepuje przepełnienie :confused:

Liczę na kogos mądrzejszego :slight_smile: