Červeno-černý strom (též ) 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.
náhled|400px|Příklad červeno-černého stromu. Č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
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 libredblack: Implementace v C
Kategorie:Stromy (datové struktury)