Červeno-černý strom

Z Wikipedie, otevřené encyklopedie
Jump to navigation Jump to search

Č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ý vrchol 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[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]

Demonstrace chodu algoritmu[editovat | editovat zdroj]

Implementace[editovat | editovat zdroj]

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
Haldy
Trie
Hašovací • Radixový (tj. Patricia) • Sufixový (tj. PAT) • Ternální hledání • X-fast • Y-fast
Prostorové indexační stromy
BK • BSP • Kartézský • Hilbertův R • k-d (implicitní k-d) • M • Metrický • MVP • Oktálový (Octree) • 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 • Fúzní (Fusion tree) • Hašovací kalendář • iDistance • K-ární • Knuthův transformovaný (Left-child right-sibling binary tree) • Link/cut • Log-strukturovaný aspojovací • Merklův (TTH) • PQ • Rozsahový (Range) • SPQR • Top (Horní strom)
Citováno z „https://cs.wikipedia.org/w/index.php?title=Červeno-černý_strom&oldid=14428484“