Crveno-crna stabla su poseban tip binarnih stabala koji se kao podatkovna struktura koriste u računarstvu za organiziranje dijelova usporedivih podataka, kao što su brojevi. U binarnim stablima je svaki podatak pohranjen u čvoru. Jedan od čvorova uvijek funkcionira kao početno mjesto, i nije dijete nijednome čvoru: zovemo ga korijenskim čvorom ili korijenom (engl. root). Ima do dva djeteta tj. dva čvora s kojima je povezan. Svako od njegove djece može imati do dva djeteta itd. Tako je korijenski čvor povezan sa svakim čvorom u stablu.

Ako čvor nema djece, zovemo ga listovni čvor ili list (engl. leaf node), jer se nalazi na samom rubu stabla. Podstablo (engl. subtree) je dio stabla kojem se može pristupiti preko određenoga čvora te se može smatrati samostalnim stablom.

Binarna pretraživačka stabla, uključujući crveno-crna stabla, zadovoljava ograničenje da svaki čvor sadržava vrijednost manju ili jednaku vrijednosti od vrijednosti desnog podčvora, a veću ili jednaku od vrijednosti lijevog podčvora. Ovo omogućava brzo pretraživanje stabla za zadanu vrijednost i dopušta učinkovito obilaženje (traversiranje) elemenata.

Razlike između crveno-crnih stabala i binarnih pretraživačkih stabala mini|350px|Primjer crveno crnoga stabla Crveno-crna stabla su binarna sortirana stabla s jednim dodatnim bitom prostora po čvoru: bojom koja može biti ili crvena ili crna. Nijedan put od korijena lista nije više od dva puta dulji od bilo koje drugog puta tako da je drvo otprilike balansirano.

Svaki čvor drva sadrži polja boju, ključ, lijevo, desno i p. Ako ne postoje dijete ili roditelj čvora, odgovarajuće polja čvora koje sadrži pokazivač sadrži vrijednost NIL. Mi ćemo smatrati ove NIL-ove kao pokazivače prema vanjskim čvorovima (listovima) binarnog stabla, a normalne čvorove koje sadrže ključeve kao unutarnje čvorove stabla.

Binarno stablo je crveno-crno stablo ako zadovoljava sljedeća crveno-crna svojstva: Svaki čvor je ili crven ili crn. Korijen je crn. Svaki list (NIL) je crn. Ako je čvor crven, onda su oba njegova djeteta crna. Za svaki čvor, svaki put od njegova čvora do listova koji su mu potomci sadržava isti broj crnih čvorova.

mini|350px|Crveno-crno stabla s crnim čvorovima i crvenim čvorovima. Svaki čvor u crveno-crnom stablu je ili crven ili crn, a djeca od crvenoga čvora su oba crna te svaki a jednostavni put od čvora do lista potomka sadrži isti broj crnih čvorova. (a) Svaki list, prikazan kao NIL, je crn. Svaki ne-NIL čvor je označen svojom crnom-visinom. NIL ima crnu-visinu jednaku 0. (b) Isto crveno-crno stablo, ali sa svakim NIL zamijenjenim istom stražarskom oznakom nil[T] koja je uvijek crna. Također su u stablu izostavljene crne-visine čvorova. Korijenov roditelj je također stražarska oznaka. (c) Isto crveno crno stablo ali s izostavljenim listovima i roditeljevim korijenom. Ovaj ćemo stil koristiti u ostatku ovog rada.

Kao pogodnost pri radu s ograničenim uvjetima prilikom rada s crveno-crnim stablima, koristimo jedinstvenu stražarsku oznaku da reprezentiramo NIL. Za crveno-crno stablo T stražarska oznaka nil[T] je objekt s istim poljima kao obični čvor u stablu. Njegovo polje boja je crna, dok njegova druga polja - p, lijevo, desno i ključ mogu biti postavljane na proizvoljne vrijednosti. Kao što slika 1(b) pokazuje, svi pokazivači na NIL su zamijenjeni pokazivačima na oznaku nil[T].

Koristimo stražarsku oznaku tako da možemo tretirati NIL dijete čvora x kao standardni čvor čiji je roditelj x. Iako smo umjesto toga mogli dodati različitu stražarsku oznaku za svaki NIL u stablu, tako da je roditelj svakoga NIL-a dobro definiran taj pristup bi trošio nepotreban prostor. Umjesto toga koristimo jednu stražarsku oznaku nil[T] da bismo predstavili sve NIL-ove listove i korijenov roditelj. Vrijednosti polja p, lijevo, desno i kljuc stražarske oznake su nevažni, iako ih možemo staviti ako nam cefne. Općenito se ograničavamo na unutrašnje čvorove crveno-crnoga stabla, jer oni sadržavaju vrijednosti ključeva.

Broj crnih čvorova na svakom putu od x-a, ali ne uključujući x, do pojedinog lista zovemo crna - visina čvora i označavamo s bh(x). Po svojstvu petom svojstvu crveno-crnih stabala, ideja crne-visine je dobro definirana jer svi silazi putovi od čvora imaju isti broj crnih čvorova. Definiramo crnu-visinu crveno-crnoga stabla kao crnu-visinu njegovog korijena.

Teorem koji slijedi pokazuje zašto je crveno-crno stablo dobro stablo za pretragu.

Teorem 1

Crveno-crno stablo s n unutrašnjih čvorova ima visinu od najviše 2log(n+1).

Dokaz Počinjemo pokazujući da podstablo s korijenom u bilo kojem čvoru x sadrži barem unutrašnjih čvorova. Dokazujemo ovu tvrdnju matematičkom indukcijom za visinu x-a. Ako je vrijednost x-a 0, onda x mora biti list nil[T]) i podstablo s korijenom u x zaista sadrži barem = - 1 = 0. unutrašnjih čvorova. Za korak indukcije, smatrajmo da čvor x ima pozitivnu vrijednost te da je unutrašnji čvor s dva djeteta. Svako dijete ima crnu-visinu od bh(x) ili bh(x) - 1, ovisno o tome je li boja crna ili crvena. Budući da je visina djeteta od x manja od same vrijednosti x, možemo primijeniti induktivnu hipotezu da zaključimo da svako dijete ima barem unutarnjih čvorova. Stoga podstablo s korijenom u x sadrži barem + + 1 = unutrašnjih čvorova što dokazuje tvrdnju.

Da se završi dokaz teorema, neka h bude visina stabla. Prema svojstvu 4, barem polovica čvorova bilo kojeg jednostavnoga puta od korijena do kraja, ne uključujući korijen, mora biti crna. Prema tome, crna vrijednost korijena mora biti barem h/2, te stoga vrijedi n >= .

Pomaknemo li 1 na lijevu stranu i logaritmiramo li izraz dobivamo lg(n + 1) = h/2, ili h = 2 lg(n + 1) Direktna posljedica ovoga teorema je ta da dinamički operacije PRETRAŽI, MINIMUM, MAXIMUM, SLJEDBENIK i PRETHODNIK na crveno-crnim stablima mogu biti implementirane u O(log n) vremenu, pošto se ionako mogu obaviti u O(h) vremenu na pretraživačkome stablu visine h, a svako crveno-crno stablo s n čvorova je pretraživačko stablo s visinom O(lg n). (Crveno - crna stabla ne podržavaju direktno dinamičke operacije INSERT i DELETE kako su one definirane na uobičajenim binarnim pretraživačkim stablima, budući da one ne garantiraju da će modificirano binarno stablo biti crveno crno stablo. Kasnije ćemo pokazati da se ove dvije operacije mogu modificirati na način da i one mogu biti obavljene u O(log n) vremenu.)

Rotacije

Operacije pretraživačkoga stabla TREE-INSERT i TREE-DELETE, izvedene na crveno-crnome stablu s n ključeva, se obavljaju u vremenu O(log n). Budući da one modificiraju stablo, rezultat može kršiti svojstva crveno-crnih stabala. Da bismo obnovili ova svojstva moramo promijeniti boju nekih čvorova u stablu i također promijeniti strukturu pokazivača. Mijenjamo strukturu pokazivača koristeći rotaciju, koja je lokalna operacija u pretraživačkom stablu koja održava svojstva binarnoga pretraživačkog stabla. Slika 2 pokazuje dvije vrste rotacija: rotacija ulijevo i rotacija udesno. Kada radimo rotaciju ulijevo na čvoru x, pretpostavljamo da desno dijete y nije nil[T] - x može biti bilo koji čvor u stablu čije desno dijete nije nil[T]. Lijeva se rotacija "vrti" oko veze od x prema y. Ona čini y novim korijenom podstabla, sa x kao y-ovo lijevo dijete, a staro y-ovo lijevo dijete postaje x-evo desno dijete. 300px|Slika 2

Rotacija kao operacija na binarnom pretraživačkom stablu. Operacija ROTIRAJ-ULIJEVO (T, x) transformira konfiguraciju dva čvora na lijevoj strani u konfiguraciju na desnoj mijenjajući konstantni broj pokazivača. Konfiguracija na desnoj strani može biti transformirana u konfiguraciju na lijevoj strani inverznom operacijom ROTIRAJ-UDESNO (T, y) Slova α, β, i γ predstavljaju proizvoljna podstabla .Operacija rotacije čuva svojstva binarnih pretraživačkih stabala: ključevi u α prethode ključ[x], koji prethodi ključevima u β, koji pak prethodi ključ[y], koji prethodi ključevima u y

Pseudokod za ROTIRAJ-ULIJEVO pretpostavlja da desno[x] ≠ nil[T] te da je korijenov roditelj nil[T].

1 y ← desno[x] ▹ postavi y. 2 desno[x] ← lijevo[y] ▹ promijeni y-ovo lijevo podstablo u x-evo desno podstablo 3 p[lijevo[y]] ← x 4 p[y] ← p[x] ▹ Poveži x-eva roditelja na y. 5 if p[x] = nil[T] 6 then root[T] ← y 7 else if x = lijevo[p[x]] 8 then lijevo[p[x]] ← y 9 else desno[p[x]] ← y 10 lijevo[y] ← x Stavi x na y-ovu lijevu stranu. 11 p[x] ← y

Kod za ROTACIJU-UDESNO je simetričan. I ROTIRAJ-ULIJEVO i ROTIRAJ-UDESNO se odvijaju u O(1) vremenu. Samo su pokazivači promijenjeni ovisno o tome o kojoj se rotaciji radi; sva ostala polja čvora ostaju ista.

Umetanje

Umetanje čvora unutar n-čvornog crveno-crnog stabla može biti završeno u O(lg n) vremenu. Koristimo modificirano verziju standardne TREE-INSERT procedure za umetanje čvora z unutar binarnog pretraživačkog stabla, pri čemu još i obojimo z u crveno. Da bismo garantirali očuvanje svojstava crveno-crnih stabala, pozivamo pomoćnu proceduru RB-INSERT-FIXUP koja prebojava čvorove i izvršava rotacije. Poziv RB-INSERT(T, z) umeće čvor z, čije je polje ključ po pretpostavci već popunjeno, unutar crveno-crnog stabla T.

RB-INSERT(T, z) 1 y ← nil[T] 2 x ← korijen[T] 3 while x ≠ nil[T] 4 do y ← x 5 if key[z] < ključ [x] 6 then x ← lijevo[x] 7 else x ← desno[x] 8 p[z] ← y 9 if y = nil[T] 10 then root[T] ← z 11 else if key[z] < ključ[y] 12 then lijevo[y] ← z 13 else desno[y] ← z 14 lijevo[z] ← nil[T] 15 desno[z] ← nil[T] 16 boja[z] ← RED 17 RB-INSERT-FIXUP(T, z)

Postoje 4 razlike između TREE-INSERT i RB-INSERT. Prvo, sve instance NIL-a u TREE-INSERT su zamijenjene s nil[T]. Drugo, postavili smo left[z] i right[z] na nil[T] u linijama 14-15 RB-INSERT operacije, kako bismo očuvali pravilnu strukturu stabla. Treće, obojali smo z u crveno u 16 liniji. Četvrto, jer bojanje z u crveno može kršiti jedno od svojstava crveno-crnih stabala, pozivamo RB-INSERT-FIXUP(T, z) u liniji 17 RB-INSERT operacije da bismo obnovili svojstva crveno-crnih stabala.

RB-INSERT-FIXUP(T, z) 1 while boja[p[z]] = CRVENA 2 do if p[z] = lijevo[p[p[z]]] 3 then y ← desno[p[p[z]]] 4 if boja[y] = CRVENA 5 then boja[p[z]] ← CRNA ▹ Slučaj 1 6 boja[y] ← CRNA ▹ Slučaj 1 7 boja[p[p[z]]] ← CRVENA ▹ Slučaj 1 8 z ← p[p[z]] ▹ Slučaj 1 9 else if z = desno[p[z]] 10 then z ← p[z] ▹ Slučaj 2 11 ROTIRAJ-ULIJEVO (T, z) ▹ Slučaj 2 12 boja[p[z]] ← CRNA ▹ Slučaj 3 13 boja[p[p[z]]] ← CRVENA ▹ Slučaj 3 14 ROTIRAJ-UDESNO(T, p[p[z]]) ▹ Slučaj 3 15 else (isto kao i kod then naredbe, samo su sad „desno“ i „lijevo“ zamijenjeni 16 boja[korijen[T]] ← CRNA

Da bismo razumjeli kako funkcionira RB-INSERT-FIXUP, razdijelit ćemo naše razmatranje koda u tri osnovna koraka. Prvo, odredit ćemo koja su kršenja svojstava crveno-crnih stabala uvedena u TREE–INSERT proceduri kada je čvor z umetnut i obojan crveno. Drugi korak koji ćemo učiniti bit će analiza uloge while petlje u linijama 1-15. Na ćemo analizirati svaki od tri slučaja koje while petlja sadrži, i vidjeti čemu služe. Slika 4 pokazuje kako RB-INSERT-FIXUP radi na oglednom crveno-crnom stablu.

Koje se od svojstava crveno-crnih stabala može prekršiti pri pozivu procedure RB-INSERT-FIXUP? Svojstvo 1 sigurno ostaje, baš kao i svojstvo 3, pošto su oba djeteta novoumetnutoga crvenog čvora stražarske oznake nil[T]. Svojstvo 5, koje kaže da je broj crnih čvorova isti na svakom putu od danoga čvora p, je također zadovoljeno, jer čvor z zamjenjuje (crnu) stražarsku oznaku, a čvor z je crven s djetetom kao stražarskom oznakom. Stoga, jedina svojstva koja se mogu prekršiti su svojstvo 2, koje zahtijeva da korijen bude crn, i svojstvo 4, koje govori da crveni čvor ne može imati crveno dijete. Oba moguća narušavanja su zato što je z obojen u crveno. Svojstvo 2 je narušeno ako je z korijen, a 4 ako je z-ev roditelj crven. Slika 4 (a) pokazuje narušavanje svojstva 5 nakon što je čvor z umetnut. While petlja u linijama 1-15 održava sljedeće trodijelne invarijante: Na početku svake iteracije petlje a. Čvor z je crven