Červeno černé stromy jsou dalším typem binárních vyhledávacích stromů. Což znamená, že stále platí uspořádání stromu - všechny uzly nalevo jsou menší a všechny uzly napravo jsou větší. U červeno černých stromů přidáme každému uzlu další položku - color, která bude u nového node nastavena na červenou. Jinak může být přebarvena na černou.
Červeno černé stromy mají několik pravidel, které je třeba dodržovat, aby se strom nacházel v konzistentním stavu. Pokud se některou z úprav stave strom nekonzistentní, budeme tuto situaci neprodleně řešit.
Zavádíme nový pojem černá výška stromu, což je stejná hodnota jako černý výška kořene stromu.
Pro vkládání vrcholu do červeno černého stromu použijeme stejný algoritmus jako pro binární vyhledávací strom. Vložíme vrchol do stromu a při vkládání nastavíme barvu na červenou. Poté musíme upravit strom tak, aby byl v konzistentním stavu.
Uvedeme si několik základních případů, jak se zachovat pokud je strom v nekonzistentním stavu po přidání nového uzlu.
Kořen stromu je červené barvy, pouze přebarvíme kořen na černý.
Strýc přidaného uzlu je červený, pak přebarvíme všechny vrcholy (kromě přidaného uzlu) na cestě z uzlu do jeho strýce.
Strýc přidaného uzlu je černý a zároveň je přidaný uzel levým potomkem, pak přebarvíme uzly až k prarodiči a následně provedeme rotace prarodiče.
Strýc přidaného uzlu je černý a zároveň je přidaný uzel pravým potomkem, pak provedeme levou rotaci rodiče.
Pro odstranění vrcholu z červeno černého stromu použijeme stejný algoritmus jako pro binární vyhledávací strom. Odstraníme vrchol ze stromu a při odstraňování nastavíme barvu na červenou. Poté musíme upravit strom tak, aby byl v konzistentním stavu.
Pro podrobnější popis k Red Black stromům(obzvlášť pro operaci delete) doporučuji stránky programiz nebo brilliant.
Úkol bude zadán i vypracován na hodině. V případě absence mě kontaktujte.