čo sme sa doteraz naučili

• poznáme rôzne typy spájaných zoznamov - sú to najjednoduchšie dynamické štruktúry

č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

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

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:

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):

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;

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

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:

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

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. 2^U 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

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)

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ť

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;

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

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čí:

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:

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