ADT – STROM Lukáš Foldýna – 26. 05. 2006
Stromy mají široké uplatnění jako datové struktury pro různé algoritmy. Jsou to matematické abstrakce množin, kterou v běžném životě používáme velice často. Příkladem může být rodokmen, sportovní soutěž založená na vylučovacím principu, kdy dál postupuje jeden ze soupeřů. V počítači je strom, datová struktura ,která uchovává objekty (prvky) hierarchicky ve vztahu předchůdce-následovník (otec-syn).
Příklady použití • reprezentace znalostí, stavového prostoru v umělé inteligenci • popis scény v oblasti zpracování a analýza obrazu, počítačová grafika • vyhledávací stromy v databázových systémech • rozhodovací stromy – expertní systémy • organizace adresářů a souborů v souborovém systému OS, • komprese dat (Hufmannovy kódovací stromy, fraktálová komprese)
Definice 1. Strom T je konečná množina jednoho nebo více prvků (uzlů), z nichž
jeden je označen jako root (kořen) a zbývající uzly jsou rozděleny do n≥0 disjunktních podmnožin T1,T2,…Tk, které jsou také stromy a jejichž kořeny r1,r2,…,rk jsou následníky kořene root . 2. Strom je graf, ve kterém existuje pouze jedna cesta z uzlu root
(kořene), do kteréhokoliv dalšího uzlu grafu (neobsahuje cykly)
Základní pojmy • • •
• •
• •
Kořen je uzel, který nemá předchůdce, ve stromu může být pouze jediný kořen. Listy (vnější uzly) jsou uzly, které nemají žádného následníka. Vnitřní uzly jsou uzly, které mají alespoň jednoho následníka. Cesta je posloupnost po sobě jdoucích vrcholů, které jsou spojeny hranou. Délka cesty je počet hran cesty. Délku cesty z vrcholu k sobě samému potom můžeme definovat jako nulovou. Ke každému vrcholu je z kořene právě jedna cesta. Hloubka uzlu je délka cesty od kořene do uzlu. Výška stromu je délka cesty od kořene k nejhlubšímu uzlu zvětšená o jednotku.
Základní vlastnosti • • • • • •
Prvek stromu se nazývá uzel. Není-li strom prázdný, tj. obsahuje-li alespoň jeden uzel, pak existuje právě jeden specifický uzel – kořen stromu. Mezi dvěma různými uzly může existovat vazba, pro kterou platí, že jeden z daných uzlů je otec a druhý syn. Každý uzel má právě jednoho otce. Výjimku tvoří pouze kořen, pro který žádný otec není definován. Z každého uzlu lze po vazbách navštívit libovolný jiný uzel – strom je spojitý. Začneme-li procházet od libovolného pevně daného uzlu vazby stromu ve směru od otce k synovy, nikdy nemůžeme navštívit uzel, ve kterém jsme již byli – strom neobsahuje cykly.
Typy stromů • Binární strom je kořen ,který má v každém uzlu maximálně dva syny • Plny binární strom je strom kde každý uzel má buď žádné nebo 2 siny
Kompletní binární strom je plný binární strom, který má všechny listy ve stejné hloubce • Skoro kompletní binární strom je kde každý uzel musí mí s pravým synem i levého, ale levý muže být bez pravého •
Algoritmy pro vyhledávaní a úpravu stromu • Binární vyhledávací strom pro jehož každý uzel platí, že jeho levý podstrom je buď prázdný, nebo sestává z uzlů, hodnoty jejichž klíčů jsou menší než hodnota klíče daného uzlu a podobně jeho pravý podstrom je buď prázdný, nebo sestává z uzlů, hodnoty jejichž klíčů jsou větší než hodnota klíče daného uzlu. Binární vyhledávací strom bude vypadat např. takto:
• AVL(Adelson-Velskii, Landis) strom (vyvážený strom) AVL strom je datová struktura pro uchovávání údajů a jejich vyhledávání. Pracuje v logaritmicky omezeném čase. Jedná se o samovyvažující se binární vyhledávací strom. Základní vlastnosti
Vrchol má maximálně dva následníky (je to binární strom) V levém podstromu vrcholu jsou pouze vrcholy s menší hodnotou klíče V pravém podstromu vrcholu jsou pouze vrcholy s větší hodnotou klíče Délka nejdelší větve levého a pravého podstromu se liší nejvýše o1 AVL strom bude vypadat např. takto:
•
Red-black strom Základní vlastnosti Každý uzel stromu je obarven červenou nebo černou barvou Kořen stromu je obarven červeně Listy(nil) jsou černé Červený uzel má pouze červené syny Na kterékoliv cestě z kořene do listu leží stejný počet černých uzlů Red-black strom bude vypadat např. takto:
•
Splay strom – Rozšířený binární vyhledávací strom Rozšířený binární vyhledávací strom, tzv. splay strom, je datová struktura, kterou zkonstruovali a popsali na počátku 80. let minulého století Daniel Dominic Sleator a Robert Endre Tarjan. Spay strom vychází z binárního vyhledávacího stromu. Rozšíření na binární strom provedeme aplikací následujícího pravidla: Uzel binárního stromu může mít nejvýše dva přímé potomky. Nyní vložíme další přívlastek a vzniklý pojem binární vyhledávací strom definujeme stejnými pravidly jako strom binární, avšak s přidáním posledních dvou pravidel: Každý uzel obsahuje právě jednu charakteristickou hodnotu ordinálního typu, kterou nazýváme klíč. Potomky uzlu nazveme levý syn a pravý syn. Levý syn má vždy hodnotu klíče menší než jeho otec. U pravého potomka je tomu naopak, tj. hodnotu klíče má větší než jeho otec.
Narozdíl od binárního vyhledávacího stromu se při každém přístupu do rozšířeného binárního vyhledávacího stromu provede automaticky také jistý specifický způsob přeuspořádání. Tato operace se v angličtině nazývá splay. Jejím cílem je přemístit uzel, na kterém je „splaying“ prováděn, do kořene stromu. K tomu se využívá tzv. rotace. Operace splay je pak definována jako posloupnost těchto rotací.
• B-tree B-tree je stromová datová struktura, používaná pro uchovávání dat a vyhledávání v nich. Operace přidání, vyjmutí i vyhledávání probíhají v logaritmicky omezeném čase. Tato struktura je často využívána pro databázové aplikace. Základní vlastnosti
B-strom řádu m je strom, kde každý uzel má maximálně m následníků a ve kterém platí: 1. Počet klíčů v každém vnitřním uzlu, je o jednu menší než je počet následníků (synů) 2. Všechny listy jsou na stejné úrovni (mají stejnou hloubku) 3. Všechny uzly kromě kořene mají nejméně následníků(1 klíčů) 4. Kořen je buďto list, nebo má od 2 do m následníků 5. Žádný uzel neobsahuje více než m následníků (m-1 klíčů)
