Problem jest taki:
Napisałem sobie procedure dodającą do drzewa AVL, z wszystkimi rotacjami, przy pomocy manuala z :
Drzewa BST
Jestem pewien, że działa ona poprawnie. Po prostu przerobiłem dodawanie.
Ale z usuwaniem jest już ciężej. Po usunięciu sprawdzam balanse, ale nie wiem czy dobrze.
Czy mógłby ktoś rzucić okiem na procedure usuwającą z drzewa AVL, ewentualnie podać porady jak to załatwić przy pomocy tego algorytmu.
Przedstawiam cały Kod - Drzewo AVL :
PROGRAM ZadAVL;
{$APPTYPE CONSOLE}
uses
SysUtils,
Crt;
TYPE
TDana = integer;
Drzewo = ^TDrzewo;
TDrzewo = record
rodzic : TDana;
balans : TDana;
lewo,prawo : Drzewo;
end;
VAR
a_Wezel : Drzewo;
dodawany,szukany,usuwany : TDana;
wybor : char;
ilosc,x,i : longint;
a_log : boolean;
{------------------------------------------------------------------------------}
procedure menu;
begin
clrscr;
writeln(' Lista 7. - Drzewo AVL.');
writeln(' =================================================');
writeln;
writeln(' 1. Wstaw element do drzewa.');
writeln(' 2. Wyswietl elementy drzewa: ');
writeln(' a. Inorder');
writeln(' b. Postorder');
writeln(' c. Preorder');
writeln(' 3. Usun element z drzewa. ');
writeln(' 4. Wyszukaj element w drzewie.');
writeln(' 0. Koniec.');
writeln;
end;
{------------------------------------------------------------------------------}
procedure Obrot_L(var Wezel:Drzewo);
var
temp : Drzewo;
begin
temp:=Wezel^.prawo;
Wezel^.prawo:=temp^.lewo;
temp^.lewo:=Wezel;
if temp^.balans=-1 then Wezel^.balans:=0
else Wezel^.balans:=-1;
if temp^.balans=0 then temp^.balans:=1
else temp^.balans:=0;
Wezel:=temp;
end;
{------------------------------------------------------------------------------}
procedure Obrot_P(var Wezel:Drzewo);
var
temp : Drzewo;
begin
temp:=Wezel^.lewo;
Wezel^.lewo:=temp^.prawo;
temp^.prawo:=Wezel;
if temp^.balans=1 then Wezel^.balans:=0
else Wezel^.balans:=1;
if temp^.balans=0 then temp^.balans:=-1
else temp^.balans:=0;
Wezel:=temp;
end;
{------------------------------------------------------------------------------}
procedure Obrot_PL (var Wezel:Drzewo);
begin
Obrot_P(Wezel^.prawo);
Obrot_L(Wezel);
end;
{------------------------------------------------------------------------------}
procedure Obrot_LP (var Wezel:Drzewo);
begin
Obrot_L(Wezel^.lewo);
Obrot_P(Wezel);
end;
{------------------------------------------------------------------------------}
procedure Wstawianie(var Wezel:Drzewo; klucz:byte; var log:boolean);
begin
if (Wezel=NIL) then
begin
new(Wezel);
log:=TRUE;
Wezel^.rodzic:=klucz;
Wezel^.balans:=0;
Wezel^.lewo:=NIL;
Wezel^.prawo:=NIL;
end
else
if (klucz < Wezel^.rodzic) then //lewe poddrzewo wiec zwiekszamy balans
begin
Wstawianie(Wezel^.lewo,klucz,log);
if log then
case Wezel^.balans of //lewa czesc za wysoka
1:
begin
if(Wezel^.balans=1) then Obrot_P(Wezel)
else Obrot_LP(Wezel);
log:=FALSE;
end;
0:
Wezel^.balans:=1;
-1:
begin
Wezel^.balans:=0;
log:=FALSE;
end;
end;
end
else
if(klucz > Wezel^.rodzic) then //prawe poddrzewo wiec zmniejszamy balans
begin
Wstawianie(Wezel^.prawo,klucz,log);
if log then
case Wezel^.balans of //prawa czesc za wysoka
1:
begin
Wezel^.balans:=0;
log:=FALSE;
end;
0: Wezel^.balans:=-1;
-1:
begin
if(Wezel^.balans=-1) then Obrot_L(Wezel)
else Obrot_PL(Wezel);
log:=FALSE;
end;
end;
end;
end;
{------------------------------------------------------------------------------}
procedure inorder(Wezel:Drzewo);
begin
if Wezel<>NIL then
begin
inorder(Wezel^.lewo);
write(Wezel^.rodzic,' - ');
inorder(Wezel^.prawo);
end;
end;
{------------------------------------------------------------------------------}
procedure postorder(Wezel:Drzewo);
begin
if Wezel<>NIL then
begin
postorder(Wezel^.lewo);
postorder(Wezel^.prawo);
write(Wezel^.rodzic,' - ');
end;
end;
{------------------------------------------------------------------------------}
procedure preorder(Wezel:Drzewo);
begin
if Wezel<>NIL then
begin
write(Wezel^.rodzic,' - ');
preorder(Wezel^.lewo);
preorder(Wezel^.prawo);
end;
end;
{------------------------------------------------------------------------------}
procedure wyszukiwanie(Wezel:Drzewo; szukany:TDana);{O(h), pesym. {O(n)}
var
znaleziono : boolean;
begin
znaleziono:=FALSE;
while ((Wezel<>NIL) and (znaleziono = FALSE)) do
begin
if Wezel^.rodzic=szukany then
znaleziono:=TRUE
else
if (szukany<Wezel^.rodzic) then
Wezel:=Wezel^.lewo
else
Wezel:=Wezel^.prawo;
end;
writeln;
if znaleziono=TRUE then writeln('Element znajduje sie w drzewie.')
else writeln('W drzewie nie ma takiego elementu.');
end;
{------------------------------------------------------------------------------}
procedure przywroc_struktureL(var Wezel:Drzewo; var log:boolean);
begin
if log then
case Wezel^.balans of
1:
begin
if(Wezel^.balans=1) then Obrot_P(Wezel)
else Obrot_LP(Wezel);
log:=FALSE;
end;
0:
Wezel^.balans:=1;
-1:
begin
Wezel^.balans:=0;
log:=FALSE;
end;
end;
end;
{------------------------------------------------------------------------------}
procedure przywroc_struktureP(var Wezel:Drzewo; var log:boolean);
begin
if log then
case Wezel^.balans of
1:
begin
Wezel^.balans:=0;
log:=FALSE;
end;
0: Wezel^.balans:=-1;
-1:
begin
if(Wezel^.balans=-1) then Obrot_L(Wezel)
else Obrot_PL(Wezel);
log:=FALSE;
end;
end;
end;
{------------------------------------------------------------------------------}
procedure Usuwanie(var Wezel:Drzewo; usuwany:TDana);
var
temp,Rodz,Dz,T: Drzewo;
begin
Rodz:=NIL;
temp:=Wezel;
while (temp<>NIL) do
begin
if (temp^.rodzic=usuwany) then break
else
begin
Rodz:=temp;
if (temp^.rodzic>usuwany) then temp:=temp^.lewo
else temp:=temp^.prawo;
end;
end;
if (temp<>NIL) then
begin
if ((temp^.lewo=NIL) or (temp^.prawo=NIL)) then
begin
if ((temp^.lewo=NIL) and (temp^.prawo=NIL)) then Dz:=NIL
else
if (temp^.lewo=NIL) then Dz:=temp^.prawo
else Dz:=temp^.lewo;
if (Rodz=NIL) then Wezel:=Dz
else
if (temp=Rodz^.lewo) then Rodz^.lewo:=Dz
else Rodz^.prawo:=Dz;
dispose(temp);
if Rodz^.lewo=Dz then przywroc_struktureL(a_Wezel,a_log);
if Rodz^.prawo=Dz then przywroc_struktureP(a_Wezel,a_log);
end
else
begin
Dz:=temp^.prawo;
if (Dz^.lewo=NIL) then temp^.prawo:=Dz^.prawo
else
begin
repeat
T:=Dz;
Dz:=Dz^.lewo;
until Dz^.lewo=NIL;
T^.lewo:=Dz^.prawo;
end;
temp^.rodzic:=Dz^.rodzic;
dispose(Dz);
if Rodz^.lewo<>NIL then przywroc_struktureL(a_Wezel,a_log);
if Rodz^.prawo<>NIL then przywroc_struktureP(a_Wezel,a_log);
end;
end
else writeln('Nie ma takiego elementu w drzewie.');
END;
{------------------------------------------------------------------------------}
procedure Zwolnij(var Wezel:Drzewo);
var
temp : Drzewo;
begin
if (Wezel<>NIL) then
begin
zwolnij(Wezel^.lewo);
zwolnij(Wezel^.prawo);
temp:=Wezel;
dispose(temp);
Wezel:=NIL;
end;
end;
{------------------------------------------------------------------------------}
BEGIN
randomize;
menu;
repeat
write(' Wybor : ');
readln(wybor);
case wybor of
'1':
begin
clrscr;
{write('Wprowadz klucz do Drzewa BST : ');
readln(dodawany);
wstawianie(a_Wezel,dodawany);}
write('Wprowadz ilosc elementow do dodania: ');
readln(ilosc);
for i:=1 to ilosc do
begin
x:=random(100);
wstawianie(a_Wezel,x,a_log);
end;
writeln;
writeln('Element/y umieszczono w drzewie prawidlowo.');
writeln('ENTER - dalej ...');
readln;
menu;
end;
'a':
begin
clrscr;
writeln('Elementy drzewa (inorder) : ');
inorder(a_Wezel);
writeln;writeln;
writeln('ENTER - dalej ...');
readln;
menu;
end;
'b':
begin
clrscr;
writeln('Elementy drzewa (postorder) : ');
postorder(a_Wezel);
writeln;writeln;
writeln('ENTER - dalej ...');
readln;
menu;
end;
'c':
begin
clrscr;
writeln('Elementy drzewa (preorder) : ');
preorder(a_Wezel);
writeln;writeln;
writeln('ENTER - dalej ...');
readln;
menu;
end;
'3':
begin
clrscr;
write('Wprowadz element, ktory chcesz usunac : ');
readln(usuwany);
Usuwanie(a_Wezel,usuwany);
writeln;
writeln('ENTER - dalej ...');
readln;
menu;
end;
'4':
begin
clrscr;
write('Wprowadz element do wyszukania : ');
readln(szukany);
wyszukiwanie(a_Wezel,szukany);
writeln;writeln;
writeln('ENTER - dalej ...');
readln;
menu;
end;
end;
until wybor='0';
writeln;
writeln('Struktura Drzewa AVL zostanie usunieta, a pamiec zwolniona.');
Zwolnij(a_Wezel);
writeln;
writeln('Wyjdz z programu ... - ENTER.');
readln;
END.