Červeno černé stromy

• červeno černý strom je binární vyhledávací strom splňující pdmínky:

1. každý uzel je obarvený červenou, nebo černou barvou
2. kořen stromů je černý
3. každý vnitřní uzel má právě dva syny
4. listy stromy nenesou žádnou hodnotu, jsou označeny nil, a mají černou barvu
5. když je uzel červený, tak jeho otec je černý (oba synové červeného uzlu mají černou barvu)
6. pro každý uzel stromy platí, že všechny cesty z něj do listů obsahují stejný počet černých listů

• výška uzlu $x$ je rovna počtu hran na nejdelší cestě z $x$ do listu
• černá výška uzlu $x$, $bh(x)$, je rovna počtu černých uzlů na cestě z $x$ do listu
  • barvu uzlu $x$ nezapočítávám do černé výšky uzlu $x$
  • (díky vlastnosti 6 je černé výška dobře definována!)

Každý uzel červ. čer. stromu s výškou $h$ má černou výšku alespoň $h/2$.

V červeno černém stromu má každý podstrom s kořenem $x$ alespoň $2^{bh(x)} - 1$ vnitřních uzlů.

Červeno černý strom s $n$ vnitřními uzly má výšku nejvýše $2 \log_2(n+1)$.

Operace

• Search, Maximum, Successor a Predecessor se implementují stejně jako pro BST - mají složitost $\mathcal{O}(\log n)$

• Insert a Delete modifikují strom → mohou porušit vlastnosti red-black tree
• potřebné další kroky pro obnovení vlastností
• takové operace je rotace

Rotace

• zachovává vlastnost binárního vyhledávacího stromu $a \in \alpha, b \in \beta, c \in \gamma \implies a \le x \le b \le y \le c$
• rotace může změnit výšku uzlů
• časová složitost $\mathcal{O}(1)$

Přidání nového uzlu

• uzel do stromy přidáme stejným postupem jako do binárního vyhledávacího stromu
• jakou barvou máme obarvit nový uzel?
• obě možnosti mají za důsledek porušení některých vlastností červeno černého stromu

• řešení: obarvi uzel $x$ červenou
• vlastnost 4 (stejná černá výška) zůstává v platnosti
• může dojít k porušení vlastnosti 1 (kořen stromu nemusí být černý) a vlastnost 3 (otec červeného uzlu nemusí být černý)
• po vložení uzlu vykonáme korekce, které obnoví platnost všech vlastností

Korekce případ 1

• uzel $a$ je červený
• otec $b$ uzlu $a$ je červený

Korekce - případ 2

Korekce - případ 3

Složitost přidání nového uzlu

• případ 1: změna obarvení 3 uzlů
• případy 2 a 3: jedna nebo dvě rotace a změna obarvení uzlů …
• celková složitost $\mathcal{O}(\log n)$

Odstranění uzlu

• uzel ze stromu odstraníme stejným postupem jako z BST
• v případě, že odstraněný uzel měl červenou barvu, vlastnosti stromy zůstavají zachované
• v případě, že měl černou barvu, může dojít k porušení vlastnosti 4 (Stejná černá výška)
• černou barvu z odstraněného uzlu přesouváme směrem ke kořenu tak, abychom obnovili platnost vlastnosti 4

Korekce 2 barev

• bazální případ: uzel má červnou a černou barvu → obarvi uzel a na černou barvu

Složitost odstranění uzlu

• celková složitost $\mathcal{O}(\log n)$

Rank (pořadí) prvku

• modifikace red black tree

• každému uzlu $x$ přidáme atribut x.size, který udává počet vnitřních uzlů v podstromě s kořenem $x$, včetně uzlu $c$