• Rdeče-črno drevo (v nadaljevanju RČD) je delno poravnano dvojiško iskalno drevo.

• Barva ni dovolj, da govorimo o RČD, potrebnih je še nekaj lastnosti. In to so:

  • koren drevesa je črne barve,
  • rdeče vozlišče sme imeti samo črne sinove,
  • vsi listi drevesa so črne barve,
  • za vsako vozlišče mora veljati, da vsaka pot od vozlišča do praznega poddrevesa vsebuje enako število črnih vozlišč.

• Primer RČD:

• Operacije, ki se izvajajo na RČD so iskanje, vstavljanje in brisanje.

• V RČD rotacije pogosto uporabimo in sicer za uravnoteženje drevesa. Rotacija zamenja vlogo očeta in sina. V splošnem poznamo levo in desno rotacijo, ki sta si nasprotni.

• Ker je RČD dvojiško iskalno drevo, vedno velja, da je vrednost v nekem vozlišču vedno večja od vrednosti v levem sinu, ter vedno manjša od vrednosti v desnem sinu.
• Z iskanjem začnemu v korenu. Če je vrednost, ki je iščemo večja od korena, nadaljujemo v desno poddrevo, če pa je vrednost manjša, nadaljujemo v levo poddrevo.

• Primer, kako v spodnjem RČD najdti element 9.

• Ker je 9 več od 8, nadaljujemo v desno podrevo in pridemo do 12. Ker je 9 manj od 12, gremo v levo poddrevo. In tako smo prišli do 9.

• Primer, kako v spodnje RČD vstaviti element 9.

• Postopek poteka na podoben način kot pri iskanju. Če je vrednost, ki je vstavljamo večja od korena (oz. trenutnega vozlišča) gremo v desno poddrevo, sicer gremo v levo poddrevo. Ko pridemo do listov, vozlišče vstavimo in ga obarvamo rdeče ter mu dodamo 2 črna sinova brez vrednosti (nil).

• Ker sta oče in stric rdeče barve, ju prebarvamo na črno, ter dedka prebarvamo na rdeče.

• Ko v RČD vstavimo vozlišče (to je trenutno vozlišče), ga vedno obarvamo rdeče. Pri tem pa pogosto pridemo do primera, ko ima rdeče vozlišče rdečega sina (kar pa pri RČD ne sme biti).
• Kako odpraviti 'napako' in pridti do RČD?
• V primeru, da je oče trenutnega vozlišča črn problema ni.
• Če je oče trenutnega vozlišča rdeče barve in dedek ne obstaja, očeta pobarvamo črno in je problem odpravljen.
• Če sta oče in stric trenutnega vozlišča rdeče barve, dedka obarvamo rdeče, očeta in strica pa črno. Po postopku prebarvanja dedek postane trenutno vozlišče in postopek rekurzivno ponovimo.

• Če je stric črn ali ga ni, ločimo 2 primera:

  • Oče trenutnega vozlišča A je desni sin svojega očeta in ločimo 2 podprimera:

    • Vozlišče A je levi sin, njegov oče postane trenutno vozlišče. Nad njim izvedemo desno rotacijo, nato njegovega očeta obarvamo črno, dedka obarvamo rdeče. Nad dedkom izvedemo še levo rotacijo.
    • Vozlišče A je desni sin. Njegovega očeta obarvamo črno, dedka rdeče. Nad dedkom izvedemo levo rotacijo.

  • Oče trenutnega vozlišča A je levi sin svojega očeta:

    • Vozlišče A je levi sin. Očeta od vozlišča A obarvamo črno ter dedka rdeče. Nad dedkom izvedemo še desno rotacijo.
    • Vozlišče A je desni sin in njegov oče postane trenutno vozlišče ter nad njim izvedemo levo rotacijo. Očeta obarvamo črno, dedka rdeče ter nad dedkom izvedemo desno rotacijo.

• Sestavimo rdeče-črno drevo z naslednjimi podatki: 24, 28, 13, 30, 8, 26, 9, 16, 14, 35, 38, 6 in 4.

Vstavimo 24:

Vstavimo 28:

Vstavimo 13:

Vstavimo 30:

Oče in stric sta rdeča, zato sledi samo prebarvanje.

Vstavimo 8:

Vstavimo 26:

Vstavimo 9:

Oče od vsavljenega vozlišča postane trenutno vozlišče, nad njim izvedemo levo rotacijo.

Očeta (od vozlišča 8) obarvamo črno, dedka pa rdeče.

Nad dedkom izvedemo desno rotacijo.

Vstavimo 16:

Sledi prebarvanje.

Vstavimo 14:

Oče je rdeč in postane trenutno vozlišče. Nad njim izvedemo desno rotacijo.

Očeta obarvamo črno, dedka rdeče in nad dedkom izvedemo levo rotacijo.

Vstavimo 35:

Sledi prebarvanje.

Vstavimo 38:

Očeta vstavljenega vozlišča obarvamo črno in dedka rdeče.

Nad dedkom izvedemo levo rotacijo.

Vstavimo 6:

Vstavimo 4:

Očeta obarvamo črno in dedka rdeče.

Nad dedkom izvedemo desno rotacijo.

VPRAŠANJA???

• http://rc.fmf.uni-lj.si/matija/OpravljeneDiplome/Petra_Tome_Diploma.pdf
• Jani Cerar: Rdeče-črna drevesa - diplomsko delo, Maribor 2010
• http://penelope.fmf.uni-lj.si/r2wiki/index.php/Glavna_stran/SeminarskeNaloge/2009_1sem/Rde%C4%8De-%C4%8Drno_drevo/ime2
• Igor Kononenko, Marko Robnik Šikonja: Algoritmi in podatkovne strukture, Ljubljana 2003