Červeno-černý strom

Červeno-černý strom 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. Listy (nil) jsou pokládány za černé vrcholy.
3. Každý červený vrchol má dva černé syny.
4. Každá cesta z jednoho vrcholu do jeho podřízených listů obsahují stejný počet černých vrcholů.

[editovat] Související články

• AA strom

[editovat] Externí odkazy

[editovat] Demonstrace chodu algoritmu

• Red/Black Tree Demonstration, interaktivní demonstrace přidávání a odebírání prvků se zdrojovým kódem v Javě
• Red-Black Tree Animation, ukázka vkládání v nejhorším případě
• aiSee: Visualization of a Sorting Algorithm, animovaný GIF ukazující vkládání prvků (200 KiB)

[editovat] 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
• libredblack: Implementace v C
• Implementace v Javě
• Implementace v C#

Tento článek o algoritmu nebo datové struktuře je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.