Stromovej dátové štruktúry

Binárne vyhľadávacie stromy sú dátovou štruktúrou veľmi obvyklú a nakoniec aj veľmi praktickú. Slúži k efektívnemu vyhľadávaniu, triedenie, ukladanie a mazanie dát. Jedná sa o štruktúru dynamickú, tzn. vzniká "za behu programu".

Binárne stromy

Binárne stromy všeobecne sú stromy, ktoré majú koreň a každý uzol má najviac dva potomkov (od toho sú binárne). V každom uzle je potom uložený práve jeden prvok. Tie sú buď ďalším uzlom, alebo tzv. null - nič. Uzol môže mať i len jedného potomka. Pokiaľ má strom veľa jednopotomkových uzlov okrem posledného poschodia, hovoríme, že strom nie je vyvážený, viď ďalej.

Na príkladoch si uvedieme, ako rôzne binárne stromy vyzerajú.

Halda

Halda je vyváženým binárnym stromom. To znamená, že je takmer celý zaplnený. V halde platí tzv. Vlastnosť haldy, ktorá hovorí: "Pre každý uzol platí, že jeho rodič nesie rovnakú alebo vyššiu hodnotu než je on sám". Halda si teda v koreni udržuje maximum alebo minimum, tu hodnota 10. Ak by sme vytvorili minimálnu haldu, platilo by obdobne, že rodič nesie rovnakú alebo vyššiu hodnotu ako je uzol sám.

Nevyvážený strom

Dátová štruktúra na obrázku je stále binárnym stromom, aj keď extrémne nevyváženým. Tam, kde nič nie je, je hodnota null. Tu je to naozaj veľmi nešťastný strom, ktorý svojím usporiadaním prvkov stráca všetky výhody a degradoval do spojovaceho zoznamu. V takom stromu si napr. Pri vyhľadávaní nemôžeme skrátiť cestu žiadnu odbočkou na inú vetvu, ale musíme prejsť všetky uzly v celom stromu. Na záver článku si ukážeme, ako sa tohto stavu vyvarovať.

Vyvážený binárny vyhľadávací strom

Binárny vyhľadávací strom (anglicky alebo niekedy tiež skrátene BST ako Binary Search Tree) sa už reálne používa pre efektívnu prácu s dátami. Oproti halde má presne dané, kde aký prvok leží. Presnejšie pravá vetva vždy obsahuje prvky väčšia ako hodnota daného uzla, ľavá vetva potom prvkami menej ako hodnota daného uzla. Kompletné definíciu a implementáciu nájdete v lekcii Binárny vyhľadávací strom (BST).

Algoritmus vyhľadávanie v BST

V čom je BST teda efektívnejšie, než spájať zoznam? Povedzme, že vo stromu na obrázku chceme vyhľadať napr. Hodnotu 7. Reálne by v strome samozrejme nebolo uložené len číslo 7, ale napríklad celá štruktúra užívateľov s ID 7. Začneme v koreni stromu. Vďaka definíciu BST vieme, že ak uzol už rovno neobsahuje nami hľadaný prvok, môže tento prvok byť vždy len v jednej z vetiev uzla (pretože je buď menšia alebo väčšia ako hodnota v uzle). Jednu z vetve teda vždy úplne ignorujeme a ak je strom dobre vyváženie, odhodíme tak vždy polovicu prvkov daného podstromu. Naša časová zložitosť tak bude logaritmické so základom 2 (log n).

Postup pre vyhľadanie prvku 7 pre strom vyššie je nasledujúci:

• Začneme v koreni, kde je číslo 5.
• Je 7 presne 5 ? => NIE. Ak by už uzol nemal žiadne potomkov, prvok by v strome jednoducho nebol. Koreň má však 2 potomkov. Keďže 7 je väčšia ako 5, potrebujeme prejsť do pravej vetvy, v ktorej sú väčšie čísla.
• Je 7 presne 8 ? => NIE, je 7 väčšia než 8 => Nie, choď doľava.
• Je 7 presne 6 ? => NIE, je 7 väčší ako 6 => Áno, choď doprava.
• Je 7 presne 7 ? => ANO. Máme nájdené, otvoríme si šampaň!

Prvok sme našli v 4 krokoch, aj keď strom má prvkov 11. Väčšinu sme ich teda preskočili a vďaka zažazení podľa veľkosti s nimi vôbec pracovala pre vás.

Porovnanie BST a polia

V čom sa líši strom od poľa? Jednak tým, že pole máme alokovanej staticky. Vopred musíme vedieť, ako je veľké. Ak by sme však mali zotriedený list, dynamickú dátovú štruktúru, aké má strom prednosti? Prečo si pridávať prácu s jeho pochopením? Ukážme si tabuľku časových zložitosťou operácií nad poľom, setříděným poľom a BST:

• Dáta v tabuľke platia za predpokladu, že je strom vyvážený

  ** len ak nebudeme kopírovať celé pole a len necháme prázdne pole

Binárne strom má tú výhodu, že sa dá veľmi dobre rozšíriť podľa potrieb. V uzle môžem mať schované napr. Celé ďalšie štruktúry, ktoré sú do stromu navěšené podľa nejakej ich vlastnosti (ID, meno používateľa a podobne).

Samovyvažovacie stromy

BST strom si síce pekný, ale nikto nám u neho nazaručí, že po určitom počte operácií nezdegeneruje do príliš nevyváženého stromu alebo dokonca do štruktúry pripomínajúce spájať zoznam.

Sľúbil som, že sa pozrieme ešte na to, ako vzniká a ako zabrániť tomu, aby vznikol tak hlúpy strom ako je ten hore - iba cesta. Skúste si len tak pridávať do stromu prvky v rastúcom poradí. Každý prvok bude väčší ako ten predchádzajúci -> celý strom bude rásť iba doprava. Preto sa hodí stavať strom z neseřazeného poľa, kam ste len tak bez ladu a skladu sypali vlastnej hodnoty a strom je sám zotriedi ako sa do neho vkladajú. Akonáhle už máte zotriedené poľa, zamiešajte ho Že to nie je moc dobrá rada, čo s defektami spôsobenými za života stromu pridávaním ďalších prvkov? Neexistuje nič elegantnejšieho? existuje Sú to tzv. Samovyvažovacie stromy. Je to typ binárnych stromov, ktoré majú funkcie navyše, ktoré kontrolujú, či nie sú príliš nevyvážené, napr. Červeno-čierne stromy, AVL-stromy a ďalšie.

AVL strom

AVL strom si udržuje tú vlastnosť, že v každom vrchole sa hĺbka jeho ľavého a pravého podstromu líšia najviac o jedna. Táto podmienka zabezpečí, že strom nemôže príliš zdegenerovať, na rozdiel od bežného binárneho stromu, ktorý môže skončiť ako lineárne spájať zoznam. Viac o AVL stromu nájdete v článku AVL strom.

B-stromy

B-stromy (nepliesť s binárnymi stromy!) Sa od väčšiny ostatných stromov líšia v tom, že v ich uzloch možno uložiť viac ako jeden prvok. Boli vytvorené najmä pre efektívne využitie na pevných diskoch, kedy možno v jednom kroku pracovať s viacerými prvkami naraz. Pre túto vlastnosť sú často prakticky využívané v databázových systémoch. Čo sa týka časovej zložitosti, tak vychádzajú rovnako ako binárny stromy. B-stromom sa venuje článok B-stromy.

Záver

Ak sa vám stromami zrúti pod rukami, je to veľmi bežná prax. Je to rozhodne zložitejšie časť programovania a či postavíte strom bez chyby na prvýkrát, niekde v ňom chybu pravdepodobne máte Len ešte neprišiel hodnota, ktorá by vám strom zničila.