- PREUSMJERI Predložak:Wikipoveznice
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 odredenoga č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 izmedu crveno-crnih stabala i binarnih pretraživačkih stabala
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.
Kao pogodnost pri radu s ograničenim uvjetima prilikom rada sa crveno-crnim stablima, koristimo jedinstvenu stražarsku oznaku da reprezentiramo NIL. Za crveno-crno stablo T stražarska oznaka nil[T] je objekt sa 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 sa 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 sa 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 sa 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 primjeniti induktivnu hipotezu da zakljucimo 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 ukljucujuci 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 dinamicke operacije INSERT i DELETE kako su one definirane na uobicajenim binarnim pretraživačkim stablima, buduci da one ne garantiraju da ce modificirano binarno stablo biti crveno crno stablo. Kasnije cemo pokazati da se ove dvije operacije mogu modificirati na nacin 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.
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 sa 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 će biti 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
b. Ako je p[z] korijen , onda je p[z] crn.
a. Ako je prisutno narušavanje svojstava crveno-crnih stabala, onda je to kršenje najviše jednog svojstva, a to je ili svojstvo 2 ili svojstvo 4. Ako je to narušavanje svojstva 2, narušavanje se pojavljuje zato što je z korijen crvene boje. Ako je to kršenje svojstva 4, tada je to zbog toga što su oboje i z i p[z] crveni.
Dio (c), koji se bavi narušavanjem svojstava crveno-crnih stabala, je više važan prilikom pokazivanja da RB-INSERT-FIXUP obnavlja svojstva crveno-crnih stabala nego dijelovi (a) i (b). Budući da ćemo se fokusirati na čvor z i čvorove uokolo njega u stablu, korisno je znati iz dijela (a) da je z crven. Koristit ćemo (b) da bismo pokazali da čvor p[p[z]] postoji kad se na njega referenciramo u linijama 2, 3, 7, 8, 13 i 14.
Potrebno je pokazati da je invarijanta petlje istinita prije prve iteracije petlje, da svaka iteracija održava invarijantu petlje, te da nam invarijanta petlje daje korisno svojstvo nakon završetka petlje.
Započinjemo sa inicijalizacijom i prekidom. Potom, kad detaljnije ispitamo rad tijela petlje, uvjerit ćemo se da petlja održava invarijantu nakon svake iteracije. Usput ćemo demonstrirati da su dva moguća ishoda nakon svake iteracije petlje: pokazivač z pomiče se prema gore u stablu, ili su obavljene neke rotacije i petlja se prekida.
• Inicijalizacija: Prije prve iteracije petlje započinjemo s crveno-crnim stablom bez narušavanja svojstava, i dodajemo crveni čvor z. Pokazujemo da se svaki dio invarijante petlje održava kada je RB-INSERT-FIXUP pozvan:
a. Kada je procedura RB-INSERT-FIXUP pozvana, z je crveni čvor koji je dodan.
b. Ako je p[z] korijen, onda je p[z] crn i nije se promijenio prije poziva RB-INSERT-FIXUP.
c. Već smo vidjeli da su svojstva 1, 2 i 4 ostala vrijediti kad je RB-INSERT-FIXUP pozvan,
Ako je narušeno svojstvo 2, onda crvenom korijenu mora nanovo biti dodan čvor z, koji je jedini unutarnji čvor stabla. Budući da su i roditelj i oba djeteta od z stražarske oznake crne boje, također nema kršenja svojstva 4. Stoga je narušavanje svojstva 2 jedino narušavanje svojstava u čitavome stablu.
Ako je je narušeno svojstvo 4, onda zboga činjenice što su djeca čvora z crne stražarske oznake, kao i zbog toga što stablo nema drugih narušavanja prije nego je z dodan, narušavanje mora biti zbog toga što su z i p[z] crveni. Osim toga, nema drugih kršenja svojstava.
• Prekid: Kada se petlja prekine, to čini zbog toga što je p[z] crn. (Ako je z korijen, tada je p[z] stražarska oznaka nil[T] crne boje.) Stoga nema kršenja svojstva 4 nakon prekida petlje. Po invarijantama petlje, jedino svojstvo koje možda neće ostati zadržano jest svojstvo 2. Linija 16 također obnavlja i ovo svojstvo, tako da kad se prekine RB-INSERT-FIXUP, sva svojstva crveno-crnog stabla ostaju vrijediti.
• Održavanje: Iako u biti treba razmotriti šest slučajeva u while petlji, tri od njih su simetrična ostalim trima, ovisno o tome je li z-ev roditelj p[z] lijevo dijete ili desno dijete z-evog djeda p[p[z]], koji je određen u liniji 2. Dali smo primjer pseudokoda samo za situaciju kada je p[z] lijevo dijete. Čvor p[p[z]] postoji, jer je prema dijelu (b) invarijante petlje vrijedi da, ako je p[z] korijen, tada je p[z] je crn. Budući da se u petlju ulazi samo ako je p[z] crven, znamo da p[z] ne može biti korijen. Stoga p[p[z]] postoji.
Slučaj 1 se razlikuje od slučaja 2 i 3 po boji brata ili sestre z-evoga roditelja, i pritom uvedimo naziv "ujak" ta takav čvor. Linija 3 čini to da y pokazuje na z-evoga ujaka desno[p[p[z]]], a test je napravljen u liniji 4. Ako je y crven, onda je slučaj 1 izveden. Inače kontrola prelazi do slučajeva 2 i 3. U sva tri slučaja, z-ev djed p[p[z]] je crn, jer je njegov roditelj p[z] crven, a svojstvo 4 se krši samo između z i p[z].
Slučaj 1: z-ev ujak y je crven
Slika 5 pokazuje situaciju za slučaj 1 (linije 5-8). Slučaj 1 je izveden kada su oboje p[z] i y crveni. Budući da je p[p[z]] crn, možemo obojati p[z] i y u crno, popravljajući problem po kojem su z i p[z] oboje crveni, te obojati p[p[z]] crveni i na taj način održati svojstvo 5. Tada ponavljamo while petlju sa p[p[z]] kao novi čvor z. Novi čvor z pomiče se dvije razine prema gore u stablu.
kao novim z. Svako kršenje svojstva 4 se može sad pojaviti između novoga z, koji je crven, i njegova rodielja, ako i on također crven.]]
Sada pokazujemo da slučaj 1 održava invarijantu petlje na početku sljedeće iteracije. Koristimo z za obilježavanje z u trenutnoj iteraciji, a z′ p[p[z]] za obilježavanje čvora z na testu u liniji 1 u idućoj iteraciji.
a. Budući da ova iteracija boja p[p[z]] u crveno, čvor z′ je crven na početku iduće iteracije.
b. Čvor p[z′] postaje p[p[p[z]]] u ovoj iteraciji, i boja ovog čvora se ne mijenja. Ako je ovaj čvor korijen, tada je on bio crne boje prije ove iteracije, i ostaje crn na početku iduće iteracije.
c. Već je objašnjeno kako slučaj 1 održava svojstvo 5 i očito je da ne ne narušava svojstva 1 i 3.
Ako je z′ korijen na početku iduće iteracije, tada je slučaj 1 ispravio jedino narušenje svojstva 4 u ovoj iteraciji. Budući da je z′ crven i usto je korijen, svojstvo 2 postaje jedino koje se krši, a to je narušavanje zbog z′.
Ako čvor z′ nije korijen na početku iduće iteracije, tada slučaj 1 nije narušio svojstvo 2. Slučaj 1 je ispravio jedino kršenje svojstva 4 koje je postojalo na početku ove iteracije. Tada je z′ obojan crveno i pritom se nije dirao lijevi p[z′]. Ako je p[z′] crn, onda nema narušavanja svojstva 4. Ako je p[z′] crven, bojanje z′ u crveno stvara jedno narušavanje svojstva 4 između z′ i p[z′].
Slučaj 2: z-ev ujak y je crn i z je desno dijete
Slučaj 3: z-ev ujak y je crn i z je lijevo dijete
U slučaju 2 i 3 boja z-evog ujaka y je crna. Dva se slučaja razlikuju ovisno o tome je li z desno ili lijevo dijete p[z]. Linije 10-11 čine slučaj 2 koji je prikazan na slici 6 zajedno sa slučajem 3. U slučaju 2, čvor z je desno dijete svojega roditelja. Odmah koristimo rotaciju ulijevo da bismo transformirali situaciju u slučaj 3 (linije 12-14), u kojem je čvor z lijevo dijete. Budući da su oboje i z i p[z] crveni, rotacija ne utječe ni na crnu-visinu čvorova niti na svojstvo 5. Bilo da uđemo u slučaj 3 direktno ili kroz slučaj 2, z-ev ujak y je crn, jer bismo inače izvršavali slučaj 1. Pored toga, čvor p[p[z]] postoji pošto je već pokazano da ovaj čvor postoji u kada su linije 2 i 3 izvedene i poslije premještenja zjza jednu razinu prema gore u liniji 10 i potom razinu dolje u liniji 11, identitet p[p[z]] ostaje nepromijenjen. U slučaju 3 izvodimo neke promjene boja i rotaciju udesno koja održava svojstvo 5, i onda, pošto više nemamo dva crvena čvora jedan za drugim, smo gotovi. Tijelo while petlje se ne izvodi drugi put, jer je p[z] sada crn.
Sada pokazujemo da slučajevi 2 i 3 održavaju invarijanti petlje (Kao što je upravo pokazano, p[z] će biti crn na sljedećemu testu u liniji 1, i tijelo petlje se neće ponovno izvesti.)
a. Slučaj 2 čini da z pokazuje na p[z] koji je crven. Niti jedna daljnja promjena z ili njegove boje se ne pojavljuje u slučajevima 2 i 3.
b. Slučaj 3 boja p[z] u crno, tako da ako je p[z] korijen na početku iduće iteracije, boja ga u crno.
c. Kao u slučaju 1, svojstva 1, 3 i 5 su održavana se u slučajevima 2 i 3.
Budući da čvor z nije korijen u slučajevima 2 i 3, znamo da nema kršenja svojstva 2. Slučajevi 2 i 3 ne uvode narušavanje svojstva 2, jer jedini čvor koji je obojan u crveno postaje dijete crnoga čvora po rotaciji u slučaju 3.
Slučajevi 2 i 3 popravljaju jedino kršenje svojstva 4 i ne uvode niti jedno drugo kršenje.
Pokazujući da svaka iteracije petlje održava invarijantu, pokazali smo da RB-INSERT-FIXUP valjano obnavlja svojstva crveno-crnih stabala.
Analiza
Kolika je vremenska složenost procedure RB-INSERT? Budući da je visina crveno-crnog stabla od n čvorova O(lg n), linije 1-16 procedure RB-INSERT se izvršavaju u vremenu O(lg n). U RB-INSERT- FIXUP, while petlja se ponavlja Samo ako je slučaj 1 izveden i tada se pokazivač z pomiče dvije razine prema gore u stablu. Ukupan broj puta koji se while petlja izvršava je stoga O(lg n). Stoga je ukupna vremenska složenost procedure RB-INSERT O(lg n). Zanimljivo je uočiti da nikad ne izvodi više od dvije rotacije pošto se while petlja prekida ako su slučajevi 2 i 3 izvedeni.
Brisanje
Kao i sve ostale osnovne operacije na crveno-crnom stablu sa n čvorova, brisanje čvora uzima O(lg n) vremena. Brisanje čvora iz crveno-crnoga stabla je malo kompliciranije nego umetanje čvora. Procedura RB-DELETE je manja modifikacija standardne TREE-DELETE procedure koja vrijedi za klasično binarno pretraživačko stablo. Nakon odvajanja čvora poziva se pomoćna procedura RB-DELETE-FIXUP koja mijenja boje i obavlja rotacije kako da bi se obnovila svojstva crveno-crnih stabala.
RB-DELETE(T, z)
1 if lijevo[z] = nil[T] or desno[z] = nil[T] 2 then y ← z 3 else y ← TREE-SUCCESSOR(z) 4 if lijevo[y] = nil[T] 5 then x ← left[y] 6 else x ← right[y] 7 p[x] ← p[y] 8 if p[y] = nil[T] 9 then korijen[T] ← x 10 else if y = lijevo[p[y]] 11 then lijevo[p[y]] ← x 12 else korijen[p[y]] ← x 13 if y 3≠ z 14 then ključ[z] ← ključ[y] 15 kopiraj ostale y-ove podatke u z 16 if boja[y] = CRNA 17 then RB-DELETE-FIXUP(T, x) 18 return y
Postoje tri razlike između procedura TREE-DELETE i RB-DELETE. Prvo, sve reference na NIL u TREE-DELETE se zamjenjuju oznakom nil[T] u RB-DELETE. Drugo, test koji provjerava je li x NIL TREE-DELETE proceduri je uklonjen i dodjela p[x] ← p[y] je bezuvjetno obavljena u liniji 7 RB-DELETE procedure. Stoga, ako je x stražarska oznaka nil[T] , njegov pokazivač na roditelja pokazuje na roditelja odvojenoga čvora y. Treće, poziv RB-DELETE-FIXUP je obavljen u linijama 16-17 ako je y crn. Ako je y crven, održavaju se crveno-crna svojstva nakon odvajanja y zbog sljedećih razloga:
- • Nije se promijenila nijedna crna-visina u stablu
- • Ne postoje susjedni crveni čvorovi
- • Budući da y ne može biti korijen ako je crvene boje, korijen ostaje crn
Čvor x proslijeđen proceduri RB-DELETE-FIXUP je jedan od dva čvora: ili čvor koji je bio y-onovo jedino dijete prije nego što je y odvojen ukoliko je y imao dijete koje nije bilo stražarska oznaka nil[T ] , ili y nije uopće imao djece pa je x stražarska oznaka nil[T ]. U drugom slučaju bezuvjetna dodjela vrijednosti u liniji 7 garantira da je x-ev roditelj sada čvor koji je prethodno bio y-ov roditelj, ovisno o tome je li x unutarnji čvor koji sa ključem ili stražarska oznaka nil[T]. Sad možemo analizirati kako procedura RB-DELETE-FIXUP obnavlja crveno-crna svojstva binarnom pretraživačkom stablu.
.RB-DELETE-FIXUP(T, x)
1 while x ≠ korijen[T] and boja[x] = CRNA 2 do if x = lijevo[p[x]] 3 then w ← desno[p[x]] 4 if boja[w] = CRVENA 5 then boja[w] ← CRNA ▹ Slučaj 1 6 boja[p[x]] ← CRVENA ▹ Slučaj 1 7 ROTIRAJ-ULIJEVO(T, p[x]) ▹ Slučaj 1 8 w ← desno[p[x]] ▹ Slučaj 1 9 if boja[lijevo [w]] = CRNA and boja[desno[w]] = CRNA 10 then boja[w] ← CRVENA ▹ Slučaj 2 11 x p[x] ▹ Slučaj 2 12 else if boja[desno[w]] = CRNA 13 then boja[left[w]] ← CRNA ▹ Slučaj 3 14 boja[w] ← CRVENA ▹ Slučaj 3 15 ROTIRAJ-UDESNO(T, w) ▹ Slučaj 3 16 w ← desno[p[x]] ▹ Slučaj 3 17 boja[w] ← boja[p[x]] ▹ Slučaj 4 18 boja[p[x]] ← CRNA ▹ Slučaj 4 19 boja[desno[w]] ← CRNA ▹ Slučaj 4 20 ROTIRAJ-ULIJEVO (T, p[x]) ▹ Slučaj 4 21 x ← korijen[T] ▹ Slučaj 4 22 else (isto kao i kod then samo što su „desno“ i „lijevo“ zamijenjeni) 23 boja[x] ← CRNA
Ako je odvojeni čvor u RB-DELETE crn mogu se pojaviti tri problema. Prvo, ako je y bio korijen i crveno dijete od y postane novi korijen, prekršili smo svojstvo 2. Drugo, ako su i x i p[y] (koji je sada također p[x]) crveni, tada smo prekršili svojstvo 4. Treće, uklanjanje y uzrokuje to da svaki put koji je zadržavao y ima jedan crni čvor manje. Stoga, svojstvo 5 je sada prekršeno od strane bilo kojeg pretka y-a u stablu. Možemo ispraviti ovaj problem tvrdeći da čvor x ima "dodatnu" crnu boju. Drugim riječima, ako dodamo 1 broju crnih čvorova na bilo kojem putu koji sadrži x, svojstvo 5 će ostati održano. Kada smo odvojili crni čvor y, potisnuli smo njegovo crnilo na njegovo dijete. Problem je taj što čvor x nije sada ni crn niti crven, i stoga krši pravilo 1. Zapravo, čvor x je ili "dvostruko crn" ili "crven i crn" i dodaje ili 2 ili 1 broju crnih čvorova na puti koji sadrži x. Boja dodijeljena x će će još uvijek biti ili CRVENA (ako je x crven-i-crn) ili CRNA (ako je x dvostruko crn). Drugim riječima, dodatno crnilo čvora se odražava u x-evom pokazivanju na čvor, mjesto u atributu boja.
Procedura RB-DELETE-FIXUP obnavlja svojstva 1, 2, i 4. Trivijalno je dokazati da ova procedura obnavlja svojstva 2 i 4, te se stoga fokusiramo na svojstvo 1. Cilj while petlje u linijama 1-22 jest pomicanje dodatnog crnog čvora prema gore u stablo sve dok:
1. x pokazuje na crveno-crni čvor , u kojem pak slučaju bojamo x u crno u liniji 23, 2. x pokazuje na korijen, u kojem pak slučaju dodatno crnilo može biti jednostavno "uklonjeno" ili 3. prikladne rotacije i prebojanja mogu biti izvedena.
Unutar while petlje, x uvijek pokazuje na nekorijenski dvostruko crni čvor. Određujemo u liniji 2 je li x lijevo dijete ili desno dijete svojega roditelja p[x]. (Dali smo kod za situaciju u kojoj je x lijevo dijete; situacija u kojoj je x desno dijete – linija 22 - je simetrična.) Održavamo pokazivač w na brata ili sestru od x. Budući da je čvor x dvostruko crn, čvor w ne može biti nil[T], jer bi inače broj crnih čvorova na putu od p[x] do (crnog) lista w bio manji od onih na putu od p[x] do x. Četiri slučaja u kodu su ilustrirana na slici 7. Prije detaljnijeg razmatranja svakoga slučaja pogledajmo kako općenitije možemo provjeriti zadržava li transformacija u svakom slučaju svojstvo 5. Ključna ideja je ta da u svakome slučaju broj crnih čvorova (uključujući x-evo dodatno crnilo) od (i uključujući) korijena pokazanog podstabla pa do svakog podstabla α, β, ..., ζ održan od strane transformacije. Stoga, ako je svojstvo održano prije transformacije, održano je i nakon nje. Na primjer, u slici 7(a), koja ilustrira slučaj 1, broj crnih čvorova od korijena do nekog od podstabla α ili β je 3 i prije i poslije transforamcije. (Pri čemu se valja prisjetiti da čvor x dodaje dodatni crni čvor.) Slično, broj crnih čvorova od korijena do bilo kojeg od γ, δ, ε, i ζ, je isti prije i poslije transformacije. Na slici 7(b) brojanje mora uključiti vrijednost c atributa boja korijena prikazanog podstabla, koji može biti ili CRVEN ili CRN. Ako definiramo broj(CRVEN) = 0 i broj(CRN) =1, tada je broj crnih čvorova od korijena do α jednak 2 + count(c), i prije i poslije transformacije. U ovom slučaju, poslije transformacije novi čvor x ima atriribut boja jednak c, ali ovaj čvor je ustvari ili crveno-crn (ako je c= CRVENA) ili dvostruko crn (ako je c=CRNA). Drugi slučajevi mogu biti provjereni na sličan način.
Slučaj 1: x-ev brat ili sestra w su crveni: Slučaj 1 (linije 5-8 procedure RB-DELETE-FIXUP i slika 3(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.
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 3(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.
Slučaj 3: x-ev brat ili sesta w su crni, w-evo lijevo dijete je crveno i w-evo desno dijete je crno:
Slučaj 3 (linije 13-16 i slika 3(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.
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 3(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.
Analiza
Kolika je vremenska složenost procedure RB-DELETE? Budući da je visina crveno-crnog stabla s n čvorova O(lg n), ukupna cijenja poziva procedure bez poziva RB-DELETE-FIXUP procedure jest O(lg n) vremena. Unutar RB-DELETE-FIXUP slučajevi 1, 3 i 4 se prekidaju nakon obavljanja konstantnog broja promjena boja i najviše tri rotacije. Slučaj 2 je jedini slučaj u kojem while petlja može biti ponovljena, i tada se pokazivač x pomiče za razinu gore u stablu u najvišie O(lg n) puta i obavlja najviše tri rotacije, pa je stoga ukupna vremenska složenost procedure RB-DELETE O(lg n).