29.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
29. Prednáška
úlohy | cvičenie


Binárny vyhľadávací strom

Ak by sme nejako zorganizovali poradie vrcholov v strome, mohli by sme výrazne zefektívniť vyhľadávanie nejakého prvku. Napr. vyhľadávanie v poli sme veľmi urýchlili, keď sme prvky poľa usporiadali napr. vzostupne: potom sme pomocou binárneho vyhľadávania našli ľubovoľný prvok v poli s N prvkami maximálne na log(N) porovnaní. Ak by sme podobnú ideu urobili aj s binárnym stromom, aj tu by sa nám veľmi urýchlilo vyhľadávanie.

Zadefinujeme binárny strom so špeciálnymi vlastnosťami, tzv. binárny vyhľadávací strom = BVS

Pre každý vrchol takéhoto stromu musí platiť:

  • všetky vrcholy jeho ľavého podstromu majú hodnoty menšie ako je hodnota vo vrchole
  • všetky vrcholy jeho pravého podstromu majú hodnoty väčšie ako je hodnota vo vrchole
  • oba podstromy sú tiež BVS

Definíciu BVS rozdelíme na definíciu vrcholu stromu TVrchol a zvlášť zapuzdrenie celého stromu TBVStrom. Samotná trieda BVS teda obsahuje len smerník na koreň stromu (môže byť nil): 

type
  TBVStrom = class
  private
    Koren: TVrchol;
  public
    constructor Create;
    function Inorder: string;
    function Hladaj(Hodnota: Integer): TVrchol;
    procedure Vloz(Hodnota: Integer);
    procedure Zrus(Hodnota: Integer);
  end;
 
function TBVStrom.Inorder: string;        // Inorder = utriedený výpis
  function Inorder1(Vrchol: TVrchol): string;
  begin
    if Vrchol = nil then
       Result := ''
     else
       Result := Inorder1(Vrchol.L) + Vrchol.Text + Inorder1(Vrchol.P);
  end;
begin
  Result := Inorder1(Koren);
end;

Uvedomte si, že výpis pomocou algoritmu Inorder vypíše utriedenú postupnosť všetkých hodnôt v BVS strome.



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. Vnáranie skončí, keď nájde hľadaný vrchol. Keď takýto vrchol nenájde, vráti nil: 

function TBVStrom.Hladaj(Hodnota: Integer): TVrchol;
begin
  Result := Koren;
  while (Result <> nil) and (Result.Info <> Hodnota) do
    if Result.Info > Hodnota then
      Result := Result.L
    else
      Result := Result.P;
end;

Ďalšie námety:

  • preprogramujte metódu Hladaj rekurzívnym algoritmom (bez cyklu)
  • napíšte metódy Min a Max, ktoré nájdu vrchol s minimálnou, resp. s maximálnou hodnotou v strome
  • preprogramujte definíciu BVS tak, aby sa v strome uchovávali reťazce (string) namiesto celých čísel



Vloženie nového prvku tak, aby strom ostal BVS


Algoritmus 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 pri hľadaní vrchol s danou hodnotou už nájde, tak do stromu nový vrchol nevloží, ale skončí: 

procedure TBVStrom.Vloz(Hodnota: Integer);
var
  V: TVrchol;
begin
  if Koren = nil then
    Koren := TVrchol.Create(Hodnota, nil, nil)
  else
  begin
    V := Koren;
    while V.Info <> Hodnota do
      if V.Info > Hodnota then
      begin
        if V.L = nil then
          V.L := TVrchol.Create(Hodnota, nil, nil);
        V := V.L;
      end
      else
      begin
        if V.P = nil then
          V.P := TVrchol.Create(Hodnota, nil, nil);
        V := V.P;
      end;
  end;
end;

Keď sa to isté zapíše rekurzívnou procedúrou, vyzerá to takto: 

procedure TBVStrom.Vloz(Hodnota: Integer);
 
  procedure Vloz1(var V: TVrchol);
  begin
    if V = nil then
      V := TVrchol.Create(Hodnota, nil, nil)
    else if V.Info = Hodnota then
      // nič, lebo už našiel
    else if V.Info > Hodnota then
      Vloz1(V.L)
    else
      Vloz1(V.P);
  end;
 
begin
  Vloz1(Koren);
end;

Všimnite si, že formálny parameter Hodnota metódy Vloz je globálnou premennou pre vnorenú pomocnú procedúru Vloz1.



Rušenie vrcholu tak, aby strom zostal BVS


Pri rušení (vyhadzovaní) nejakého vrcholu z BVS môžu nastať tieto prípady:

  • vrchol sa tam nenachádza a teda nie je čo robiť
  • vyhadzovaný vrchol je list (nemá žiadnych synov), tak ho stačí zrušiť a otcovi nastaviť nil
  • vyhadzovaný vrchol má len jedného syna: vrchol vyhodíme a v strome ho nahradíme jeho synom
  • malým problémom je rušenie vrcholu, ktorý má oboch synov: algoritmus to bude pracovať tak, že nájde minimum v pravom podstrome vyhadzovaného vrcholu, toto minimum vyhodí a jeho hodnotu dá namiesto rušeného vrcholu (fungovalo by to aj s maximom v ľavom podstrome):
procedure TBVStrom.Zrus(Hodnota: Integer);
 
  function ZrusMin(var S: TVrchol): Integer;
  var
    Q: TVrchol;
  begin
    if S.L = nil then
    begin
      Result := S.Info;
      Q := S;
      S := S.P;   // toto modifikuje skutočný parameter
      Q.Free;
    end
    else
      Result := ZrusMin(S.L);
  end;
 
  procedure Zrus1(var S: TVrchol);
  begin
    if S = nil then
      // nič
    else if S.Info > Hodnota then
      Zrus1(S.L)
    else if S.Info < Hodnota 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;

Funkcia ZrusMin má formálny var-parameter - je to veľmi dôležité, totiž funkcia okrem toho, že vráti nejakú hodnotu (minimum z ľavého podstromu), vrchol s týmto minimom zo stromu vyhodí (tým sa bude meniť nejaká položka niektorého vrcholu)

Môžete experimentovať s aplikáciou, ktorá pracuje s binárnym vyhľadávacím stromom P29.1.zip.

Ďalšie námety:

  • realizovať bez rekurzie
  • 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 (treba poznať predchodcu 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


Aritmetické stromy

Veľmi zaujímavé je využitie binárnych stromov, keď do vrcholov zapíšeme znamienka aritmetických operácií a tiež rôzne čísla. Aritmetické operácie (+, -, /, *) dáme do vnútorných vrcholov a do listov dáme operandy (napr. čísla alebo identifikátory premenných). Takto dostaneme, tzv. aritmetický strom. Keďže všetky operácie sú binárne, tak musí platiť, že aj každý vrchol má 0 alebo 2 synov (nemôže mať iba jedného).

V anglickej literatúre pod názvom "binary expression tree", napr. [1] alebo [2].

Každému aritmetickému výrazu zodpovedá práve jeden aritmetický strom a naopak každý aritmetický strom reprezentuje nejaký aritmetický výraz. Napr. daný strom na obrázku má takýto úplne uzátvorkovaný infixový zápis: (( 5 - 2 ) * ( 1 + 3 )):

aritmetický strom

Takýto strom má veľmi zaujímavú vlastnosť:

  • ak jeho vrcholy vypíšeme pomocou algoritmu Preorder, dostaneme známy prefixový zápis, napr. * - 5 2 + 1 3,
  • ak jeho vrcholy vypíšeme pomocou algoritmu Postorder, dostaneme postfixový zápis, napr. 5 2 - 1 3 + *,
  • horšie je to s algoritmom Inorder: ak by sme pomocou neho vypísali vrcholy stromu, dostali by sme 5 - 2 * 1 + 3 a preto zvykneme v Inorder vypisovať aj zátvorky (úplný uzátvorkovaný výraz)

Aritmetický strom môžeme reprezentovať rôznymi spôsobmi. My tu ukážeme jedno z najelegantnejších riešení, v ktorom zadefinujeme bázovú triedu TAstrom a z nej odvodené dve triedy TAOperacia a TAOperand:

  • bázová trieda TAstrom slúži na definovanie virtuálnych metód a zároveň pomocou nej definujeme polymorfizmus:
    • strom sa skladá z vrcholov dvoch typov a preto všetky smerníky v ňom musia ukazovať buď na jeden alebo druhý typ (sú to "polymorfné smerníky")
    • my to riešime touto bázovou triedou: všetky smerníky budú tohto typu a z polymorfizmu vieme, že aj ľubovoľného odvodeného
  • inštancia triedy TAOperacia uchováva jednu binárnu operáciu (nejaký znak) a dva jej operandy, čo sú opäť smerníky buď na ďalšiu operáciu alebo nejaké konštanty
  • inštancia triedy TAOperand uchováva len nejakú číselnú konštantu - z tohto vrcholu už nejdú žiadne ďalšie smerníky a teda je to list stromu
type
  TAStrom = class
    function Hodnota: Integer; virtual; abstract;
    function Prefix: string; virtual; abstract;
  end;
 
  TAOperacia = class(TAStrom)
    Op: Char;
    L, P: TAStrom;
    constructor Create(Z: Char; LL, PP: TAStrom);
    function Hodnota: Integer; override;
    function Prefix: string; override;
  end;
 
  TAOperand = class(TAStrom)
    Hod: Integer;
    constructor Create(H: Integer);
    function Hodnota: Integer; override;
    function Prefix: string; override;
  end;
 
constructor TAOperacia.Create(Z: Char; LL, PP: TAStrom);
begin
  Op := Z;
  L := LL;
  P := PP;
end;
 
function TAOperacia.Hodnota: Integer;
begin
  case Op of
    '+': Result := L.Hodnota + P.Hodnota;
    '-': Result := L.Hodnota - P.Hodnota;
    '*': Result := L.Hodnota * P.Hodnota;
    '/': Result := L.Hodnota div P.Hodnota;
    else raise Exception.Create('nerozumiem ' + Op);
  end;
end;
 
function TAOperacia.Prefix: string;
begin
  Result := ' ' + Op + L.Prefix + P.Prefix;
end;
 
constructor TAOperand.Create(H: Integer);
begin
  Hod := H;
end;
 
function TAOperand.Hodnota: Integer;
begin
  Result := Hod;
end;
 
function TAOperand.Prefix: string;
begin
  Result := ' ' + IntToStr(Hod);
end;
 
{ testovací program }
 
var
  AStrom: TAStrom;
begin
  AStrom := TAOperacia.Create('-',
              TAOperacia.Create('*',
                TAOperand.Create(7),
                TAOperand.Create(3)),
              TAOperacia.Create('/',
                TAOperand.Create(15),
                TAOperand.Create(3)));
  WriteLn('Prefix = ', AStrom.Prefix);
  WriteLn('Hodnota = ', AStrom.Hodnota);
end.

V tomto progame sa vyskytlo niekoľko noviniek:

  • pri deklarovaní metód triedy TAstrom sme použili direktívu abstract
    • takéto metódy (nemajú definované svoje telo) sa ale volať nedajú - spôsobí to prerušenie programu s chybovou správou
    • ale toto zabezpečí, že bázová trieda definuje virtuálne metódy, ktoré sa v odvodených triedach prekryjú (override) nejakým konkrétnym správaním
    • tomuto hovoríme abstraktná trieda, lebo nemá zmysel definovať priamo inštancie tejto triedy, ale len z nej odvodených typov
    • napr. aj trieda TStream má niektoré metódy abstract (Read, Write a Seek) a z nej odvodený typ TFileStream tieto metódy konkretizuje svojim obsahom
  • hoci sme v testovacom programe zadeklarovali premennú typu TAstrom, priradili sme do nej objekt typu TAOperacia (lebo aritmetický výraz na najvyššej úrovni obsahuje nejakú binárnu operáciu), ale mohli by sme sem priradiť aj objekt typu TAOperand, ak by bol aritmetický výraz len číselnou konštantou
  • už vieme, že príkaz raise Exception.Create(text chyby); spôsobí prerušenie výpočtu s danou chybovou správou

Môžete experimentovať s aplikáciou, ktorá nakreslí aritmetický strom P29.2.zip.

Ďalšie námety:

  • zrealizujte postfixový a úplne uzátvorkovaný infixový výpis aritmetického stromu
  • skonštruujte aritmetický strom z prefixového (postfixového, úplne uzátvorkovaného) zápisu
  • navrhnite tretí typ vrcholu - premenná:
    • výpis (napr. Prefix) vypíše identifikátor,
    • Hodnota vráti hodnotu premennej z tabuľky (tabuľka je nejaké dvojstĺpcové pole: identifikátor premennej a hodnota premennej)
  • aritmetický strom sa dá reprezentovať jediným typom vrcholu, ktorý obsahuje zlúčené stavové premenné zo všetkých typov vrcholov a tiež stavovú premennú, ktorá vyjadruje typ vrcholu (napr. operand, operátor, ...) - naprogramujte metódy pre takúto reprezentáciu:
type
  TAStrom = class
    Typ: (Operand, Operacia);
    Hod: Integer;
    Op: Char;
    L, P: TAStrom;
    constructor CreateOperand(H: Integer);
    constructor CreateOperaciu(Z: Char; LL, PP: TAstrom);
    function Hodnota: Integer;
    function Prefix: string;
    ...
  end;


Všeobecné stromy

Keď potrebujeme pracovať so stromovou štruktúrou, v ktorej môže mať každý vrchol aj viac ako 2 synov, musíme nejako ideu binárneho stromu zovšeobecniť. Jednou z možností je, namiesto ľavého a pravého podstromu (syna), zadefinovať pole smerníkov na podstromy, napr. takto: 

const
  N = 5;
 
type
  TStrom = class
    Info: Integer;
    Syn: array [1..N] of TStrom;
    function PocetVrcholov: Integer;
    function PocetListov: Integer;
  end;
 
function TStrom.PocetVrcholov: Integer;
var
  I: Integer;
begin
  Result := 1;
  for I := 1 to N do
    if Syn[I] <> nil then
      Inc(Result, Syn[I].PocetVrcholov);
end;
 
function TStrom.PocetListov: Integer;
var
  I: Integer;
begin
  Result := 0;
  for I := 1 to N do
    if Syn[I] <> nil then
      Inc(Result, Syn[I].PocetListov);
  if Result = 0 then
    Result := 1;
end;

Maximálny počet synov pre každý vrchol (stupeň vrcholu) nemusíme obmedziť nejakou konštantou, ale môžeme použiť dynamické pole: 

type
  TStrom = class
    Info: Integer;
    Syn: array of TStrom;
    function PocetVrcholov: Integer;
    function PocetListov: Integer;
  end;
 
function TStrom.PocetVrcholov: Integer;
var
  I: Integer;
begin
  Result := 1;
  for I := 0 to High(Syn) do        // predpokladáme, že žiaden syn nie je nil
    Inc(Result, Syn[I].PocetVrcholov);
end;
 
function TStrom.PocetListov: Integer;
var
  I: Integer;
begin
  Result := 1;
  for I := 0 to High(Syn) do
    Inc(Result, Syn[I].PocetListov);
  if Result > 1 then
    Dec(Result);
end;

Všeobecné stromy sa ale zvyknú reprezentovať aj inak: pomocou metódy brat-syn, ktorá vychádza z binárneho stromu:

  • v každom vrchole sú okrem samotnej informácie Info aj dva smerníky:
    • 1. smerník - prvý (najľavejší, najstarší, prvorodený) syn
    • 2. smerník - brat, t.j. nasledujúci vrchol so spoločným otcom
  • reťaz vrcholov spojených smerníkom brat tvorí jednosmerný spájaný zoznam synov nejakého vrcholu

Napr. strom vľavo je reprezentovaný pomocou syn-brat vpravo:

všeobecný strom

Všimnite si, že smerníky smerom nadol znamenajú vzťah syn a vodorovné smerníky znamenajú vzťah brat.

Reprezentácia všeobecného stromu pomocou syn-brat: 

type
  TStrom = class
    Info: Integer;
    Syn, Brat: TStrom;
    function PocetVrcholov: Integer;
    function PocetListov: Integer;
  end;
 
function TStrom.PocetVrcholov: Integer;
var
  P: TStrom;
begin
  Result := 1;
  P := Syn;
  while P <> nil do
  begin
    Inc(Result, P.PocetVrcholov);
    P := P.Brat;
  end;
end;
 
function TStrom.PocetListov: Integer;
var
  P: TStrom;
begin
  Result := 0;
  P := Syn;
  while P <> nil do
  begin
    Inc(Result, P.PocetListov);
    P := P.Brat;
  end;
  if Result = 0 then
    Result := 1;
end;

Poznámka:

  • koreň väčšinou nemá bratov - ak by mal, voláme túto štruktúru "les", t.j. štruktúra s viacerými stromami

Ďalšie námety:

(vo všetkých troch reprezentáciách):
  • hĺbka, šírka, súčet hodnôt, ...
  • výpis ako reťazec alebo nakreslenie do plátna (Canvas)
  • zistiť, či je strom binárny, resp. zistiť árnost stromu
  • vygenerovať úplný N-árny strom nejakej hĺbky
    • hodnoty vynulovať
    • postupne očíslovať
    • očíslovať po úrovniach
  • prekódovať binárny strom do tejto reprezentácie - treba si uvedomiť, že sa stratí informácia o tom, že napr. ľavý syn neexistuje ale pravý áno
  • Pridaj(I, J, Hodnota) - pridať nového syna I-temu vrcholu v úrovni J
  • vytvoriť všeobecný strom z nejakej adresárovej štruktúry súborov
  • vytvoriť alebo načítať textový súbor popisujúci strom: každý riadok bude popisovať jeden vrchol, počet medzier na začiatku riadka označuje úroveň vnorenia (koreň - prvý riadok začína v 1. stĺpci, jeho synovia začínajú na druhých stĺpcoch ...)


Všeobecné zoznamy

Zatiaľ sme poznali lineárny zoznam ako postupnosť (aj prázdna) atómov (t.j. nejakých základných hodnôt, napr. reťazcov), napr. (a b c d).

Všeobecný zoznam je je komplexnejšia štruktúra. Definujeme ju rekurzívnym popisom:

  • aj samotný atóm je zoznam - napr. znakový reťazec, číslo, objekt, ...
  • postupnosť atómov a zoznamov (aj prázdna) uzavretá v okrúhlych zátvorkách je zoznam

Napr. všeobecné zoznamy môžeme zapísať takto:

  • () je prázdny zoznam
  • q, Lazarus, 2010 sú atómy
  • (lazarus) je jednoprvkový zoznam
  • (x y), (Janko Hrasko), (100 150) sú dvojprvkové zoznamy
  • (a b c d e f) je šesťprvkový zoznam atómov
  • (a () b) je trojprvkový zoznam, ktorého druhým prvkom je prázdny zoznam
  • ((a b) c (d) ()) je štvorprvkový zoznam, kde prvý prvok je dvojprvkový zoznam, druhý je atóm, tretí je jednorvkový zoznam a posledným prvkom je prázdny zoznam

Použijeme podobnú reprezentáciu s akou sme pracovali pri aritmetických stromoch (abstraktná bázová trieda a od nej odvodené dva typy vrcholov), pričom ale samotná stromová štruktúra sa podobá všeobecnému stromu typu syn-brat.

...

Idea je takáto:

  • jeden typ vrcholov stromu je atóm TAtom - tento vrchol už nemá potomkov, teda je to list; nesie len informáciu o hodnote atómu
  • druhý typ vrcholu stromu TZoznam označuje, že tento prvok je časť zoznamu, t.j. vrchol má dvoch potomkov: hodnota prvku zoznamu (niečo ako prvý syn vo všeobecnom strome) a ďalší prvok zoznamu (ten musí byť typu TZoznam)
  • okrem toho sme zadefinovali abstraktnú bázovú triedu TVseobZoznam, aby sme mohli definovať polymorfné objekty (sú buď typu TAtom alebo TZoznam) a virtuálne metódy
type
  TVseobZoznam = class
    function Vypis: string; virtual; abstract;
    function Prvy: TVseobZoznam; virtual; abstract;
  end;
 
  TAtom = class(TVseobZoznam)
    Hodn: string;
    constructor Create(H: string);
    function Vypis: string; override;
    function Prvy: TVseobZoznam; override;
  end;
 
  TZoznam = class(TVseobZoznam)
    Syn: TVseobZoznam;
    Dalsi: TZoznam;
    function Vypis: string; override;
    function Prvy: TVseobZoznam; override;
  end;
 
constructor TAtom.Create(H: string);
begin
  Hodn := H;
end;
 
function TAtom.Vypis: string;
begin
  Result := Hodn + ' ';
end;
 
function TAtom.Prvy: TVseobZoznam;
begin
  raise Exception.Create('pre ATOM sa nedá urobiť Prvy');
end;
 
function TZoznam.Vypis: string;
var
  S: TZoznam;
begin
  Result := '( ';
  S := self;
  repeat
    if S.Syn <> nil then
      Result := Result + S.Syn.Vypis;
    S := S.Dalsi;
  until S = nil;
  Result := Result + ') ';
end;
 
function TZoznam.Prvy: TVseobZoznam;
begin
  Result := Syn;
  if Result = nil then
    raise Exception.Create('z prázdneho zoznamu sa nedá urobiť Prvy');
end;

Ako ukážku uvádzame aplikáciu, v ktorej sa ilustruje čítanie dobrého všeobecného zoznamu do zadanej dátovej štruktúry a jeho výpis v rovnakom tvare. Konzolovú aplikáciu si môžete stiahnuť P29.3.zip.


Ďalšie námety:

  • testovací program neobsahuje uvoľňovanie pamäti - metóda Destroy, doprogramujte ju
  • naprogramujte funkcie, ktoré vrátia: í-ty, posledný prvok zoznamu, zoznam bez prvého prvku, bez posledného, bez í-teho prvku, počet atómov, počet výskytov ...,
  • naprogramujte metódy, ktoré vyrobia kópiu všeobecného zoznamu, zistia, či sa dané zoznamy rovnajú
  • konštruktor CreateFromStream(t: TStream) - z jedného riadka textového súboru
  • metódy: VlozPrvy(Prvok: TVseobZoznam), VlozPosledny(Prvok: TVseobZoznam),
  • Prevrat, Pripoj(Z: TVseobZoznam)
  • zmeňte reprezentáciu všeobecného zoznamu tak, že vrchol je buď atóm alebo obsahuje dynamické pole svojich prvkov
    • realizujte načítanie, výpis a aj ostatné metódy


Lexikografické stromy

V literatúre môžeme nájsť aj názvy prefixový strom, písmenkový strom alebo v angličtine Trie (zo slova "retrieval").

Budeme riešiť takúto úlohu: do binárneho stromu budeme ukladať informácie o reťazcoch (slovách), ktoré sú zložené len z dvoch písmen z {'a', 'b'}. Napr. sú to slová 'abba', 'aaab', 'b', 'ba', 'bbbbbbbabb', atď. V strome označíme všetky hrany do ľavého podstromu písmenom 'a' a do pravého písmenom 'b'. Potom sa každá cesta od koreňa do nejakého vrcholu dá popísať postupnosťou týchto písmen. Preto každému vrcholu v strome sa dá jednoznačne priradiť reťazec z písmen 'a' a 'b', ktorý vyjadruje cestu od koreňa do tohto vrcholu.

Ak teraz zadeklarujeme vrchol takéhoto stromu takto: 

type
  TLexStrom = class
    Info: ...
    P: array['a'..'b'] of TLexStrom;
  end;
 
var
  Koren: TLexStrom;

tak cesta v strome Koren.P['a'].P['b'].P['a'].P['a'] vyjadruje vrchol, ktorý reprezentuje reťazec 'abaa'. Zrejme samotný koreň reprezentuje prázdne slovo a jeho dvaja synovia Koren.P['a'] a Koren.P['b'] reprezentujú jednoznakové reťazce 'a' a 'b'. Vrcholy v druhej úrovni, t.j. štyria synovia vrcholov Koren.P['a'] a Koren.P['b'] reprezentujú všetky 4 dvojpísmenové slová: 'aa', 'ab', 'ba', 'bb', atď.

Takáto štruktúra sa najčastejšie používa na evidovanie slovníkov, usporiadaných tabuliek (tabuľka symbolov), frekvenčné tabuľky a pod. V takejto štruktúre sa dá veľmi rýchlo nájsť nielen konkrétne slovo, ale vieme veľmi rýchlo vytvoriť celú množinu slov so zadaným prefixom (preto prefixový strom). V každom vrchole sa bude strom rozvetvovať na toľko podstromov (árnosť stromu), koľko rôznych písmen budeme akceptovať. Preto

  • lexikografické stromy sú N-árne stromy
  • každý vrchol reprezentuje prvých K znakov z nejakého slova (K je vzdialenosť od koreňa), ktoré je zložené z N-prvkovej množiny písmen
  • v Info položke môžeme uchovávať informáciu rôzneho typu, napr. počet výskytov daného slova, reťazec reprezentujúci preklad, kód prekladu v encyklopédii, atď.



Príklad: frekvenčná tabuľka


Budeme riešiť takúto úlohu: na vstupe je daná množina slov z abecedy {a, b}. Takýchto slov môže byť aj niekoľko stotisíc a my potrebujeme vedieť, koľkokrát sa nachádza každé slovo v tejto množine. Preto

  • najprv vytvoríme lexikografický strom - do Info budeme ukladať počet výskytov každého slova
  • potom vypíšeme všetky slová zo stromu, t.j. vypíšeme všetky cesty k vrcholom, ktoré majú nenulový počet výskytov

Riešenie: 

type
  TLexStrom = class
    Pocet: Integer;
    P: array ['a'..'b'] of TLexStrom;
    constructor Create;
    procedure Pridaj(const S: string);
    function Vypis(const Pre: string): string;
  end;
 
constructor TLexStrom.Create;  // takýto Create, ktorý iba nuluje, je zbytočný
begin
  Pocet := 0;
  P['a'] := nil;
  P['b'] := nil;
end;
 
procedure TLexStrom.Pridaj(const S: string);
begin
  if S = '' then
    Inc(Pocet)
  else if S[1] in ['a', 'b'] then
  begin
    if P[S[1]] = nil then
      P[S[1]] := TLexStrom.Create;
    P[S[1]].Pridaj(Copy(S, 2, MaxInt));
  end
  else
    raise Exception.Create('chybný znak: ' + S[1]);
end;
 
function TLexStrom.Vypis(const Pre: string): string;
var
  Z: Char;
begin
  if Pocet = 0 then
    Result := ''
  else
    Result := IntToStr(Pocet) + ' ' + Pre + #13#10;
  if P['a'] <> nil then
    Result := Result + P['a'].Vypis(Pre + 'a');
  if P['b'] <> nil then
    Result := Result + P['b'].Vypis(Pre + 'b');
end;
 
// hlavný program
 
var
  L: TLexStrom;
begin
  L := TLexStrom.Create;
  L.Pridaj('abaa');
  L.Pridaj('bb');
  L.Pridaj('');
  L.Pridaj('aaaaaaaaaaaaaaaaaaaaaaaaaaaa');
  L.Pridaj('abaabba');
  L.Pridaj('abaabab');
  L.Pridaj('aabb');
  L.Pridaj('abab');
  L.Pridaj('aabb');
  L.Pridaj('abaa');

  WriteLn(L.Vypis(''));
end.

Môžete experimentovať s aplikáciou, ktorá nakreslí lexikografický strom P29.4.zip a dovolí pridávať slová z abecedy {a, b}.

Ďalšie námety:

  • Pridaj aj Vypis sú rekurzívne a preto pri nich môže pretiecť zásobník - prerobte ich bez rekurzie
  • zadefinujte metódu Hladaj, ktorá nájde vrchol v strome pre zadané slovo - realizujte rekurzívne aj nerekurzívne
  • dorobiť pre N-prvkovú abecedu
  • premyslite situáciu, keď slová budú zložené len z písmen 'a', 'e', 'i', 'o', 'u', 'y' a teda chceme vytvoriť 6-árny strom
  • napíšte metódy triedy, ktoré nájdu
    • slová danej dĺžky
    • najkratšie, najdlhšie slová
    • najkratšie slovo začínajúce daným reťazcom
    • dĺžka najdlhšieho slova = hĺbka stromu
  • navrhnite metódy na rušenie slova alebo všetkých slov, ktoré začínajú nejakým reťazcom
  • lexikografický strom vytvárať v binárnom súbore (namiesto smerníkov budú Seek-adresy viet a nil nech je 0)
  • pomocou lexikálneho stromu reprezentujte množiny slov nad nejakou abecedou (namiesto stavovej premennej Pocet bude informácia o tom, či dané slovo patrí do množiny) => zrealizujte operácie zjednotenia, prieniku, rozdielu množín



Príklad: slovník


Sila lexikografického stromu sa najlepšie ukáže pri spracovávaní veľkého slovníka: Najprv prečítame niekoľko tisícový zoznam slov (z nejakej časti slovníka slovenského jazyka), uložíme ich do lexikografického stromu, ktorý sme pripravili pre 26 písmen abecedy (predpokladáme, že slová neobsahujú diakritiku). Zároveň pri ukladaní slov pre každý vrchol uchovávame aj informáciu, koľko slov "prechádza" cez každý vrchol (stavová premenná Prefix): tým získame počítadlo predpôn, t.j. pre každý reťazec písmen sa automaticky v slovníku nachádza aj počet slov, ktoré začínajú týmto reťazcom. 

type
  TLexStrom = class
    Pocet, Prefix: Integer;
    P: array ['a'..'z'] of TLexStrom;
    function Pridaj(const Slovo: string): Boolean;
    function PocetSlov: Integer;
    function Hladaj(const Slovo: string): TLexStrom;
    function Vypis(const Pre: string): string;
    function PocetVrcholov: Integer;
    function PocetDlzky(N: Integer): Integer;
    function Hlbka: Integer;
  end;

Vidíme, že strom je 26-árny a preto bude každý vrchol takéhoto stromu zaberať v pamäti minimálne 112 bajtov (napr. pre 10000 vrcholov to bude viac ako megabajt). Uvádzame niekoľko užitočných metód (počet slov v slovníku, počet vrcholov celého stromu, hĺbka stromu, t.j. dĺžka najdlhšieho slova a pod.). Všimnite si metódu Pridaj, ktorá je logickou funkciou a vráti hodnotu True, len ak sa tam takéto slovo ešte nenachádzalo. Potrebujeme to preto, aby sme korektne počítali počet prefixových slov (v premennej Prefix) aj ak by sme do slovníka zaraďovali to isté slovo aj viackrát. 

function TLexStrom.Pridaj(const Slovo: string): Boolean;
begin
  Result := True;
  if Slovo = '' then
    if Pocet = 0 then
      Pocet := 1
    else
      Result := False
  else if Slovo[1] in ['a'..'z'] then
  begin
    if P[Slovo[1]] = nil then
      P[Slovo[1]] := TLexStrom.Create;
    Result := P[Slovo[1]].Pridaj(Copy(Slovo, 2, MaxInt));
  end
  else
    raise Exception.Create('chybný znak: ' + Slovo[1]);
  if Result then
    Inc(Prefix);
end;
 
function TLexStrom.Hladaj(const Slovo: string): TLexStrom;
begin
  if Slovo = '' then
    Result := Self
  else if Slovo[1] in ['a'..'z'] then
  begin
    if P[Slovo[1]] = nil then
      Result := nil
    else
      Result := P[Slovo[1]].Hladaj(Copy(Slovo, 2, MaxInt));
  end
  else
    raise Exception.Create('chybný znak: ' + Slovo[1]);
end;
 
function TLexStrom.PocetSlov: Integer;
var
  Z: Char;
begin
  Result := Pocet;
  for Z := 'a' to 'z' do
    if P[Z] <> nil then
      Inc(Result, P[Z].PocetSlov);
end;
 
function TLexStrom.PocetDlzky(N: Integer): Integer;  // počet slov dĺžky N
var
  Z: Char;
begin
  if N = 0 then
    Result := Pocet
  else
  begin
    Result := 0;
    for Z := 'a' to 'z' do
      if P[Z] <> nil then
        Inc(Result, P[Z].PocetDlzky(N - 1));
    end;
end;
 
function TLexStrom.PocetVrcholov: Integer;
var
  Z: Char;
begin
  Result := 1;
  for Z := 'a' to 'z' do
    if P[Z] <> nil then
      Inc(Result, P[Z].PocetVrcholov);
end;
 
function TLexStrom.Hlbka: Integer;
var
  Z: Char;
begin
  Result := 0;
  for Z := 'a' to 'z' do
    if P[Z] <> nil then
      Result := Max(Result, P[Z].Hlbka + 1);
end;
 
function TLexStrom.Vypis(const Pre: string): string;
var
  Z: Char;
begin
  if Pocet = 0 then
    Result := ''
  else
    Result := Pre + ' ';   // alebo #13#10;
  for Z := 'a' to 'z' do
    if P[Z] <> nil then
      Result := Result + P[Z].Vypis(Pre + Z);
end;

Všimnite si, že všetky metódy sú rekurzívne, ale jedine Hladaj by sa dala jednoducho (bez pomocného zásobníka) prepísať na nerekurzívny tvar.

Môžete si stiahnuť aplikáciou P29.5.zip a otestovať načítaný slovník slovenských slov (vyše 216 000 slov). Táto aplikácia pre zadaný prefix (predponu slova) zistí, koľko slov v slovníku má tento prefix a ak ich nie je priveľa, tak ich všetky vypíše.


Komponent TreeView

Tento vizuálny komponent umožňuje zobraziť údaje, ktoré majú stromovú štruktúru, vo vizuálnej forme, napr.

...

Komponent TreeView je dosť komplexný - tu popíšeme len niekoľko stavových premenných (property) a niekoľko metód:

  • vrcholmi stromu sú inštancie triedy TTreeNode
  • trieda TTreeView má tieto metódy a premenné (property):
  • Items[i] - vráti í-ty vrchol (sú číslované od 0)
  • Items.Count - počet synov
  • Items.Add(vrchol, reťazec) - vrcholu pridá nového brata s daným textom - reťazcom
  • Items.AddFirst(vrchol, reťazec) - ako Add - pridá nového brata, ktorý sa stane prvým synom ich otca
  • Items.AddChild(vrchol, reťazec) - vrcholu pridá nového syna s daným textom - reťazcom (podobne aj AddChildFirst)
  • LoadFromFile(meno_súboru) - z textového súboru načíta kompletný strom - každý riadok popisuje jeden vrchol stromu, počet medzier, resp. tabulátorov na začiatku riadka vyjadruje "vnorenie" vrcholu
  • SaveToFile(meno_súboru) - vytvorí textový súbor, ktorý popisuje kompletný strom
  • Items.Delete(vrchol) - vyhodí vrchol zo stromu
  • GetNodeAt(X, Y) - vráti vrchol (ak existuje), ktorý je zobrazený na súradniciach (X, Y)

Aj samotný vrchol - TTreeNode má svoje užitočné stavové premenné (property), napr.

  • Count - počet synov
  • Item[i] - smerník na í-teho syna (je to tiež TTreeNode)
  • Parent - smerník na otca (je to tiež TTreeNode)
  • Selected - či je/má byť označený - označený môže byť maximálne jeden vrchol v celom strome
  • Index - koľký je to syn svojho otca
  • Level - v akej úrovni stromu je tento vrchol
  • Text - textový reťazec v danom vrchole

a niektoré dôležité metódy, napr.

  • Delete - zruší vrchol
  • DeleteChildren - zruší všetky deti
  • GetNextSibling - nasledujúci brat
  • GetPrevSibling - predchádzajúci brat
  • GetFirstChild - prvý syn

napr. táto časť programu vytvorí strom s 3 vrcholmi: 

var
  k, v1, v2: TTreeNode;
begin
  k := TreeView1.Items.Add(nil, 'koreň stromu');
  v1 := TreeView1.Items.AddChild(k, 'druhý vrchol');
  v2 := TreeView1.Items.Add(v1, 'tretí vrchol');
//  v2 := TreeView1.Items.AddChild(k, 'tretí vrchol');
             // to je to isté ako predchádzajúci riadok



Malý testovací projekt


Do formulára položte tieto komponenty:

  • TTreeView z palety Common Controls
  • TEdit
  • 2-krát TButton s popismi "Pridaj" a "Pridaj syna"
  • TCheckBox' s popisom "Pridávaj na začiatok"

projekt: 

procedure TForm1.FormCreate(Sender: TObject);
begin
  if FileExists('strom.txt') then
    TreeView1.LoadFromFile('strom.txt');
end;
 
procedure TForm1.FormClose(Sender: TObject; var Action: TCloseAction);
begin
  TreeView1.SaveToFile('strom.txt');
end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  Sel, Novy: TTreeNode;
begin
  if Edit1.Text = '' then
    Exit;
  Sel := TreeView1.Selected;
  if CheckBox1.Checked then
    Novy := TreeView1.Items.AddFirst(Sel, Edit1.Text)
  else
    Novy := TreeView1.Items.Add(Sel, Edit1.Text);
  Novy.Selected := True;
  TreeView1.SetFocus;
  Edit1.Text := '';
end;
 
procedure TForm1.Button2Click(Sender: TObject);
var
  Sel, Novy: TTreeNode;
begin
  if Edit1.Text = '' then
    Exit;
  Sel := TreeView1.Selected;
  if CheckBox1.Checked then
    Novy := TreeView1.Items.AddChildFirst(Sel, Edit1.Text)
  else
    Novy := TreeView1.Items.AddChild(Sel, Edit1.Text);
  Novy.Selected := True;
  TreeView1.SetFocus;
  Edit1.Text := '';
end;

Tento projekt si môžete stiahnuť P29.6.zip.

Ďalšie námety:

  • vytvorte TreeView zo štruktúry adresárov nejakého disku


späť | ďalej
Zdroj: „http://pascal.input.sk/index.php?title=29.Prednaska&oldid=1300“