Rdeče-črna drevesa

Rdeče-črna drevesa izpeljemo iz binarnih iskalnih dreves tako, da vsakemu vozlišču dodamo še barvo in podatek o očetu. Barva vozlišča je lahko rdeča ali črna. Rdeče-črno drevo mora izpolnjevati dva pogoja:

1. Rdeče vozlišče mora imeti samo črna sinova.
2. Vsaka pot od korena nekega poddrevesa do praznega poddrevesa mora vsebovati enako število črnih vozlišč.

Vstavljanje elementa v rdeče-črno drevo

Element vstavimo podobno kot pri binarnem iskalnem drevesu v list na ustrezno mesto glede na ključ in ga pobarvamo rdeče. Če ima vstavljeni element črnega očeta je postopek vstavljanja končan, če pa ima rdečega očeta ne velja več prva lastnost rdeče-črnih dreves in je treba zato drevo popraviti. Obstajajo tri različne možnosti za popravljanje drevesa:

1. Če je oče vstavljenega elementa koren drevesa, očeta pobarvamo črno in končamo.
2. Stric vstavljenega vozlišča je rdeč. Starega očeta pobarvamo rdeče, očeta in strica pa črno. Če ima stari oče rdečega očeta, moramo postopek ponoviti od starega očeta navzgor (smatramo da je stari oče novi element). Postopek zaključimo, ko je oče novega vozlišča črn ali ko pridemo do korena.
3. Stric vstavljenega vozlišča je črn ali ne obstaja. Na poddrevesu starega očeta izvedemo enojno ali dvojno rotacijo tako, da srednjega po velikosti potegnemo v koren poddrevesa. Koren nato pobarvamo črno, njegova sinova pa rdeče.

Primer

Zaporedoma bomo v drevo vstavili elemente 25, 36, 333, 12, 9, 7 in 39.

V prazno drevo vstavimo element 25:

Vstavimo element 36:

Ker ima rdečega očeta, je drevo treba popraviti. Očeta pobarvamo črno, ker je koren drevesa (glej točko 1) in postopek je končan.

Vstavimo element 333:

Ker je oče vstavljenega elementa rdeč, je drevo treba popraviti. Vstavljeni element nima strica, zato drevo popravimo po točki 3 tako, da z levo rotacijo dvignemo element 36 v koren.

Vstavimo element 12:

Zopet je treba popraviti drevo, ker ima vstavljeni element rdečega očeta. Ker je stric vstavljenega rdeč, popravimo drevo po točki 2.

Vstavimo element 9:

Ker ima vstavljeni element rdečega očeta, a nima strica popravimo drevo po točki 3 tako, da z desno rotacijo dvignemo v koren poddrevesa element 12, ki je srednji po vrednosti (med elementi poddrevesa, katerega koren je stari oče vstavljenega elementa).

Vstavimo element 7:

Ker ima vstavljeni element rdečega očeta in rdečega strica popravimo drevo po točki 2 tako, da prebarvamo starega očeta na rdeče, očeta in strica pa na črno. Ker ima stari oče črnega očeta, je postopek končan.

Vstavimo element 39:

Ker ima vstavljeni element črnega očeta, drevesa ni treba popravljati.

Glej tudi: Animacija vstavljanja elementov v rdeče-črna drevesa

Brisanje elementa iz rdeče-črnega drevesa