Problematika nevyvážených stromů Flashcards
(6 cards)
Problematika nevyvážených stromů
Nevyvážený strom:
Binární strom, kde výšky podstromů jednotlivých uzlů nejsou vyrovnané.
Může se zdegenerovat (např. do podoby lineárního seznamu).
Výrazně se zhoršuje výkonnost základních operací.
Strom ztrácí výhodu rychlého vyhledávání.
Strom je vyvážený, pokud pro každý uzel platí:
|výška levého podstromu − výška pravého podstromu| ≤ 1
AVL Stromy
Typ samovyvažujícího binárního vyhledávacího stromu.
Hlavní myšlenkou AVL stromu je, že po každé operaci (vkládání nebo mazání) se kontroluje tzv. vyvažovací faktor (balance factor) každého uzlu. Tento faktor určuje, jak „nevyvážený“ je daný uzel.
Výhody AVL stromu:
1) Zajišťuje, že výška stromu zůstává v O(log n), a tím pádem i efektivita operací.
2) Je deterministický – pro stejná data vytvoří stejnou strukturu.
3) Hodí se tam, kde jsou časté dotazy na vyhledávání, protože udržuje větší míru vyváženosti než např. Red-Black strom.
Nevýhody AVL stromu
1) Složitější implementace než obyčejný BST.
2) Více rotací při vkládání nebo mazání – AVL stromy jsou náročnější na údržbu (zejména u častých úprav dat).
3) Není ideální pro situace, kde se často mění struktura stromu (časté mazání/vkládání)
Red-Black Stromy
Nejsou tak dobře vyvážené jako AVL, ale řeší problém mnohonásobné rotace. Efektivní vkládání, ale méně efektivní vyhledávání. Každý uzel v Red-Black stromu je označen buď jako červený, nebo černý. Tato barva se nepoužívá ke klasifikaci dat, ale k udržování rovnováhy stromu podle několika striktních pravidel.
1) Každý uzel je buď červený, nebo černý.
2) Kořen stromu je vždy černý.
3) Všechny listy (NULL uzly, tj. prázdné potomky) jsou černé.
4) Červený uzel nemůže mít červeného potomka (žádné dvě červené po sobě).
5) Každá cesta od libovolného uzlu k jeho listům obsahuje stejný počet černých uzlů (tzv. černá výška stromu).
Po každé operaci (vkládání nebo mazání) může být některé z pravidel porušeno. Red-Black strom používá dvě hlavní techniky k obnovení rovnováhy:
1) Rotace (levá nebo pravá) – podobné jako v AVL stromech.
2) Změna barvy uzlů – efektivnější než neustálé rotace.
Rotace se používají pouze tehdy, když samotná změna barvy nestačí. Díky tomu je Red-Black strom úspornější než AVL strom z hlediska počtu nutných úprav.
Hashovací tabulka
Hashovací tabulka spojuje klíč s odpovídající hodnotou. Klíč je vypočítán z obsahu položky tak, aby byl co nejjednoznačnější a nedocházelo ke kolizím; vše vychází z pravděpodobnosti o hashovacích funkcích. Využívají se nejčastěji v databázích nebo k rychlému vyhledávaní v polích. Paměťová složitost je O(𝑛).
Při vkládání se z vkládaného prvku udělá hash. Tento hash se přiřadí do pole, na místo, které mu odpovídá. Jestliže je místo obsazeno přiřadíme mu další volné místo dle algoritmu.
Při vyhledávání využijeme klíče, který nám vrátí index položky. Jestliže na odpovídajícím indexu se nenachází daná položka, pomocí algoritmu vypočteme, kde je další místo, kde se položka může nacházet.
Hashovací tabulka - Řešení kolizí
Kolize nastává, když dva různé klíče jsou zobrazeny na stejný index (např. h(“abc”) = 5, h(“xyz”) = 5). Jelikož v každé buňce tabulky může být jen jeden záznam, musí se kolize nějak řešit.
1) Metoda Řetězení - Každá položka v tabulce ukazuje na spojený seznam (nebo jinou kolekci) všech prvků, které do daného indexu „kolidují“.
Pokud vznikne kolize, nový prvek se přidá na konec seznamu u příslušného indexu.
2) Otevřené adresování - Lineární sondování
Místo seznamu v buňce hledáme jiný volný index v tabulce podle určitého schématu. Pokud je pozice obsazená, zkoušíme postupně dál.
3) Otevřené adresování - double hashing
Pokud dojde ke kolizi, použije se druhá hasovací funkce.
Nejlepší rozptyl, ale je potřeba udržovat a navrhnout 2 hashovací funkce a je složitější implementace.
Binární strom vs AVL strom vs Hashovací tabulka
Binární vyhledávací strom (BST) je jednoduchá datová struktura, která zachovává přirozené uspořádání dat, ale bez vyvažování může mít v nejhorším případě lineární časovou složitost. Je vhodný pro situace, kde se očekává rovnoměrné vkládání a je potřeba zachovat pořadí prvků.
AVL strom je vyvažovaný binární strom, který zaručuje logaritmickou výšku i v nejhorším případě díky rotacím. Je vhodný pro scénáře, kde jsou časté vyhledávací operace a je třeba pracovat s uspořádanými daty, např. při hledání minim, maxim nebo rozsahů.
Hashovací tabulka poskytuje v průměru konstantní časové složitosti pro vyhledávání, vkládání i mazání, ale nezachovává žádné pořadí a je náchylná na kolize, které musí být řešeny. Hodí se tam, kde je klíčové rychlé mapování hodnot podle klíče a nepracuje se s intervaly nebo seřazením.
