Crveno-crno stablo: razlika između inačica

Slika 73: Slučajevi u while petlji u proceduri RB-DELETE-FIXUP. Tamni čvorovi imaju atribut boja jednak CRNA, jako osjenčani čvorovi imaju boju jednaku CRVENA, dok slabo osjenčani čvorovi imaju atribut boja predstavljen sa c i c', koji mogu biti ili CRNA ili CRVENA. Slova α, β, ..., ζ predstavljaju proizvoljna podstabla. U svakom pojedinom slučaju je konfiguracija sa lijeve strane transformirana u konfiguraciju s desne strane mijenjanjem nekih boja i/ili obavljanjem rotacije. Svaki čvor na koji x pokazuje ima jedno dodatno crnilo i on je ili crveno-crn ili dvostruko crn. Jedini slučaj koji uzrokuje da se petlja ponovi jest slučaj 2. (a) Slučaj 1 je transformiran u slučajeve 2,3 i 4 zamjenom boja čvorova B i D i obavljanjem rotacije ulijevo. (b) U slučaju 2, dodatno crnilo predstavljeno pokazivačem od x je pomaknuto razinu prema gore u stablu bojanjem čvora D u crveno i postavljanjem x da pokazuje na čvor B. Ako uđemo u slučaj 2 kroz slučaj 1, while petlja se prekida zato jer je novi čvor x crveno-crn, te je stoga vrijednost c njegova atributa boje ima vrijednost CRVENA. (c) Slučaj 3 je transformiran u slučaj 4 zamjenom boja čvorova C i D te obavljanjem rotacije udesno. (d) U slučaju 4, dodatni crni čvor predstavljen x-om može biti uklonjen mijenjanjem nekih boja i obavljanjem rotacije ulijevo (bez kršenja crveno-crnih svojstava), a pri tom se i petlja prekida. ]]

'''Slučaj 1: x-ev brat ili sestra w su crveni:''' Slučaj 1 (linije 5-8 procedure RB-DELETE-FIXUP i slika 73(a)) se pojavljuje kad je čvor w, brat ili sestra x-a, crvene boje. Budući da w mora imati crnu djecu, možemo zamijeniti boje w i p[x] te potom obaviti rotaciju ulijevo nad p[x] bez kršenja iti jednoga crveno-crnog svojstva. Novi brat ili sestra od x, koji je jedan od w-ove djece prije obavljene rotacije, je sada crn, i stoga imamo konvertiran slučaj 1 u slučajeve 2, 3 i 4. Slučajevi 2, 3 i 4 se pojavljuju kada je w crn - razlikuju se bojama w-ove djece. <br> <br>

'''Slučaj 2: x-ev brat ili sestra w su crni, i oba djeteta od w su crna:''' U slučaju 2 (linije 10-11 procedure RB-DELETE-FIXUP i slika 73(b)), oba djeteta od w su crna. Budući da je w također crn, oduzimamo jedan crni i od x i od w, ostavljajući x sa samo jednim crnim i ostavljajući w crvenim. Da nadomjestimo uklanjanje jednog crnog od x i w, željeli bismo dodati dodatni crni p[x], koji je izvorno ili crven ili crn. To činimo ponavljajući while petlju s p[x] kao novim čvorom x. Uočimo da ako uđemo u slučaj 2 kroz slučaj 1, novi čvor x je crven-i-crn, pošto je izvorni p[x] bio crven. Dakle, vrijednost c atributa boja novog čvora x je CRVENA, i petlja se prekida pri provjeri uvjeta petlje. Novi čvor x je tada obojan u crno u liniji 23. <br> <br>

Slučaj 3 (linije 13-16 i slika 73(c)) se pojavljuje kad je w crn, njegovo lijevo dijete je crveno, a njegovo desno dijete crno. Možemo zamijeniti boje w-a i njegovog lijevog dijeta lijevo[w] te potom obaviti rotaciju udesno nad w bez kršenja iti jednoga crveno-crnog svojstva. Novi brat ili sestra w od x-a je sad crni čvor s crvenim desnim djetetom, te smo stoga transformirali slučaj 3 u slučaj 4. <br> <br>

'''Slučaj 4: x-ev brat ili sestra su crni i w-evo desno dijete je crveno''': Slučaj 4 (linije 17-21 i slika 73(d)) se pojavljuje kad x-ev brat ili sestra w je crn, a njegovo desno dijete crveno. Promjenom nekih boja i obavljanjem rotacije ulijevo nad p[x] možemo ukloniti dodatno crnilo na x, čineneći ga tako običnim crnim čvorom, bez kršenja bilo kojega crveno-crnoga svojstva. Stavljanjem x kao korijena uzrokujemo prekidanje while petlje kad ona testira svoj uvjet.