• "Rdeče-črno drevo je delno poravnano iskalno dvojiško drevo z nadzorovano rastjo. Vsako vozlišče je bodisi rdeče bodisi črne barve. Poleg kazalcev na sinova, vozlišča vsebujejo še kazalec na očeta in informacijo o barvi. Za višino(h) rdeče - črnega drevesa velja: h <= 2 log (n + 1). Torej višina rdeče - črnega drevesa ni več kot dvakrat večja od višine polnega drevesa." (//wiki.fmf.uni-lj.si/wiki/Rde%C4%8De-%C4%8Drno_drevo)
• Časovna zahtevnost vseh osnovnih operacij nad iskalnim dvojiškim drevesom(išči, vstavi, briši) je odvisna od višine drevesa. Preprečiti želimo, da bi se drevo izrodilo(postalo podobno linearnemu seznamu). To naredimo tako, da pri vsakem vstavljanju in brisanju preverimo njegovo zgradbo, sproti pa preverjamo razliko med višinami levega in desnega poddrevessa. Če se drevo razvija enostransko, ga moramo uravnotežiti. Drevo je uravnoteženo, kadar se v vsakem vozlišču višini razlikujeta kvečjemu za 1.
• Prvotno strukturo je izumil Rudolf Bayer leta 1972 in jo poimenoval binarno B-drevo.
• Časovna zahtevnost osnovnih algoritmov (vstavljanje/brisanje/iskanje) je O(log n), kjer je n-skupno število elementov v drevesu.

Primer rdeče - črnega drevesa

• Vsako vozlišče v drevesu je črno ali rdeče,
• Koren drevesa je črn,
• Vsi listi so črni,
• Če je vozlišče v drevesu rdeče sta oba sinova črna,
• Poti od korena do vsakega lista vsebujejo enako število črnih vozlišč.

• Novo vozlišče v drevo vstavimo enako, kot ga vstavimo v navadnem iskalnem dvojiškem drevesu. Ko podatek vstavimo v list drevesa, vozlišče pobarvamo rdeče.
• Nato pa poskrbimo, da se ohranijo lastnosti rdeče-črnega drevesa. To storimo tako, da določenim vozliščem spremenimo barvo in naredimo rotacije.
• Rotacija je postopek, ki zamenja vlogo očeta in sinov.

Rotacije

• Slika desno nam prikazuje, da je X manjši od Y. C je večji od Y, a manjši od X in b večji kot X. Ko naredimo levo rotacijo(X), dobimo sliko na desni, ki prikazuje, da je Y na desni, zato je večji od X, a je manjši od X, c je večji kot Y na desni in b manjši kot Y in večji kot X.
• Za vstavljanje podatkov v rdeče-črno drevo obstaja algoritem, ki vstavi podatek in ohrani lastnosti rdeče-črnega drevesa.

• Brat B je rdeče barve. Njegova sinova SL in SR sta zaradi lastnosti črne barve. Zamenjamo lahko barvo brata B in njegovega očeta O, ter izvedemo levo rotacijo na očetu. Novi brat očeta O, ki je eden od sinov je črne barve.

Barvanje in rotacije

• Brat B in njegov desni sin SD sta črna, levi sin SL je rdeč. Zamenjamo barvo brata B in njegovega levega sina SL. Naredimo desno rotacijo na bratu B, s tem prevedemo problem na naslednjo možnost.

Barvanje in rotacije

• Brat B je črn in njegov desni sin SD je rdeč. Vozlišče brata B pobarvamo z barvo njegovega očeta O. Očeta O in bratovega sina pa s črno. Nato izvedemo levo rotacijo , ter postavimo B za koren drevesa. Sedaj popravki niso več potrebni, razen morda pobarvati koren drevesa na črno.

Barvanje in rotacije

• Belo vozlišče v diagramu je lahko rdeče ali črne barve, vendar se mora ujemati z enako barvo tako pred kot po preoblikovanju.

• Brata B in oba njegova sinova SL in SR so vsi črne barve, oče O pa je rdeč. Zamenjamo barvi brata B in očeta O, to ne vpliva na število vozlišč na poti skozi B.

Barvanje in rotacije

• Brat B in oba njegova sinova SL in SR so vsi črne barve. Brata B pobarvamo rdeče.

Barvanje in rotacije

• Brisanje v rdeče - črnem drevesu je podobno brisanju v običajnem iskalnem dvojiškem drevesu, le da moramo paziti na lastnosti:

1. če element v drevesu nima sina ga lahko odstranimo,
2. če ima element v drevesu samo enega od sinov, ga odstranimo in prevežemo ustrezen kazalec njegovega očeta,
3. če ima element v drevesu oba sina, ga nadomestimo s prvim največjim iz levega poddrevesa.

• Ohranjanje lastnosti:

1. če je bilo izbrisano rdeče vozlišče so vse lastnosti pravilne,
2. če je bilo izbrisano črno vozlišče, ima poti, ki ga je vsebovala eno vozlišče manj. Problem rešimo tako, da uporabimo dvojno črnino - to vozlišče ima začasno dvakratno vrednost črnega številčenja.

• Dodatno črnino potiskamo proti korenu dokler:

  1. ne pridemo do rdečega vozlišča in ga obarvamo črno,
  2. ne pridemo do korena in na črnino pozabimo,
  3. ne moremo izvesti barvanj oziroma rotacij.

• Z rdeče - črnim drevesom rešujemo najtežje primere vstavljanja, brisanja in iskanje, kar se tiče časa. Ta drevesa so uporabna in kakovostna v aplikacija v katerih je časovna zahtevnost pomembna in so tudi pomemben del v osnovnih podatkovnih strukturah.

• Še bolj kot rdeče - črna drevesa so uravnotežena AVL drevesa, to pomeni, da v najtežjih primerih potrebujejo še več rotacij pri vstavljanju ali brisanju podatkov.

• Sestavi rdeče črno drevo iz urejenih podatkov. Imamo števila 1, 2, 3, 4, 5.

Najprej vstavimo števila 1, 2, 3.

1. korak

Stari oče(1) je črn, strica pa ni. Zato prebarvamo očeta(2) črno in starega očeta(1) rdeče, ter izvedemo levo rotacijo.

2. korak

Vstavimo 4.

3. korak

Stari oče(2) je črn, stric(1) in oče(3) sta rdeča. Sledi prebarvanje stric(1) in oče(3) postaneta črna, star oče(2) pa rdeč, ker se moramo držati pravil, moramo koren oziroma starega očeta(2) prebarvati na črno.

4. korak

Vstavimo 5.

5. korak

Ker stric ne obstaja je potrebna rotacija in prebarvanje. Vsakemu vozlišču, ki nima obeh sinov, vstavimo še list črne barve, ki je brez vrednosti(nil).

Pravilo pravi, da to naredimo že na vsakem vstavljenem vozlišču, ampak zaradi preglednosti, sem to naredila na koncu. Primer je končan.

6. korak

• V RČD vstavi elemente 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23.

• Najprej vstavimo elemente 1, 2, 3. Vsak vstavljen element je rdeče barve. Koren(1) pobarvamo črno.

1. korak

• Kršimo pravilo. Rdeče vozlišče ima samo črne sinove. Drevo pobarvamo tako, da pogledamo kako je obarvan stric vozlišča(3), ker ne obstaja obarvamo očeta(2) črno in starega očeta(1) rdeče, ter naredimo levo rotacijo. Potem pa še dodamo element 4.

2. korak

• Spet smo kršili pravilo. Rdeče vozlišče ima samo črne sinove. Pogledamo kako je obarvan stric(3) in oče(1) vozlišča(4), ker sta oba rdeča jih pobarvamo na črno in starega očeta(2) na rdeče.

• Lastnost pravi, da more biti koren črn, zato ga prebarvamo črno.

3. korak

• Vstavimo element 5. Ker je oče(4) rdeč in ker vozlišče(5) nima strica ga obarvamo črno, starega očeta(1) na rdeče in izvedemo desno rotacijo.

4. korak

• Vstavimo element 6. Oče(1) vstavljenega vozlišča 6 je rdeč, zato je kršeno pravilo, da ima rdeče vozlišče le črne sinove. Pogledamo strica(5) vozlišča(6) in je rdeč tako kot oče(1) vozlišča(6). Zato ju pobarvamo črno in njunega očeta(4) rdeče. Tako veljajo vse lastnosti RČD. Potem vstavimo še element 7.

5. korak

• Kršeno je pravilo. Ni strica vozlišča 7, zato prebarvamo očeta(6) na črno, starega očeta(1) rdeče in uporabimo desno rotacijo. Ker vsa pravimo držijo vstavimo še element 8.

6. korak

• Ker sta oče(7) in stric(1) vozlišča(8) rdeče barve ju prebarvamo na črno, njunega očeta(6) pa na rdeče.
• Vozlišče(6) in njegov oče(4), stari oče(2) je črn. Toda stric(3) vozlišča(6) je črn, zato izvedemo rotacijo. Ker je vozlišče(6) desni sin očeta(4) izvedemo levo rotacijo.

7. korak

• Kršeno pravilo. Sedaj pogledamo vozlišče(4), ki je levi sin očeta((6), zato pobarvamo očeta(6) vozlišča(4) črno. Starega očeta(2) pa rdeče. Naredimo desno rotacijo. Vozlišče(6) postane novi koren drevesa.
• Nobena lastnost ni kršena. Vstavimo element 9.

8. korak

• Kršimo pravilo. Vozlišče(9) nima strica. Naredimo rotacijo, nato prebarvamo očeta(8) in starega očeta(7). Sledi še levo rotacijo starega očeta(7).
• Sedaj lahko vstavimo še element 10.

9. korak

• Oče(8) vstavljenega vozlišča(10) je rdeč, zato je kršeno pravilo, da ima rdeče vozlišče le črne sinove. Pogledamo strica(7) vozlišča(10) in je rdeč, zako kot oče(8) vozlišča(10). Zatu ju prebarvamo črno, očeta(9) pa rdeče.

• Vozlišče(9) in njegov oče(4) sta rdeče barve, stari oče(6) pa črne barve. Stric(2) vozlišča(9) je rdeč. To pomeni, da ima stari oče(6) oba sinova rdeča. Starega očeta(6) obarvamo rdeče, očeta(4) in strica(2) pa črno.

• Kršimo pravilo, ki pravi, da mora biti koren(6) črn, zato ga pobarvamo črno.

10. korak

• Držijo vse lastnosti, zato vstavimo še 11, 12, 13, 14, 15, 16, 17, 18, 19, 20.

11. korak

• Oče(12) vstavljenega vozlišča(20) je rdeč, zato kršimo pravilo, da ima rdeče vozlišče le črne sinove. Pogledamo strica(11) vozlišča(20) in je rdeč, tako kot oče(12) vozlišča(20). Zatu ju prebarvamo črno, očeta(5) pa rdeče.

• Vstavimo še vozlišče 21, 22, 23, ter liste nil. Naloga je končana, veljajo vse lasnosti RČD.

12. korak

• //penelope.fmf.uni-lj.si/r2wiki/index.php/Glavna_stran/SeminarskeNaloge/2009_1sem/Rde%C4%8De-%C4%8Drno_drevo/ime2
• //penelope.fmf.uni-lj.si/r2wiki/images/f/fa/Prosojice.pdf
• //en.wikipedia.org/wiki/Red-black_tree#Insertion
• //wiki.fmf.uni-lj.si/wiki/Rde%C4%8De-%C4%8Drno_drevo
• //rc.fmf.uni-lj.si/matija/OpravljeneDiplome/Petra_Tome_Diploma.pdf
• //www.nauk.si/materials/366/out/index.html#state=4