IB111 Programování a algoritmizace Datové struktury II Stromy Struktura stromu Strom Acyklická struktura, kde každý uzel kromě kořene má právě jednoho rodiče Kořen, uzel, list Rodič, dítě Výška stromu Hloubka uzlu Vstupní stupeň uzlu Pro kořen je nulová Výstupní stupeň uzlu Binární stromy Binární strom je strom, kde každý uzel má maximálně 2 děti Binární vyhledávací stromy Binární stromy Pro každý uzel x platí, že uzly v levém podstromě uzlu x mají klíč menší nebo roven x a uzly v pravém podstromě mají klíč větší nebo roven uzlu x. Implementace Jak implementovat binární stromy? Implementace Jak implementovat binární stromy? struct BinTreeNode { int key; struct BinTreeNode *left, *right; // struct BinTreeNode *parent; } struct BinTreeNode *root = NULL; Operace nad binárními stromy Nad binárními vyhledávacími stromy provádíme především vyhledávání Ostatní operace Přidání prvku Smazání prvku Výpis prvků (inorder, preorder, postorder) Nalezení minimálního a maximálního prvku Vyhledání prvku Začneme v kořeni a pokračujeme dolů Porovnáme klíč uzlu s hledanou hodnotou Je roven ­ našli jsme Hledaná hodnota je menší ­ pokračujeme levým podstromem Hledaná hodnota je větší ­ pokračujeme pravým podstromem Složitost je dána výškou (hloubkou) stromu Výpis prvků binárního stromu Inorder verze Vypiš prvky v levém podstromu (existuje-li) Vypiš procházený uzel Vypiš prvky v pravém podstromu (existuje-li) Postorder (levý, pravý, aktuální) Preorder (aktuální, levý, pravý) Minumum a maximum Nalezení minimální hodnoty sledujeme levé podstromy Nalezení maximální hodnoty Sledujeme pravé podstromy Přidání prvku Vytvoříme nový uzel a zařadíme jej tak, aby stále platily podmínky binárního vyhledávacích stromů Odebrání prvku 3 případy: Uzel nemá děti rovnou smažeme Uzel má právě jedno dítě (levé nebo pravé) nahradíme uzel, které máme smazat tímto dítětem Uzel má dvě děti najdeme minimální hodnotu v pravém podstromu, tento uzel smažeme a jeho hodnotou přepíšeme uzel, který jsme chtěli odstranit. Odebrání prvku ­ ilustrace 1 Odebrání prvku ­ ilustrace 2 Odebrání prvku ­ ilustrace 3 Časová náročnost Vyhledávání, přidávání i odebírání prvků má časovou náročnost O(h), kde h je výška stromu V ideálním případě je výška stromu rovna log2 n, kde n je počet uzlů V nejhorším případě je výška stromu rovna n, kde n je počet uzlů Degenerovaný strom, vlastně zřetězený seznam Výška stromu Strom je vyvážený, pokud až na poslední úroveň je strom ,,zaplněný". Strom je kompletní, pokud je vyvážený a poslední úroveň se plní postupně zleva doprava. Optimální binární vyhledávací stromy Optimální binární vyhledávací stromy průměrná doby vyhledání je minimalizována Uzly jsou uspořádány tak, aby u často vyhledávaných položek byla cesta z kořene krátká Potřebujeme znát četnosti vyhledávání jednotlivých prvků AVL stromy Vyvážené binární vyhledávací stromy, toto vyvážení se neustále udržuje i při operacích přidávání a odebírání prvků 1962: G.M. Adelson-Velskii a E.M. Landis Faktor vyvážení Výška jednoho podstromu MINUS výška druhého podstromu Uzel je vyvážený, pokud má faktor -1, 0, 1 Operace na AVL stromech jsou stejné jako u normálních binárních vyhledávacích stromů, ale pokud po operaci nejsou všechny uzly vyváženy je potřeba provést dodatečné vyvážení pomocí rotací stromů. Rotace stromů Vkládání Vložíme uzel a kontrolujeme faktor vyváženosti všech předchůdců Pokud -1, 0, +1 pak OK Pokud +2 pak kontrolujeme faktor pravého dítěte Pokud +1 levá rotace Pokud -1 dvojitá levá rotace (pravá, pak levá) Pokud -2 pak kontrolujeme faktor levého dítěte Pokud -1 pravá rotace Pokud +1 dvojitá pravá rotace (levá, pak pravá) Rotace stromu Odstranění uzlu Obdobné jako při vkládání Navíc další případy Faktor vyváženosti uzlu je 2 Faktor vyváženosti pravého dítěte 0 levá rotace Faktor vyváženosti uzlu je -2 Faktor vyváženosti levého dítěte je 0 pravá rotace AVL stromy Časová náročnost operací je stejná jako u operací s binárními vyhledávacími stromy, tj. O(h), kde h je výška stromu Vyvažování stromů tedy asymptotickou časovou náročnost nezvyšuje ALE výška h stromu je u AVL stromů vždy logaritmická, tedy i náročnost operací je logaritmická Příští přednáška Následuje cvičení v B311 v 14:00 Příští přednáška 20.10.2009 v B410 od 12:00