Az előző bejegyzésben a Red-Black Trees bevezetését tárgyaltuk. Ebben a bejegyzésben a beszúrást tárgyaljuk. Az AVL fa beszúrásánál a rotációt használtuk eszközként, hogy a beszúrás után kiegyenlítést végezzünk. A Vörös-fekete fában két eszközt használunk a kiegyensúlyozáshoz.
- Átszínezés
- Rotáció
Az átszínezés a csomópont színének megváltoztatása, azaz ha piros, akkor változtassuk feketére és fordítva. Meg kell jegyezni, hogy a NULL csomópont színe mindig fekete. Ezenkívül először mindig az újraszínezéssel próbálkozunk, és ha az újraszínezés nem működik, akkor a forgatáshoz folyamodunk. Az alábbiakban egy részletes algoritmus következik. Az algoritmusoknak főként két esete van a bácsi színétől függően. Ha a bácsi piros, akkor újraszínezzük. Ha a bácsi fekete, akkor elforgatjuk és/vagy átszínezzük.
A következő ábrázolással fogunk dolgozni:
Ez a reprezentáció az X
logikán alapul:
Először is be kell illesztenünk a csomópontot a bináris fához hasonlóan, és piros színt kell rendelnünk hozzá. Most, ha a csomópont gyökércsomópont, akkor változtassuk a színét feketére, de ha nem, akkor ellenőrizzük a szülőcsomópont színét. Ha a színe fekete, akkor ne változtassuk meg a színét, de ha nem az, azaz piros, akkor ellenőrizzük a csomópont nagybátyjának színét. Ha a csomópont nagybátyjának színe piros, akkor változtassuk meg a csomópont szülőjének és nagybátyjának színét feketére, a nagyapa színét pedig pirosra, és ismételjük meg ugyanezt a folyamatot vele (azaz a nagyapával).
De ha a csomópont nagybátyja fekete színű, akkor 4 lehetséges eset van:
- Balra balra eset (LL forgatás):
- Balra jobbra eset (LR forgatás):
- Jobbra Jobb eset (RR forgatás):
- Balra Jobb eset (RL forgatás):
Most, ezen forgatások után, ha a csomópontok színei nem egyeznek, akkor színezzük át őket.
Algoritmus:
Legyen x az újonnan beillesztett csomópont.
- Végezzük el a szokásos BST beszúrást, és az újonnan beillesztett csomópontok színét tegyük VÖRÖSSÉ.
- Ha x a gyökér, változtassuk meg x színét FEKETE-re (a teljes fa fekete magassága 1-gyel nő).
- Ha x szülőjének színe nem FEKETE, és x nem a gyökér, akkor a következőket tegyük.
a) Ha x nagybátyja VÖRÖS (A nagyszülőnek a 4. tulajdonságból feketének kellett lennie)
(i) Módosítsuk a szülő és a nagybácsi színét FEKETE színűre.
(ii) A nagyszülő színe legyen VÖRÖS.
(iii) Változtassuk meg x-et = x nagyszülője, ismételjük meg a 2. és 3. lépést az új x-re.b) Ha x nagybátyja FEKETE, akkor x-nek négyféle konfigurációja lehet, x szülője (p) és x nagyszülője (g) (Ez hasonló az AVL fához)
(i) Bal bal oldali eset (p g bal oldali gyermeke és x p bal oldali gyermeke)
(ii) Bal oldali jobb oldali eset (p a g bal oldali gyermeke és x p jobb oldali gyermeke)
(iii) Jobb oldali jobb eset (Az i. eset tükörképe)
(iv) Bal oldali jobb eset (A ii. eset tükörképe)
Példa: Piros-fekete fa létrehozása 3, 21, 32 és 17 elemekkel egy üres fában.
Megoldás:
Az első elem beszúrásakor gyökércsomóként kerül beszúrásra, és mivel a gyökércsomó fekete színű, így fekete színt kap.
Az új elem mindig piros színnel kerül beszúrásra, és mivel 21 > 3, így a gyökércsomó jobb oldali részfájának része lesz.
Most, ahogy beszúrjuk a 32-t, látjuk, hogy van egy piros apa-gyerek pár, ami sérti a piros-fekete fa szabályt, ezért el kell forgatnunk. Továbbá látjuk az RR forgatás feltételeit (a gyökércsomópont nullcsomópontját feketének tekintve), így a forgatás után, mivel a gyökércsomópont nem lehet piros, így átszínezést kell végeznünk a fában, ami a fent látható fát eredményezi.
Most az új elem beillesztésekor a szülő és a gyermek csomópont ismét piros színnel jelenik meg, és itt újra kell színeznünk őket. Látjuk, hogy a szülő csomópont és a bácsi csomópont is piros színű, ezért egyszerűen megváltoztatjuk a színüket feketére, a nagyapa színét pedig pirosra. Most, mivel a nagyapa a gyökércsomópont, ezért a színét ismét feketére változtatjuk, ami a fent látható fát eredményezi.
A végső fa struktúrája:
A végleges fa így fog kinézni
A fenti algoritmus teljes megvalósításához lásd: C program a vörös-fekete fa beillesztéséhez.
Vörös-fekete fa | 3. készlet (Törlés)