I det foregående indlæg diskuterede vi introduktionen til rød-sorte træer. I dette indlæg diskuteres indsættelse. I AVL-træindsættelse brugte vi rotation som et værktøj til at foretage balancering efter indsættelse. I Red-Black-træet bruger vi to værktøjer til at foretage balanceringen.
- Omfarvning
- Rotation
Omfarvning er ændringen af knodens farve, dvs. hvis den er rød, ændres den til sort og omvendt. Det skal bemærkes, at farven på NULL-knuden altid er sort. Desuden prøver vi altid først at omfarve, og hvis omfarvning ikke virker, går vi over til rotation. Følgende er en detaljeret algoritme. Algoritmerne har primært to tilfælde afhængig af farven på onklen. Hvis onklen er rød, foretager vi en omfarvning. Hvis onklen er sort, foretager vi rotationer og/eller recolouring.
Den repræsentation, vi skal arbejde med, er:
Denne repræsentation er baseret på X
Logik:
Først skal man indsætte knuden på samme måde som i et binært træ og tildele den en rød farve. Hvis knuden nu er en rodknude, skal du ændre dens farve til sort, men hvis den ikke er det, skal du kontrollere farven på den overordnede knude. Hvis dens farve er sort, skal du ikke ændre farven, men hvis den ikke er sort, dvs. hvis den er rød, skal du kontrollere farven på knodens onkel. Hvis knodens onkel har en rød farve, ændres farven på knodens forælder og onkel til sort og farven på bedstefar til rød farve, og den samme proces gentages for ham (dvs. bedstefar).
Men hvis knodens onkel har sort farve, er der 4 mulige tilfælde:
- Venstre venstre tilfælde (LL rotation):
- Vestre højre tilfælde (LR rotation):
- Højre højre tilfælde (RR-rotation):
- Højre venstre tilfælde (RL-rotation):
Nu, efter disse rotationer, hvis knudernes farver ikke stemmer overens, skal de omfarves.
Algoritme:
Lad x være den nyligt indsatte knude.
- Udfør standard BST-indsættelse og gør farven på nyligt indsatte knuder som RØD.
- Hvis x er roden, ændres farven på x som SORT (Sort højde af komplet træ øges med 1).
- Gør følgende, hvis farven på x’s forælder ikke er SORT, og x ikke er roden.
a) Hvis x’s onkel er RØD (Bedsteforælder skal have været sort fra egenskab 4)
(i) Ændr farven på forælder og onkel som SORT.
(ii) Farven på en bedsteforælder som RØD.
(iii) Ændr x = x’s bedsteforælder, gentag trin 2 og 3 for det nye x.b) Hvis x’s onkel er SORT, kan der være fire konfigurationer for x, x’s forælder (p) og x’s bedsteforælder (g) (Dette svarer til AVL Tree)
(i) Venstre venstre tilfælde (p er venstre barn af g, og x er venstre barn af p)
(ii) Venstre højre tilfælde (p er venstre barn af g og x er højre barn af p)
(iii) Højre højre tilfælde (spejlbillede af tilfælde i)
(iv) Højre venstre tilfælde (spejlbillede af tilfælde ii)
Eksempel: Oprettelse af et rød-sort træ med elementerne 3, 21, 32 og 17 i et tomt træ.
Løsning:
Når det første element indsættes, indsættes det som rodknude og som rodknude har sort farve, så det får farven sort.
Det nye element indsættes altid med en rød farve og som 21 > 3, så det bliver en del af rodknudens højre undertræ.
Nu, da vi indsætter 32, ser vi, at der er et rødt far-barn-par, hvilket er i strid med reglen om rød-sort træ, så vi er nødt til at rotere det. Desuden ser vi betingelserne for RR-rotation (idet vi betragter rodknudenes nulknude som sort), så efter rotationen kan rodknuden ikke være rød, så vi er nødt til at foretage en omfarvning i træet, hvilket resulterer i det træ, der er vist ovenfor.
Nu, når vi indsætter det nye element, vises den overordnede og den underordnede knude med rød farve igen, og her skal vi omfarve dem. Vi kan se, at både forældreknuden og onkelknuden har rød farve, så vi ændrer simpelthen deres farve til sort og ændrer bedstefarsfarven til rød. Da bedstefaren er rodknuden, ændrer vi igen dens farve til sort, hvilket resulterer i det træ, der er vist ovenfor.
Den endelige træstruktur:
Det endelige træ ser således ud
Se venligst C Program for Red Black Tree Insertion for komplet implementering af ovenstående algoritme.
Red-Black Tree | Set 3 (Delete)