Cesko.wiki Červeno-černý strom
Author
Albert FloresČ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.
Příklad červeno-černého stromu. +more Č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
Externí odkazy
Demonstrace chodu algoritmu
[url=https://people. ksp. +moresk/~kuko/gnarley-trees/Redblack. html]Vizualizace červeno-černých stromů[/url] * [url=http://www. ibr. cs. tu-bs. de/lehre/ss98/audii/applets/BST/RedBlackTree-Example. html]Red-Black Tree Animation[/url], 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> * [url=https://web. archive. +moreorg/web/20070927222509/http://eternallyconfuzzled. com/tuts/datastructures/jsw_tut_rbtree. aspx]Efektivní implementace červeno-černých stromů[/url] * [url=http://efsa. sourceforge. net/archive/durian/red_black_tree. htm]RBT: knihovna červeno-černých stromů v jazyce SmallEiffel[/url] * [url=http://libredblack. sourceforge. net/]libredblack: Implementace v C[/url].
