4.3.2003
|
čo sa budeme dnes učiť
- ďalšia dynamická štruktúra
je strom - najjednoduchší typ je binárny
strom
- so stromom sa najčastejšie pracuje pomocou
rekurzie
- binárny vyhľadávací
strom
Základné pojmy
Graf je množina vrcholov pospájaných
hranami. V orientovanom grafe sú hrany usporiadané dvojice vrcholov, určujú
aj smer prepojenia vrcholov.
Strom je taký orientovaný graf, v ktorom
-
je jeden vrchol špeciálny - koreň - do tohto vrcholu nevedie žiadna hrana (šípka)
- do všetkých ostatných vrcholov vedie
práve jedna hrana
- graf je súvislý
Terminológia
- ak z nejakého vrcholu A vedie hrana (šípka)
do vrcholu B, tak vrchol A nazveme otcom (alebo predchodcom) a vrchol B synom
- ak sú dva vrcholy spojené hranou, hovoríme,
že spolu susedia
- ak nejaký vrchol nemá žiadnych synov,
hovoríme mu list, inak je to vnútorný
vrchol stromu
- podstrom - nejaký vrchol považujeme za koreň
a všímame si len jeho synov a ich synov atď.
- cesta - postupnosť vrcholov spojených hranami
(len jedným smerom)
- dĺžka cesty = počet vrcholov na ceste-1 (t.j. počet
hrán na ceste)
- výška/hĺbka stromu = dĺžka najdlhšej cesty
od koreňa k listom (prázdny strom=?; len koreň=0;
...)
- binárny strom - každý vrchol má
maximálne 2 synov
Reprezentácia stromov
- ako v halde - v jednorozmernom poli:
- každý prvok reprezentuje jeden vrchol stromu:
- prvý prvok je koreň
- í-ty vrchol má synov na indexoch 2*i a 2*i+1
- treba evidovať "diery" - miesta, ktoré
nereprezentujú vrcholy
- pole vrcholov, kde vrchol obsahuje info a indexy
do poľa pre ľavého a pravého syna
- pole vrcholov - každý vrchol má spájaný
zoznam synov (táto reprezentácia by sa
dala použiť aj na všeobecný strom)
NDÚ:
- vyskúšajte tieto reprezentácie
Dynamická štruktúra pre binárny
strom
definícia binárneho
stromu:
|
type
TStrom = class
info:prvok;
l,p:TStrom;
constructor Create(i:prvok; nl,np:TStrom);
function text:string; virtual;
end;
constructor TStrom.Create(i:prvok; nl,np:TStrom);
begin
info:=i; l:=nl; p:=np;
end;
function TStrom.text:string;
begin
Result:=IntToStr(info);
end;
var s:TStrom;
...
s:=nil; // prázdny strom
s:=TStrom.Create(1,nil,nil);
s:=TStrom.Create(1,TStrom.Create(2,nil,nil),TStrom.Create(3,nil,nil));
s:=TStrom.Create(1,TStrom.Create(2,TStrom.Create(4,nil,nil),
TStrom.Create(5,nil,nil)),
TStrom.Create(3,TStrom.Create(6,nil,nil),
TStrom.Create(7,nil,nil)));
...
|
NDÚ:
- zistite, koľko existuje rôznych stromov zložených
z N vrcholov?
Základné algoritmy
- na navštívenie postupne všetkých vrcholov
(napr. výpis hodnôt)
- pre N vrcholový binárny strom N! možných
prechodov, len niektoré z nich sú rozumné
=> 3 algoritmy prechádzania vrcholmi stromov:
- Preorder - najprv informáciu vo vrchole, potom
v ľavom podstrome a na záver v pravom
- Inorder - najprv spracuje ľavý podstrom, potom
info vo vrchole a na záver v pravom podstrome
- Postorder - najprv spracuje ľavý, potom pravý
podstrom a na záver info v samotnom vrchole
- naprogramujeme metódy preorder, inorder, postorder
- tieto postupne spracujú všetky vrcholy podľa špecifického poradia
nasledujúce metódy vypíšu všetky
vrcholy (do Memo1) v rôznych poradiach podľa príslušných
algoritmov:
|
procedure TStrom.vypis; // vypíše len jeden vrchol = koreň
begin
Form1.Memo1.Lines.Add(text);
end;
procedure TStrom.preorder;
begin
vypis;
if l<>nil then l.preorder;
if p<>nil then p.preorder;
end;
procedure TStrom.inorder;
begin
if l<>nil then l.inorder;
vypis;
if p<>nil then p.inorder;
end;
procedure TStrom.postorder;
begin
if l<>nil then l.postorder;
if p<>nil then p.postorder;
vypis;
end;
|
NDÚ:
- naučte sa "ručne" vytvoriť postupnosti
hodnôt vrcholov podľa všetkých troch algoritmov
- sú dané dve postupnosti čísel,
ktoré reprezentujú, napr. inorder a postorder
výpis nejakého stromu
- nakreslite tento strom
- navrhnite algoritmus, ktorý skonštruuje strom
na základe nejakých dvoch postupností
čísel
Metóda na pridávanie vrcholu na náhodné miesto do stromu - môžeme
využiť pri ladení algoritmov so stromami:
pridá list na náhodné
miesto v strome:
|
procedure TStrom.nahodnePridaj(i:prvok);
begin
if random(2)=0 then
if l=nil then l:=TStrom.Create(i,nil,nil)
else l.nahodnePridaj(i)
else
if p=nil then p:=TStrom.Create(i,nil,nil)
else p.nahodnePridaj(i)
end;
...
s:=TStrom.Create(1,nil,nil);
for i:=2 to 20 do s.nahodnePridaj(i);
|
- uvedomte si, že pridávať vrchol
pomocou tohto algoritmu môžeme len vtedy,
ak je strom neprázdny
Použitie procedurálneho parametra pre strom
Metóda vsetky vykoná nejaký
príkaz (procedúra pr) s každým
vrcholom stromu (algoritmus prechádza strom metódou preorder):
metóda všetky:
|
type
TStrom = class;
// niečo ako forward = sľubujem, že o chvíľu sa objaví deklarácia TStrom
prikaz = procedure(s:TStrom);
prvok = integer;
TStrom = class
...
procedure vsetky(pr:prikaz);
end;
procedure TStrom.vsetky(pr:prikaz);
begin
pr(self);
if l<>nil then l.vsetky(pr);
if p<>nil then p.vsetky(pr);
end;
|
Použitie procedurálneho parametra:
|
var
str:string;
procedure test(s:TStrom);
begin
str:=str+' '+s.text
end;
...
begin
str:='test =';
if s<>nil then s.vsetky(test);
Form1.Memo1.Lines.Add(str);
end;
|
Ďalšie algoritmy na stromoch
počet listov stromu:
|
function TStrom.pocetlistov:integer;
begin
if (l=nil) and (p=nil) then Result:=1
else begin
Result:=0;
if l<>nil then inc(Result,l.pocetlistov);
if p<>nil then inc(Result,p.pocetlistov);
end;
end;
|
Tri verzie funkcie na výpočet súčtu
hodnôt v strome: rekurzívna metóda,
nerekurzívna metóda, rekurzívna globálna funkcia:
súčet:
|
function TStrom.sucet:integer;
begin
Result:=info;
if l<>nil then inc(Result,l.sucet);
if p<>nil then inc(Result,p.sucet);
end;
function TStrom.NRsucet:integer; // nerekurzívna verzia
var
stack:array[1..100] of TStrom;
sp:integer; // stack pointer = ukazovateľ na vrch zásobníka
s:TStrom;
begin
Result:=0;
sp:=1; stack[sp]:=self;
repeat
if stack[sp]=nil then dec(sp)
else begin
s:=stack[sp];
inc(Result,s.info);
stack[sp]:=s.l;
inc(sp);
stack[sp]:=s.p;
end;
until sp=0;
end;
function sucet(s:TStrom):integer; // externá funkcia s parametrom TStrom
begin
if s=nil then Result:=0
else Result:=s.info+sucet(s.l)+sucet(s.p);
end;
|
Dve verzie algoritmu na zistenie hĺbky stromu - ako
metóda a ako globálna funkcia
hĺbka stromu:
|
function TStrom.hlbka:integer;
begin
if l<>nil then
if p<>nil then Result:=max(l.hlbka,p.hlbka)+1 // max je z unitu Math
else Result:=l.hlbka+1
else if p<>nil then Result:=p.hlbka+1
else Result:=0;
end;
function hlbka(s:TStrom):integer;
begin
if s=nil then Result:=-1
else Result:=max(hlbka(s.l),hlbka(s.p))+1;
end;
|
NDÚ:
- nerekurzívne: hĺbka, počet vrcholov,
preorder
- vzdialenosť najbližšieho listu od koreňa (plytčina)
Ďalšie pojmy
- otec = predchodca; syn = nasledovník
- dva stromy sú podobné, ak majú
rovnakú štruktúru (rovnaký tvar)
- jeden strom je kópiou druhého, ak sú
podobné a majú rovnaký obsah vrcholov
- úrovne: každý vrchol v strome má
svoju úroveň (level):
- koreň je v úrovni 0
- jeho synovia sú úrovne 1
- synovia vrcholu úrovne U majú úroveň
U+1
- v každej úrovni U je max. 2U vrcholov
- úplný strom úrovne U má
vo všetkých úrovniach (0 až U) maximálny
počet vrcholov
- šírka stromu = najväčší počet
vrcholov na jednej úrovni
šírka stromu (!!! pozor - algoritmus
je veľmi neefektívny):
|
function TStrom.sirka:integer;
var
n,p:integer;
begin
n:=0; Result:=0;
repeat
p:=pocetnaurovni(n);
if p>Result then Result:=p;
inc(n)
until p=0;
end;
function TStrom.pocetnaurovni(n:integer):integer;
begin
if n=0 then Result:=1
else begin
Result:=0;
if l<>nil then inc(Result,l.pocetnaurovni(n-1));
if p<>nil then inc(Result,p.pocetnaurovni(n-1));
end;
end;
|
NDÚ:
- vymyslite efektívnejší algoritmus
na zistenie šírky stromu
Metóda kresli nakreslí strom do grafickej
plochy (do nejakého canvasu)
kresli strom:
|
procedure TStrom.Kresli(g:TCanvas; sir,x,y:integer);
begin
sir:=sir div 2;
if l<>nil then begin
g.MoveTo(x,y); g.LineTo(x-sir,y+30);
l.Kresli(g,sir,x-sir,y+30);
end;
if p<>nil then begin
g.MoveTo(x,y); g.LineTo(x+sir,y+30);
p.Kresli(g,sir,x+sir,y+30);
end;
g.TextOut(x-5,y-8,text+' ');
end;
...
procedure TForm1.KresliClick(Sender: TObject); // tlačidlo KRESLI vo formulári
begin
Image1.Canvas.FillRect(Image1.ClientRect);
if s<>nil then
s.Kresli(Image1.Canvas,Image1.Width div 2,Image1.Width div 2,10);
end;
|
NDÚ:
- vyrobiť podobný strom (k danému),
ale s nulovými hodnotami
- vyrobiť kópiu stromu
- generovanie úplného stromu
- očíslujte strom po úrovniach -
v jednej úrovni zľava doprava
- vypíšte vrcholy po úrovniach
- pridaj vrchol na náhodné miesto
(s rovnakou pravdepodobnosťou pre ľubovoľné miesto)
Binárny vyhľadávací strom
- všetky hodnoty naľavo od otca sú menšie ako
otec
- všetky hodnoty napravo od otca sú väčšie
ako otec
- všetky podstromy sú tiež BVS
- výpis pomocou algoritmu inorder vypíše utriedenú
postupnosť
definíciu stromu rozdelíme na definíciu
vrcholu stromu:
|
type
prvok = integer;
TVrchol = class
info:prvok;
l,p:TVrchol;
constructor Create(i:prvok; nl,np:TVrchol);
function text:string; virtual;
end;
constructor TVrchol.Create(i:prvok; nl,np:TVrchol);
begin
info:=i; l:=nl; p:=np;
end;
function TVrchol.text:string;
begin
Result:=IntToStr(info);
end;
|
a trieda strom obsahuje len smerník na koreň
stromu:
|
type
TBVStrom = class
private
koren:TVrchol;
public
constructor Create;
procedure vypis;
function hladaj(i:prvok):TVrchol;
procedure vloz(i:prvok);
procedure zrus(i:prvok);
end;
constructor TBVStrom.Create;
begin
koren:=nil;
end;
procedure TBVStrom.vypis;
procedure vypis1(s:TVrchol);
begin
if s=nil then exit;
Form1.Memo1.Lines.Add(s.text);
vypis1(s.l);
vypis1(s.p);
end;
begin
vypis1(koren);
end;
|
Hľadanie v binárnom vyhľadávacom strome
- algoritmus sa postupne vnára do stromu,
pričom na základe hodnoty vo vrchole sa rozhoduje,
či pokračuje vľavo alebo vpravo
- keď nenájde vrchol, vráti nil
hľadanie v BVS:
|
function TBVStrom.hladaj(i:prvok):TVrchol;
begin
Result:=koren;
while (Result<>nil) and (Result.info<>i) do
if Result.info>i then Result:=Result.l
else Result:=Result.p;
end;
|
NDÚ:
- preprogramujte metódu hladaj rekurzívnym
algoritmom
- napíšte metódy min a max, ktoré
nájdu vrchol s minimálnou, resp. s
maximálnou hodnotou
Vloženie nového prvku tak, aby strom ostal
BVS
- najprv nájde miesto, kam by sa dal zavesiť
nový vrchol (ako list), pričom sa podľa hodnoty
vo vrchole rozhoduje, či pokračuje vľavo alebo vpravo
- ak vrchol s danou hodnotou nájde, tak do
stromu nový vrchol nevloží, ale skončí:
vloženie novej hodnoty do BVS:
|
procedure TBVStrom.vloz(i:prvok);
procedure vloz1(var s:TVrchol);
begin
if s=nil then s:=TVrchol.Create(i,nil,nil)
else if s.info=i then // nič, lebo sa našiel
else if s.info>i then vloz1(s.l)
else vloz1(s.p)
end;
begin
vloz1(koren);
end;
|
NDÚ:
- metódu vloz preprogramujte nerekurzívnym
algoritmom
Rušenie vrcholu tak, aby ostal strom BVS
- problém je iba s rušením vrcholu,
ktorý má oboch synov - daný algoritmus
nájde minimum v pravom podstrome vrcholu, toto minimum vyhodí
a jeho hodnotu dá namiesto rušeného vrcholu:
vyhodenie vrcholu z BVS:
|
procedure TBVStrom.zrus(i:prvok);
function zrusmin(var s:TVrchol):prvok;
var
q:TVrchol;
begin
if s.l=nil then begin
Result:=s.info;
q:=s; s:=s.p; q.Free
end
else Result:=zrusmin(s.l)
end;
procedure zrus1(var s:TVrchol);
begin
if s=nil then // nič
else if s.info>i then zrus1(s.l)
else if s.info<i then zrus1(s.p)
else if (s.l=nil) and (s.p=nil) then begin s.Free; s:=nil end
else if s.l=nil then s:=s.p
else if s.p=nil then s:=s.l
else s.info:=zrusmin(s.p) // z pravého podstromu minimálny prvok
end;
begin
zrus1(koren);
end;
|
NDÚ:
- realizovať bez rekurzie (netreba stack)
- opravte algoritmus tak, aby sa neuvoľňoval minimálny,
ale rušený vrchol a minimálny vrchol
sa presmerníkoval na miesto rušeného
vrcholu
- problém s degenerovanými stromami
- závisí od poradia vloz
- daná utriedená postupnosť - vytvoriť
čo "najvyváženejší" BVS
- daný BVS treba preusporiadať tak, aby
výsledný BVS mal minimálne
možnú hĺbku
|