In de vorige post bespraken we de inleiding tot Red-Black Trees. In deze post, wordt het invoegen besproken. Bij het invoegen van AVL bomen, gebruikten we rotatie als een hulpmiddel om te balanceren na het invoegen. In de Rood-Zwarte boom gebruiken we twee hulpmiddelen om het in evenwicht brengen te doen.
- Recoloring
- Rotation
Recoloring is het veranderen van de kleur van een knooppunt, d.w.z. als het rood is, verander het dan in zwart en vice versa. Opgemerkt moet worden dat de kleur van het NULL knooppunt altijd zwart is. Bovendien proberen we altijd eerst te herkleuren, als herkleuren niet werkt, dan gaan we over tot rotatie. Hieronder volgt een gedetailleerd algoritme. De algoritmen hebben hoofdzakelijk twee gevallen, afhankelijk van de kleur van de oom. Als de oom rood is, doen we herkleuren. Als de oom zwart is, doen we rotaties en/of herkleuren.
De voorstelling waar we mee zullen werken is:
Deze representatie is gebaseerd op X
Logica:
Eerst moet je het knooppunt op dezelfde manier invoegen als in een binaire boom en er een rode kleur aan toekennen. Als de node een root node is, verander dan zijn kleur in zwart, maar als dat niet het geval is, controleer dan de kleur van de parent node. Als de kleur zwart is, verander de kleur dan niet, maar als dat niet het geval is, d.w.z. als de kleur rood is, controleer dan de kleur van de oom van het knooppunt. Als de oom van de node een rode kleur heeft, verander dan de kleur van de ouder en oom van de node in zwart en die van grootvader in rood en herhaal hetzelfde proces voor hem (d.w.z. grootvader).
Maar, als de oom van het knooppunt een zwarte kleur heeft, zijn er 4 mogelijke gevallen:
- Links geval (LL-rotatie):
- Links rechts geval (LR-rotatie):
- Rechts geval (RR-rotatie):
- LinksRechts geval (RL-rotatie):
Nu, na deze rotaties, als de kleuren van de knooppunten niet overeenkomen, kleur ze dan opnieuw in.
Algoritme:
Laat x de nieuw ingevoegde node zijn.
- Voer standaard BST insertie uit en maak de kleur van nieuw ingevoegde nodes als ROOD.
- Als x de root is, verander de kleur van x dan als ZWART (Zwarte hoogte van complete boom neemt met 1 toe).
- Doe het volgende als de kleur van x’s ouder niet ZWART is en x niet de root is.
a) Als de oom van x ROOD is (Grootouder moet zwart zijn geweest van eigenschap 4)
(i) Verander de kleur van ouder en oom in ZWART.
(ii) Kleur van grootouder als ROOD.
(iii) Verander x = de grootouder van x, herhaal stap 2 en 3 voor nieuwe x.b) Als de oom van x ZWART is, dan kunnen er vier configuraties voor x zijn, x’s ouder (p) en x’s grootouder (g) (Dit is vergelijkbaar met AVL Tree)
(i) Linker geval (p is het linker kind van g en x is het linker kind van p)
(ii) Linker geval rechts (p is links kind van g en x is het rechter kind van p)
(iii) Rechts Rechts geval (spiegel van geval i)
(iv) Rechts Links geval (spiegel van geval ii)
Exemplaar: Het maken van een rood-zwarte boom met elementen 3, 21, 32 en 17 in een lege boom.
Oplossing:
Wanneer het eerste element wordt ingevoegd wordt het ingevoegd als root node en als root node heeft het de kleur zwart dus krijgt het de kleur zwart.
Het nieuwe element wordt steeds ingevoegd met een rode kleur en als 21 > 3 dus wordt het een deel van de rechter subtree van de root node.
Nu, als we 32 invoegen, zien we dat er een rood vader-kind paar is dat in strijd is met de Rood-Zwarte boomregel, dus moeten we het draaien. Bovendien zien we de voorwaarden van de RR-rotatie (waarbij de nulknoop van de wortelknoop als zwart wordt beschouwd), dus na de rotatie kan de wortelknoop niet rood zijn, dus moeten we de boom opnieuw inkleuren, wat resulteert in de hierboven getoonde boom.
Nu we het nieuwe element invoegen, verschijnen de parent en child node met rode kleur weer en hier moeten we ze opnieuw inkleuren. We zien dat zowel de parent node als de oom node een rode kleur hebben dus we veranderen gewoon hun kleur in zwart en veranderen de kleur van de grootvader in rood. Aangezien de grootvader de root node is, veranderen we zijn kleur opnieuw in zwart, wat resulteert in de boom die we hierboven zien.
Eindstructuur van de boom:
De uiteindelijke boom ziet er als volgt uit
Gelieve C-programma voor Rood-Zwart boom invoegen te raadplegen voor de volledige implementatie van het bovenstaande algoritme.
Rood-Zwarte boom | Set 3 (Delete)