![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/langcs-640px-Red-black_tree_example.svg.png&w=640&q=50)
Červeno-černý strom
From Wikipedia, the free encyclopedia
Č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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/6/66/Red-black_tree_example.svg/640px-Red-black_tree_example.svg.png)
Č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ů.