Černobílé stromy
Binární vyhledávací stromy, jejichž uzlynesou kromě klíče další atribut – BARVU
(černou nebo bílou).
Černobílý strom je binární vyhledávací strom, jehož každýuzel je obarven černou nebo
bílou barvou. Musí splňovat tyto podmínky:
1) Kořen stromu je černý.
2) Je-li vnitřní uzel bílý, jeho následníci (pokud existují) jsou černí.
3) Všechny větve obsahují stejný počet černých uzlů.
Přidáváníuzlu:
Přidávaný uzel bude bílý. Tím se nezmění černá hloubka podstromů, ale mohou se dostat
pod sebe dva bílé uzly.
Se dvěma bílými uzly nad sebou a s černým uzlem nad nimi provedeme takovou rotaci,
abychom snížili hloubku stromu, ale přebarvíme je tak, aby černá hloubka stromu zůstala
zachována: kořen bude bílý a jeho dva následníci černí.
Tím se mohly pod sebe dostat dva bílé uzly. Proto celý postup opakujeme tak dlouho,
dokud jsou někde pod sebou dva bílé uzly.
Zůstane-li bílýkořen, přebarvíme ho načerno. Tím se černá hloubka celého stromu zvýší
o jedničku.
Složitost: Θ(log n)
Rušeníuzlu:
Rušení vnitřního uzlu převedeme na rušení listu. Je-li rušenýlist bílý, jerušení triviální –
strom i bez listu zůstane černobílý. Je-li rušenýlist černý, je nutné jej nejdříve „odbarvit“.
Odbarvíme-li černýlist, stane se tento list bílým a můžeme hosnadno zrušit.
Operace odbarvení spočívá v přesunutí přebytečné černé barvy blíže ke kořeni tak, aby
černé délky všech větví zůstaly stejné. Přitom může dojít k „přibarvení“ černého uzlu –
přesuneme-li černou barvu na uzel, který byl sám černý, stane se tento uzel „dvojnásobně
černý“ a je nutné jej dále odbarvovat (přesovat černou barvu blíže ke kořeni), aby byl
každý uzel nejvýše jednou černý.
Stane-li se dvojnásobně černý kořen celého stromu, přebytečnou černou barvu z něj
smažeme a necháme jej „jednou černý“. Tím se sníží černá hloubka celého stromu.
Složitost: Θ(log n)
Printed with FinePrint - purchase at www.fineprint.com
PDF created with pdfFactory trial version www.pdffactory.com
Printed with FinePrint - purchase at www.fineprint.com
PDF created with pdfFactory trial version www.pdffactory.com