9.  Stromy

9.1  Na úvod trochu teórie

Ak programátor rozmýšľa o strome, tak s veľkou pravdepodobnosťou nejde o strom listnatý, ihličnatý (ba ani vianočný :-), ale o ďalšiu dynamickú údajovú štruktúru. Pôvod pomenovania je zrejmý z grafického znázornenia tejto údajovej štruktúry:

Na obrázku vidíme príklad stromu. Aby sme boli dôslední, v skutočnosti ide vlastne o obrátený strom, ktorého koreň je na vrchu a konáre s listami rastú smerom nadol. Pre strom ako údajovú štruktúru je však táto orientácia vhodnejšia.

  So stromami sa stretávame pomerne často. Uvedieme niekoľko príkladov: strom adresárov na disku počítača, strom hypertextových odkazov v tejto učebnici (pozri vľavo :-), rozhodovací strom (od jednoduchého binárneho vetvenia až po strom všetkých možností), strom odvodenia a pod. Pomocou stromu vždy vyjadrujeme určitú hierarchickú štruktúru, vzájomné vzťahy objektov. Dobrým príkladom zo života môže byť strom, v ktorom sa nachádzajú všetci zamestnanci firmy - v koreni je generálny riaditeľ, nižšiu úroveň tvoria vedúci oddelení, každému z nich podliehajú ďalší pracovníci atď.

Na obrázku je graf - vrcholy pospájané hranami (orientovanými). V teórii grafov stromom rozumieme súvislý orientovaný graf, v ktorom neexistujú cykly. Existuje práve jeden vrchol, do ktorého nevstupuje žiadna hrana - koreň a do každého iného vrcholu vstupuje práve jedna hrana. Pre jednotlivé vrcholy sa používa rodinná terminológia:

• Ak z vrcholu v idú hrany do vrcholov w1 a w2, tak hovoríme, že w1 a w2 sú bratia a sú synmi vrcholu v (je ich otec)
Ak existuje cesta z vrcholu v do vrcholu w, tak vrchol v nazývame predkom vrcholu w a vrchol w nazývame potomkom vrcholu v
• Každý vrchol so všetkymi svojimi potomkami tvorí podstrom (s koreňom v)
• Vrcholy, ktoré majú synov, sa nazývajú vnútorné, vrcholy bez synov sú listy

V "našom" strome sú napr. vrcholy d, e bratia, sú synmi vrcholu b. Vrchol h je potomkom vrcholu b, koreň stromu - vrchol a je predkom všetkých ostatných vrcholov. Vrcholy d, h, i, g sú listy.

Usporiadaný strom je taký, v ktorom synovia každého vrcholu tvoria usporiadanú množinu (je medzi nimi stanovené poradie).

Počet priamych potomkov vnútorného vrcholu nazývame jeho stupňom. Maximálny stupeň spomedzi všetkých vrcholov určuje stupeň stromu.

Binárny strom (binary tree), je taký strom, v ktorom má každý vrchol najviac dvoch synov, pričom je určené, ktorý syn je ľavý a ktorý pravý. Binárny strom je teda usporiadaný strom druhého stupňa. Aj "náš" strom je binárny!

Viaccestný strom je strom so stupňom vyšším ako 2. My sa budeme ďalej zaoberať len binárnymi stromami.