Lekce 5 - Stromové datové struktury

V minulé lekci, Fronta a zásobník, jsme si ukázali, jak fungují datové struktury fronta a zásobník, k čemu se v praxi používají, a jaké časové složitosti mají jejich operace.

Binární vyhledávací stromy jsou datovou strukturou velmi obvyklou a nakonec i velmi praktickou. Slouží k efektivnímu vyhledávání, třídění, ukládání a mazání dat. Jedná se o strukturu dynamickou, tzn. vzniká "za běhu programu".

Binární stromy

Binární stromy obecně jsou stromy, které mají kořen a každý uzel má nejvýše dva potomky (od toho jsou binární). V každém uzlu je potom uložený právě jeden prvek. Ty jsou buď dalším uzlem, nebo tzv. null – nic. Uzel může mít i jen jednoho potomka. Pokud má strom hodně jednopotomkových uzlů kromě posledního patra, říkáme, že strom není vyvážený, viz dále.

Na příkladech si uvedeme, jak různé binární stromy vypadají.

Halda

Halda je vyváženým binárním stromem. To znamená, že je téměř celý zaplněný. V haldě platí tzv. vlastnost haldy, která říká:

Pro každý uzel platí, že jeho rodič nese stejnou nebo vyšší hodnotu, než je on sám.

Halda si tedy v kořeni udržuje maximum nebo minimum, zde hodnota 10. Pokud bychom vytvořili minimální haldu, platilo by obdobně, že rodič nese stejnou nebo vyšší hodnotu než je uzel sám.

Nevyvážený strom

Datová struktura na obrázku je stále binárním stromem, i když extrémně nevyváženým. Tam, kde nic není, je hodnota null. Zde je to opravdu velmi nešťastný strom, který svým uspořádáním prvků ztrácí veškeré výhody a degradoval do spojového seznamu. V takovém stromu si např. při vyhledávání nemůžeme zkrátit cestu žádnou odbočkou na jinou větev, ale musíme projít všechny uzly v celém stromu. Na závěr lekce si ukážeme, jak se tohoto stavu vyvarovat.

Vyvážený binární vyhledávací strom

Binární vyhledávací strom (anglicky nebo někdy také zkráceně BST jako Binary Search Tree) se již reálně používá pro efektivní práci s daty. Oproti haldě má přesně dané, kde jaký prvek leží. Přesněji pravá větev vždy obsahuje prvky větší než hodnota daného uzlu, levá větev potom prvky menší než hodnota daného uzlu. Kompletní definici a implementaci naleznete v lekci Binární vyhledávací strom (BST).

Algoritmus vyhledávání v BST

V čem je BST tedy efektivnější, než spojový seznam? Řekněme, že ve stromu na obrázku chceme vyhledat např. hodnotu 7. Reálně by ve stromu samozřejmě nebylo uloženo jen číslo 7, ale třeba celá struktura uživatele s ID 7. Začneme v kořeni stromu. Díky definici BST víme, že pokud uzel již rovnou neobsahuje námi hledaný prvek, může tento prvek být vždy jen v jedné z větví uzlu (protože je buď menší nebo větší než hodnota v uzlu). Jednu z větvi tedy vždy úplně ignorujeme a pokud je strom dobře vyvážený, odhodíme tak vždy polovinu prvků daného podstromu. Naše časová složitost tak bude logaritmická se základem 2 (log n).

Postup pro vyhledání prvku 7 pro strom výše je následující:

• Začneme v kořeni, kde je číslo 5.
• Je 7 rovno 5? => NE. Pokud by již uzel neměl žádné potomky, prvek by ve stromu jednoduše nebyl. Kořen má však 2 potomky. Jelikož 7 je větší než 5, potřebujeme přejít do pravé větve, ve které jsou větší čísla.
• Je 7 rovno 8? => NE, je 7 větší než 8 => Ne, jdi doleva.
• Je 7 rovno 6? => NE, je 7 větší než 6 => Ano, jdi doprava.
• Je 7 rovno 7? => ANO. Máme nalezeno, otevřeme si šampáňo!

Prvek jsme našli ve 4 krocích, i když strom má prvků 11. Většinu jsme jich tedy přeskočili a díky zařazení podle velikosti s nimi vůbec nepracovali.

Srovnání BST a pole

V čem se liší strom od pole? Jednak tím, že pole máme alokované staticky. Předem musíme vědět, jak je velké. Pokud bychom však měli setříděný list, dynamickou datovou strukturu, jaké má strom přednosti? Proč si přidělávat práci s jeho pochopením? Ukažme si tabulku časových složitostí operací nad polem, setříděným polem a BST:

	pole	setříděné pole	BST
najdi prvek	O(n)	O(log n)	O(log n)*
přidej prvek	O(1)	O(log n)	O(log n)*
smaž prvek	O(n)	O(log n)**	O(log n)*
vypiš všechny prvky	O(n)	O(n)	O(n)

* Data v tabulce platí za předpokladu, že je strom vyvážený.

** Jen pokud nebudeme kopírovat celé pole a necháme pole prázdné (např. tam dáme 0).

Binární strom má tu výhodu, že se dá velmi dobře rozšířit dle potřeb. V uzlu můžeme mít schované např. celé další struktury, které jsou do stromu navěšené podle nějaké jejich vlastnosti (ID, jméno uživatele a podobně).

Samovyvažovací stromy

BST strom je sice hezký, ale nikdo nám u něj nezaručí, že po určitém počtu operací nezdegeneruje do příliš nevyváženého stromu nebo dokonce do struktury připomínající spojový seznam.

Slíbil jsem, že se podíváme ještě na to, jak vzniká, a jak zabránit tomu, aby vznikl tak hloupý strom, jako je ten nahoře - pouze cesta. Zkuste si jen tak přidávat do stromu prvky v rostoucím pořadí. Každý prvek bude větší než ten předchozí -> celý strom bude růst pouze doprava. Proto se hodí stavět strom z neseřazeného pole, kam jste jen tak bez ladu a skladu sypali vlastní hodnoty a strom je sám setřídí, jak se do něj vkládají. Jakmile již máte setříděné pole, zamíchejte ho Že to není moc dobrá rada, co s defekty způsobenými za života stromu přidáváním dalších prvků? Neexistuje nic elegantnějšího? Existuje Jsou to tzv. samovyvažovací stromy. Je to typ binárních stromů, které mají funkce navíc, které kontrolují, zda nejsou příliš nevyvážené, např. červeno-černé stromy, AVL-stromy a další.

AVL strom

AVL strom si udržuje tu vlastnost, že v každém vrcholu se hloubka jeho levého a pravého podstromu liší nejvýše o jedna. Tato podmínka zajistí, že strom nemůže příliš zdegenerovat, na rozdíl od běžného binárního stromu, který může skončit jako lineární spojový seznam. Více o AVL stromu naleznete v článku AVL strom.

B-stromy

B-stromy (neplést s binárními stromy!) se od většiny ostatních stromů liší v tom, že v jejich uzlech lze uložit více než jeden prvek. Byly vytvořeny zejména pro efektivní využití na pevných discích, kdy lze v jednom kroku pracovat s více prvky najednou. Pro tuto vlastnost jsou často prakticky využívány v databázových systémech. Co se týká časové složitosti, tak vycházejí stejně jako binární stromy. B-stromům se věnuje článek B-stromy.

Závěr

Jestli se vám stromy zhroutí pod rukama, je to velmi běžná praxe. Je to rozhodně složitější část programování a jestli postavíte strom bez chyby napoprvé, někde v něm chybu pravděpodobně máte Jen ještě nepřišla hodnota, která by vám strom zničila.