Předvánoční slevová akce PHP týden
Pouze tento týden sleva až 80 % na PHP e-learning!
Využij předvánočních slev a získej od nás 20 % bodů zdarma! Více zde

Stromové datové struktury

Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem.
Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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

Datová struktura 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

Nevyvážený binární 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 článku si ukážeme, jak se tohoto stavu vyvarovat.

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

Binární vyhledávací strom BST
Tento výukový obsah pomáhají rozvíjet následující firmy, které dost možná hledají právě tebe!

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 napracovali.

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 jen necháme prázdné pole

Binární strom má tu výhodu, že se dá velmi dobře rozšířit dle potřeb. V uzlu můžu 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 si sice hezký, ale nikdo nám u něj nazaručí, ž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.

Datová struktura B-strom

Závěr

Disaster

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šela hodnota, která by vám strom zničila.


 

 

Článek pro vás napsal Tricerator
Avatar
Jak se ti líbí článek?
1 hlasů
Autor se věnuje teoretické informatice. Ve svých volných chvílích nepohrdne šálkem dobrého čaje, kaligrafickým brkem a foukací harmonice.
Předchozí článek
Fronta a zásobník
Všechny články v sekci
Datové struktury
Aktivity (3)

 

 

Komentáře

Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zatím nikdo nevložil komentář - buď první!