V předchozím příspěvku jsme probrali úvod do červeno-černých stromů. V tomto příspěvku se zabýváme vkládáním. Při vkládání stromů AVL jsme použili rotaci jako nástroj k provedení vyvážení po vložení. V červeno-černém stromu používáme k vyvažování dva nástroje.
- Recoloring
- Rotation
Recolouring je změna barvy uzlu, tj. pokud je červený, pak jej změňte na černý a naopak. Je třeba poznamenat, že barva uzlu NULL je vždy černá. Navíc vždy nejprve vyzkoušíme přebarvení, pokud přebarvení nepomůže, přejdeme k rotaci. Následuje podrobný algoritmus. Algoritmy mají především dva případy v závislosti na barvě strýce. Pokud je strýc červený, provedeme přebarvení. Pokud je strýc černý, provedeme rotaci a/nebo přebarvení.
Zobrazení, se kterým budeme pracovat, je následující:
Tato reprezentace vychází z X
Logika:
Nejprve je třeba vložit uzel podobně jako v binárním stromu a přiřadit mu červenou barvu. Nyní, pokud je uzel kořenovým uzlem, změňte jeho barvu na černou, ale pokud není, zkontrolujte barvu nadřazeného uzlu. Pokud je jeho barva černá, pak barvu neměňte, ale pokud není, tj. je červená, pak zkontrolujte barvu strýce uzlu. Pokud má strýc uzlu červenou barvu, pak změňte barvu rodiče a strýce uzlu na černou a barvu dědečka na červenou a stejný postup opakujte i pro něj (tj. dědečka).
Pokud má ale strýc uzlu černou barvu, pak existují 4 možné případy:
- Levý levý případ (LL rotace):
- Levý pravý případ (LR rotace):
- Pravý pravý případ (rotace RR):
- Pravý levý případ (rotace RL):
Nyní, pokud se po těchto rotacích barvy uzlů neshodují, přebarvěte je.
Algoritmus:
Nechť x je nově vložený uzel.
- Provedeme standardní vložení BST a barvu nově vložených uzlů uděláme ČERVENOU.
- Je-li x kořen, změníme barvu x na ČERNOU (Černá výška kompletního stromu se zvýší o 1).
- Pokud barva rodiče x není ČERNÁ a x není kořen, provedeme následující.
a) Je-li strýc x ČERVENÝ (Prarodič musel být černý z vlastnosti 4)
(i) Změňte barvu rodiče a strýce jako ČERNOU.
(ii) Barvu prarodiče jako ČERVENOU.
(iii) Změňte x = prarodič x, opakujte kroky 2 a 3 pro nové x.b) Je-li strýc x ČERNÝ, pak mohou existovat čtyři konfigurace pro x, rodiče x (p) a prarodiče x (g) (To je podobné jako u AVL stromu)
(i) Levý levý případ (p je levým potomkem g a x je levým potomkem p)
(ii) Levý pravý případ (p je levý potomek g a x je pravý potomek p)
(iii) Pravý pravý případ (zrcadlo případu i)
(iv) Pravý levý případ (zrcadlo případu ii)
Příklad: Vytvoření červeno-černého stromu s prvky 3, 21, 32 a 17 v prázdném stromu.
Řešení:
Při vložení prvního prvku je vložen jako kořenový uzel a jako kořenový uzel má černou barvu, takže získá barvu černou.
Nový prvek je vždy vložen s červenou barvou a jako 21 > 3, takže se stane součástí pravého podstromu kořenového uzlu.
Nyní při vkládání 32 vidíme, že existuje červená dvojice otec-dítě, která porušuje pravidlo červeno-černého stromu, takže ji musíme otočit. Navíc vidíme podmínky rotace RR (považování nulového uzlu kořenového uzlu za černý), takže po rotaci jako kořenový uzel nemůže být Červený, takže musíme provést přebarvení stromu, jehož výsledkem je výše uvedený strom.
Nyní se při vložení nového prvku opět objeví rodičovský a podřízený uzel s červenou barvou a zde je musíme přebarvit. Vidíme, že jak rodičovský uzel, tak i uzel strýc mají červenou barvu, takže jednoduše změníme jejich barvu na černou a dědečkovi změníme barvu na červenou. Nyní je dědeček kořenovým uzlem, takže opět změníme jeho barvu na černou, čímž vznikne výše zobrazený strom.
Finální struktura stromu:
Finální strom bude vypadat takto
Pro kompletní implementaci výše uvedeného algoritmu se podívejte na program v jazyce C pro vkládání červeno-černého stromu.
Červeno-černý strom | Sada 3 (Odstranit)