Č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ý vrchol 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[editovat | editovat zdroj]
Externí odkazy[editovat | editovat zdroj]
Obrázky, zvuky či videa k tématu červeno-černý strom ve Wikimedia Commons
Demonstrace chodu algoritmu[editovat | editovat zdroj]
- 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ě
Implementace[editovat | editovat zdroj]
- 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
- libredblack: Implementace v C