Červeno-černý strom
Červeno-černý strom (též anglicky red-black tree) je binární vyhledávací strom. Jedná se o datovou strukturu často používanou pro implementaci asociativního pole. Autor algoritmu, Rudolf Bayer, jej nejprve nazval symetrický binární B-strom, své moderní jméno získal až v práci Lea J. Guibase a Roberta Sedgewicka z roku 1978.
Červeno-černý strom musí splňovat následující pravidla:
- Každý uzel je buď červený, nebo černý.
- Kořen je černý.
- Listy (nil) jsou pokládány za černé vrcholy.
- Každý červený vrchol má dva černé syny.
- Každá cesta z jednoho vrcholu do jeho podřízených listů obsahuje stejný počet černých vrcholů.
Související články
- AA strom
Externí odkazy
- Obrázky, zvuky či videa k tématu červeno-černý strom na Wikimedia Commons
Demonstrace chodu algoritmu
- Vizualizace červeno-černých stromů
- Red-Black Tree Animation, ukázka vkládání v nejhorším případě
Implementace
- V implementaci Standard Template Library jazyka C++ jsou červeno-černé stromy často použity v kontejnerech
std::set<Value>
astd::map<Key,Value>
- Efektivní implementace červeno-černých stromů
- RBT: knihovna červeno-černých stromů v jazyce SmallEiffel Archivováno 7. 10. 2017 na Wayback Machine.
- libredblack: Implementace v C
Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty. |
Stromové datové struktury | |
---|---|
Vyhledávací stromy (dynamické množiny/ asociativní pole) | 2–3 • 2–3–4 • AA • (a,b) • AVL • B • B+ • B* • Bx • (Optimální) Binární vyhledávací • Dancing • HTree • Intervalový • Stromy s pořadím (Order statistic) • (Doleva převážený) Červeno-černý • Scapegoat • Splay • T • Treap • UB • Váhově vyvážený (tj. BB[α]) |
Haldy | Binární • Binomiální • Brodal • Fibonacciho • Leftist • Pairing • Skew • Van Emde Boasův strom • Slabá |
Trie | Ctrie • C-trie • Hašovací • Komprimovaná trie (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast |
Prostorové indexační stromy | Ball • BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • PH • Prioritní R • Čtyřstrom (Quadtree) • R • R+ • R* • Segmentový • VP (vantage-point) • X |
Jiné stromy | Strom pokrytí • Obousměrně provázaný (Doubly chained tree) • Exponenciální • Fenwickův • (Binární) Strom s prstem • Fraktálový indexový • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný spojovací • Hašový Merkleův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom) |
Kategorie:Stromy (dat. strukt.) |