Tímto článkem zahajuji sérii článků o známých i méně známých datových strukturách a také o jejich aplikaci v praxi.

Ve svých článcích poskytnu příklady kódu ve dvou jazycích najednou: Java a Haskell. Díky tomu bude možné porovnat imperativní a funkcionální styly programování a vidět klady a zápory obou.

Rozhodl jsem se začít s binárními vyhledávacími stromy, protože se jedná o docela základní, ale zároveň zajímavou věc, která má také velké množství modifikací a variací a také praktických aplikací.

Proč to udělal?

Binární vyhledávací stromy se běžně používají k implementaci sad a asociativních polí (například sada a mapa v C++ nebo TreeSet a TreeMap v jazyce Java). Složitější aplikace zahrnují lana (o kterých budu hovořit v příštím článku), různé algoritmy výpočetní geometrie, zejména algoritmy založené na scanline.

V tomto článku budou stromy zkoumány na příkladu implementace asociativního pole. Asociativní pole je zobecněné pole, ve kterém mohou být indexy (obvykle nazývané klíče) libovolné.

No, pojďme začít

Binární strom se skládá z vrcholů a spojení mezi nimi. Přesněji řečeno, strom má vyhrazený kořenový vrchol a každý vrchol může mít levé a pravé potomky. Slovy to zní poněkud složitě, ale když se podíváte na obrázek, je vše jasné:

Kořenem tohoto stromu bude vrchol A. Je vidět, že vrchol D nemá levého syna, vrchol B nemá pravého syna a vrcholy G, H, F a I mají oba. Vrcholy bez synů se obvykle nazývají listy.

Každý vrchol X může být spojen s vlastním stromem, který se skládá z vrcholu, jeho synů, synů jeho synů atd. Takový strom se nazývá podstrom s kořenem X. Levý a pravý podstrom X jsou podstromy zakořeněné v levém a pravém synu X. Všimněte si, že takové podstromy mohou být prázdné, pokud X nemá odpovídajícího syna.

Data ve stromu jsou uložena v jeho vrcholech. V programech jsou vrcholy stromu obvykle reprezentovány strukturou, která ukládá data a dva odkazy na levé a pravé potomky. Chybějící vrcholy jsou označeny hodnotou null nebo speciálním konstruktorem Leaf:

data Ord key => BSTree key value = Leaf | Branch key value (BSTree key value) (BSTree key value) deriving (Show) 
static class Node < T1 key; T2 value; Nodeleft, right; Node(T1 key, T2 value) < this.key = key; this.value = value; >> 

Jak můžete vidět z příkladů, požadujeme, aby klíče byly vzájemně srovnatelné (Ord a v Haskell a T1 implementuje Comparable v Javě). To vše není jednoduché – aby byl strom užitečný, musí v něm být uložena data podle nějakých pravidel.

ČTĚTE VÍCE
Jak oplodnit Cymbidium?

Jaká jsou tato pravidla? Je to jednoduché: pokud vrchol X ukládá klíč x, pak by měl levý (pravý) podstrom ukládat pouze klíče menší (respektive větší) než x. Pojďme si to ilustrovat:

Co nám toto uspořádání dává? Skutečnost, že požadovaný klíč x snadno najdeme ve stromu! Stačí porovnat x s hodnotou v kořenu. Pokud jsou si rovni, pak jsme našli to, co potřebujeme. Pokud je x menší (větší), pak může být pouze v levém (respektive pravém) podstromu. Hledejme například číslo 17 ve stromu:

Funkce, která získá hodnotu klíčem:

get :: Ord key => BSTree key value -> key -> Maybe value get Leaf _ = Nothing get (Branch key value left right) k | k < key = get left k | k >key = get right k | k == key = Just value 
public T2 get(T1 k) < Nodex = root; while (x != null) < int cmp = k.compareTo(x.key); if (cmp == 0) < return x.value; >if (cmp < 0) < x = x.left; >else < x = x.right; >> return null; > 

Přidat do stromu

Nyní zkusme operaci přidání nového páru klíč/hodnota (a,b). Abychom to udělali, půjdeme dolů po stromu jako ve funkci get, dokud nenajdeme vrchol se stejným klíčem, nebo nedosáhneme chybějícího syna. Pokud najdeme vrchol se stejným klíčem, pak jednoduše změníme odpovídající hodnotu. Jinak je snadné pochopit, že právě do tohoto místa by měl být vložen nový vrchol, aby nedošlo k narušení pořádku. Zvažte vložení klíče 42 do stromu na předchozím obrázku:

add :: Ord key => BSTree key value -> key -> value -> BSTree key value add Leaf k v = Branch k v Leaf Leaf add (Branch key value left right) k v | k < key = Branch key value (add left k v) right | k >key = Branch key value left (add right k v) | k == key = Branch key value left right 
public void add(T1 k, T2 v) < Nodex = root, y = null; while (x != null) < int cmp = k.compareTo(x.key); if (cmp == 0) < x.value = v; return; >else < y = x; if (cmp < 0) < x = x.left; >else < x = x.right; >> > Node newNode = new Node(k, v); if (y == null) < root = newNode; >else < if (k.compareTo(y.key) < 0) < y.left = newNode; >else < y.right = newNode; >> > 

Pokud se pozorně podíváte na příklady v obou jazycích, můžete vidět určité rozdíly v chování funkčních a imperativních implementací: pokud v jazyce Java jednoduše upravíme data a odkazy v existujících vrcholech, pak verze Haskell vytvoří nové vrcholy podél celé cesty procházející rekurzí. Je to proto, že v čistě funkčních jazycích nemůžete dělat destruktivní úkoly. To samozřejmě snižuje výkon a zvyšuje spotřebu paměti. Na druhou stranu má tento přístup také pozitivní aspekty: absence vedlejších účinků umožňuje mnohem snadněji pochopit, jak program funguje. Více se o tom můžete dočíst téměř v každé učebnici nebo úvodním článku o funkcionálním programování.

ČTĚTE VÍCE
Jak jíst zelené fazolky?

Ve stejném článku chci upozornit na další důsledek funkčního přístupu: i po přidání nového prvku do stromu zůstane stará verze dostupná! Díky tomuto efektu fungují lana, včetně těch implementovaných v imperativních jazycích, což umožňuje implementaci řetězců s asymptoticky rychlejšími operacemi než s tradičním přístupem. O lanech vám povím v jednom z následujících článků.

Zpátky k našim ovečkám

Nyní se dostáváme k nejtěžší operaci v tomto článku – odstranění klíče x ze stromu. Pro začátek, stejně jako předtím, najdeme náš vrchol ve stromu. Nyní se objevují dva případy. Případ 1 (odstraňte číslo 5):

Je vidět, že mazaný vrchol nemá pravého syna. Pak jej můžeme odstranit a místo něj vložit levý podstrom, aniž bychom narušili pořadí:

Pokud existuje správný syn, máme případ 2 (opět odstraníme vrchol 5, ale z trochu jiného stromu):

To nepůjde tak snadno – levý syn už může mít pravého syna. Udělejme to jinak: najdi minimum ve správném podstromu. Je jasné, že se to dá najít, když začnete v pravém synovi a půjdete úplně doleva. Protože nalezené minimum nemá levého syna, můžete jej vyříznout analogicky s případem 1 a vložit jej místo smazaného vrcholu. Vzhledem k tomu, že v pravém podstromu byl minimální, nebude porušena vlastnost objednávky:

remove :: Ord key => BSTree key value -> key -> BSTree key value remove Leaf _ = Leaf remove (Branch key value left right) k | k < key = Branch key value (remove left k) right | k >key = Branch key value left (remove right k) | k == key = if isLeaf right then left else Branch leftmostA leftmostB left right' where isLeaf Leaf = True isLeaf _ = False ((leftmostA, leftmostB), right') = deleteLeftmost right deleteLeftmost (Branch key value Leaf right) = ((key, value), right) deleteLeftmost (Branch key value left right) = (pair, Branch key value left' right) where (pair, left') = deleteLeftmost left 
public void remove(T1 k) < Nodex = root, y = null; while (x != null) < int cmp = k.compareTo(x.key); if (cmp == 0) < break; >else < y = x; if (cmp < 0) < x = x.left; >else < x = x.right; >> > if (x == null) < return; >if (x.right == null) < if (y == null) < root = x.left; >else < if (x == y.left) < y.left = x.left; >else < y.right = x.left; >> > else < NodeleftMost = x.right; y = null; while (leftMost.left != null) < y = leftMost; leftMost = leftMost.left; >if (y != null) < y.left = leftMost.right; >else < x.right = leftMost.right; >x.key = leftMost.key; x.value = leftMost.value; > > 

Jako dezert pár funkcí, které jsem použil k testování:

fromList :: Ord key => [(key, value)] -> BSTree key value fromList = foldr ((key, value) tree -> add tree key value) Leaf toList :: Ord key => BSTree key value -> [(key, value)] toList tree = toList' tree [] where toList' Leaf list = list toList' (Branch key value left right) list = toList' left ((key, value):(toList' left list)) 

Jak je to všechno užitečné?

Čtenář se může divit, proč je potřeba taková složitost, když můžete jednoduše uložit seznam párů [(klíč, hodnota)]. Odpověď je jednoduchá – operace se stromem jsou rychlejší. Při implementaci jako seznam vyžadují všechny funkce akce O(n), kde n je velikost struktury. (Zápis O(f(n)) zhruba znamená „proporcionální k f(n)“; přesnější popis a podrobnosti si můžete přečíst zde). Operace se stromem fungují v O(h), kde h je maximální hloubka stromu (hloubka je vzdálenost od kořene k vrcholu). V optimálním případě, kdy je hloubka všech listů stejná, bude mít strom n=2^h vrcholů. To znamená, že složitost operací ve stromech blízkých optimu bude O(log(n)). Bohužel v nejhorším případě může strom zdegenerovat a složitost operací bude jako u seznamu, například v takovém stromě (to se stane, když vložíte čísla 1..n v pořadí):

ČTĚTE VÍCE
Kdo vynalezl skořici?

Naštěstí existují způsoby, jak implementovat strom tak, aby byla zachována optimální hloubka stromu v jakékoli sekvenci operací. Takové stromy se nazývají vyvážené. Patří sem např. červeno-černé stromy, AVL stromy, rozvětvené stromy atp.

Oznámení o dalších epizodách

V příštím článku udělám krátký přehled různých vyvážených stromů, jejich klady a zápory. V následujících článcích budu o některých (možná několika) mluvit podrobněji a s implementací. Poté budu hovořit o realizaci lan a dalších možných rozšířeních a aplikacích vyvážených stromů.

Zůstaňte v kontaktu!

Užitečné odkazy

Kompletní zdrojové kódy pro příklady:

Vřele také doporučuji přečíst si knihu od Cormena T., Leisersona Ch., Rivesta R.: „Algorithms: Construction and Analysis“, což je vynikající učebnice algoritmů a datových struktur.