AVL medis

Norint gauti papildomų balų neštis į egzaminą, galima buvo suprogramuoti AVL medį. Iš kursiokės paėmiau jos AVL programą ir aiškinausi pusę nakties prieš atsiskaitymo dieną. Pagalvojau, kad galbūt galima bus gauti nors ne maksimumą, bet bent pusę taškų už nepaties programuotą programą, jeigu gerai ją sugebėsiu paaiškinti bet kurioje eilutėje, bei jeigu parašysiu programai kažkokių papildomų įrankių. Kitą pusnaktę tuos įrankius ir bandžiau rašyti. Pavyko parašyti procedūrą, kuri sunumeruoja dvejetainio AVL medžio elementus man reikiama hierarchine tvarka, ir antrą procedūrą, kuri tuos elementus išspausdina ekrane atidėdama atitinkamą skaičių tarpų.

AVL programa tai dvejetainis medis, kuris pildomas naujais elementais, balansuojasi. Dvejetainis medis skirtas ten įdėto elemento paieškai. Jeigu į medį bus dedami elementai vienas po kito didėjantys, arba vienas po kito mažėjantys, tai medis turės vieną ilgą šaką, o jei bus dedami įvairūs elementai, tai jis bus šakotas bei trumpašakis ir bus greičiau vykdoma paieška. AVL medis - besibalansuojantis medis. Kuomet viena jo šaka pasidaro ilgesnė už bet kurią kitą 2 sąlyginiai vienetais, tai ji deformuojasi, vykdomas "posūkis": šaka ale nupjaunama, perlaužiama perpus, tada suklijuojama "V" raide ir pritvirtinama prie šakos pamato.

Taip atrodo programos interfeiso fragmentas, atlikus vieno skaičiaus įterpimą į AVL medį:

(dvejetas ir trejetas paraudoninti, neryškiai čia matosi)

Beje, formulę su DIV'ais tai galvojau ir testavau tikrai kokias 3 valandas. O medžio išspausdinimą padariau su lygiavimo klaida (buvo ne visai gražu), kurią sugalvojau kaip pataisyti tik kai prisėdau savaitę po atsiskaitymo.

Pateiksiu tik programos procedūras, kurios paruošia masyvą ir išspausdina medį pseudografiškai.

( uses crt;
type Pnode=^node;
node=record
l,r,t : Pnode;
n: integer;
end;

var root :Pnode; skait: array[1..255] of integer;

function auksciai( rod : Pnode) : integer;
var a1, a2 : integer;
begin
if (rod <> nil)
then
begin
a1 := auksciai(rod^.l) + 1 ;
a2 := auksciai(rod^.r) + 1 ;
if a1>=a2 then auksciai:=a1
else auksciai:=a2 ;
end
else auksciai := -1;
end; )

procedure isEilesMasyvas;
var te:Pnode; au,n,el,power,k,kn: integer;
begin
au:=auksciai(root);
power:=1; el:=0;
for n:=1 to au+1 do begin power:=power*2; el:=el+power div 2; end;
for n:=1 to el do
begin k:=1; kn:=n;
while k*2<=n do k:=k*2; te:=root;
while (kn<>1 ) and (k<>1) and (kn div k <>0) and (te<>nil) do
begin if kn mod k div (k div 2) = 0 then te:=te^.l else te:=te^.r; k:=k div 2; end;
if te <> nil then skait[n]:=te^.n else skait[n]:=0;
end;
writeln('stai isEilesMasyvo ',el, ' elementai: ');
for n:=1 to el do write(skait[n],' ');
end;


procedure piestiMedi(reiksme: integer);
var au,i,j,k,s,power,tarpai: integer;
begin
au:=auksciai(root);
s:=0;
writeln;
writeln('isspausdinu visus Medzio elementus: ');
for i:=1 to au+1 do
begin
power:=1;
for j:=au+1-i downto 1 do begin power:=power*2; end;
tarpai:=power*2-2;
power:=1;
for j:=1 to i do power:=power*2;
for k:=1 to power div 2 do
begin
for j:=1 to tarpai do write(' ');
if k>1 then for j:=1 to tarpai do write(' ');
s:=s+1;
if (skait[s]<10) and (skait[s]>0) then write(' ');
if skait[s]<>0 then
begin write(' ');
if skait[s]<>reiksme then write(skait[s])
else begin textcolor(12); write(skait[s]); textcolor(7); end;
write(' ');
end
else write(' ');
end;

writeln;
end;
end;