29. Binárne stromy


posledná zmena: 4.3.2003

Banner Text 4.3.2003

    č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

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


© 2003 AB, KVI
blaho@fmph.uniba.sk