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

Příklad červeno-černého stromu.

Červeno-černý strom musí splňovat následující pravidla:

  1. Každý uzel je buď červený, nebo černý.
  2. Kořen je černý.
  3. Listy (nil) jsou pokládány za černé vrcholy.
  4. Každý červený vrchol má dva černé syny.
  5. 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

  • Logo Wikimedia Commons 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> a std::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
Pahýl
Pahýl
 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.)