Červeno-černý strom

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Č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. Kořen je černý.
  3. Listy (nil) jsou pokládány za černé vrcholy.
  4. Každý červený vrchol má dva černé syny.
  5. 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]

Demonstrace chodu algoritmu[editovat | editovat zdroj]

Implementace[editovat | editovat zdroj]