Wikipedija

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

Pregledaj povijest
← Starija izmjenaNovija izmjena →
Izbrisani sadržaj Dodani sadržaj
VizualnoWikitekst
{{wp+}}
Nema sažetka uređivanja
Redak 1:
{{dijakritici}}
{{wp+}}
'''Crveno-crna stabla''' su poseban tip [[binarno stablo|binarnih stabala]] koji se kao podatkovna struktura koriste u [[računarstvo|računarstvu]] za organiziranje dijelova usporedivih podataka, kao što su [[broj]]evi. U binarnim stablima je svaki podatak pohranjen u cvoručvoru. Jedan od cvorovačvorova uvijek funkcionira kao pocetnopočetno mjesto, i nije dijete nijednome cvoručvoru: zovemo ga korijenskim cvoromčvorom ili [[Korijen (biljke)|korijenom]] (engl. ''root''). Ima do dva djeteta tj. dva cvoračvora s kojima je povezan. Svako od njegove djece može imati do dva djeteta itd. Tako je korijenski cvorčvor povezan sa svakim cvoromčvorom u stablu.
 
Ako cvorčvor nema djece, zovemo ga listovni cvorčvor ili list (engl. ''leaf node''), buduci da se nalazi na samom rubu stabla. Podstablo (engl. subtree) je dio stabla kojem se može pristupiti preko odredenoga cvoračvora te se može smatrati samostalnim stablom.
 
Binarna pretraživackapretraživačka stabla, ukljucujuciuključujući crveno-crna stabla, zadovoljava ogranicenje da svaki cvorčvor sadržava vrijednost manju ili jednaku vrijednosti od vrijednosti desnog podcvorapodčvora, a vecu ili jednaku od vrijednosti lijevog podcvorapodčvora. Ovo omogucavaomogućava brzo pretraživanje stabla za zadanu vrijednost i dopušta ucinkovitoučinkovito obilaženje (traversiranje) elemenata.
 
== Razlike izmedu crveno-crnih stabala i binarnih pretraživackihpretraživačkih stabala ==
[[Slika:Red-black tree example.svg|thumb|300px|Primjer crveno crnoga stabla]]
Crveno-crna stabla su binarna sortirana stabla s jednim dodatnim bitom prostora po cvoruč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 cvorčvor drva sadrži polja boju, kljuc, lijevo, desno i p. Ako ne postoje dijete ili roditelj cvoračvora, odgovarajuceodgovarajuće polja cvoračvora koje sadrži pokazivacpokazivač sadrži vrijednost NIL. Mi cemoćemo smatrat ove NIL-ove kao pokazivacepokazivače prema vanjskim cvorovimačvorovima (listovima) binarnog stabla a normalne cvorovečvorove koje sadrže kljuceve kao unutarnje cvorovečvorove stabla.
 
Binarno stablo je crveno-crno stablo ako zadovoljava sljedeca crveno-crna svojstva:
# Svaki cvorčvor je ili crven ili crn.
# Korijen je crn.
# Svaki list (NIL) je crn.
# Ako je cvorčvor crven, onda su oba njegova djeteta crna.
# Za svaki cvorčvor, svaki put od njegova cvoračvora do listova koji su mu potomci sadržava isti broj crnih čvorova.
 
[[Slika:Crveno_crna_stabla_slika_2.jpg |thumb|350px|left|Crveno-crno stabla s crnim cvorovimačvorovima i crvenim cvorovimačvorovima. Svaki cvorčvor u crveno-crnom stablu je ili crven ili crn, a djeca od crvenoga cvoračvora su oba crna te svaki a jednostavni put od cvoračvora do lista potomka sadrži isti broj crnih cvorovačvorova. (a) Svaki list, prikazan kao NIL, je crn. Svaki ne-NIL cvorčvor je oznacenoznač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. TakoderTakođer su u stablu izostavljene crne-visine cvorovačvorova. Korijenov roditelj je takodertakođer stražarska oznaka. (c) Isto crveno crno stablo ali sa izostavljenim listovima i roditeljevim korijenom. Ovaj cemo stil koristiti u ostatku ovog rada.]]
Kao pogodnost pri radu s ogranicenimogranič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 obicni cvorčvor u stablu. Njegovo polje boja je CRNA, dok njegova druga polja - p, lijevo, desno i kljuc mogu biti postavljane na proizvoljne vrijednosti. Kao što slika 1(b) pokazuje, svi pokazivacipokazivači na NIL su zamijenjeni pokazivacimapokazivačima na oznaku nil[T].
 
Koristimo stražarsku oznaku tako da možemo tretirati NIL dijete cvoračvora x kao standardni cvorčvor cijičiji je roditelj x. Iako smo umjesto toga mogli dodati razliciturazlič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.
OpcenitoOpćenito se ogranicavamoograničavamo na unutrašnje cvorovečvorove crveno-crnoga stabla, buduci da oni sadržavaju vrijednosti kljucevaključeva. U ostatku ovog rada izostavljamo listove prilikom crtanja crveno-crnih stabla, kao što je prikazano na slici 1(c).
Broj crnih čvorova na svakom putu od x-a, ali ne uključujuci x, do pojedinog lista zovemo crna - visina čvora i oznacavamo 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.
 
Broj crnih cvorova na svakom putu od x-a, ali ne ukljucujuci x, do pojedinog lista zovemo crna - visina cvora i oznacavamo sa bh(x). Po svojstvu petom svojstvu crveno-crnih stabala, ideja crne-visine je dobro definirana jer svi silazi putovi od cvora imaju isti broj crnih cvorova. 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.
Line 34 ⟶ 32:
 
 
Crveno-crno stablo sa n unutrašnjih cvorovačvorova ima visinu od najviše 2log(n+1).
 
*Dokaz
PocinjemoPočinjemo pokazujuci da podstablo s korijenom u bilo kojem cvoručvoru x sadrži barem 2bh(x) – 1 unutrašnjih cvorovačvorova. Dokazujemo ovu tvrdnju matematickommatematič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 2bh(x) - 1 = 20 - 1 = 0. unutrašnjih cvorovačvorova. Za korak indukcije, smatrajmo da cvorčvor x ima pozitivnu vrijednost te da je unutrašnji cvorč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. Buduci da je visina djeteta od x manja od same vrijednosti x, možemo primjeniti induktivnu hipotezu da zakljucimo da svako dijete ima barem 2bh(x) - 1 unutarnjih cvorovačvorova. Stoga podstablo s korijenom u x sadrži barem (2bh(x) - 1 ) + (2bh(x)-1 - 1) + 1 = 2bh(x) – 1 unutrašnjih cvorovačvorova što dokazuje tvrdnju.
 
Da se završi dokaz teorema, neka h bude visina stabla. Prema svojstvu 4, barem polovica cvorovač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 = 2h/2 - 1.
 
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.)
Direktna posljedica ovoga teorema je ta da dinamicki 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živackome stablu visine h, a svako crveno-crno stablo s n cvorova je pretraživacko 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živackim 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 ==
Line 58 ⟶ 54:
 
 
 
ROTIRAJ-ULIJEVO (T, x)
1 y ← desno[x] ▹ postavi y.
2 desno[x] ← lijevo[y] ▹ promijeni y-ovo lijevo podstablo u x-evo desno podstablo
Line 73 ⟶ 69:
 
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, budući da 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] = RED
5 then boja[p[z]] ← BLACK ▹ Slučaj 1
6 boja[y] ← BLACK ▹ Slučaj 1
7 boja[p[p[z]]] ← RED ▹ 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.
[[Slika:RB-INSERT-FIXUP.jpg |thumb| 350 px | right | Slika 4: Djelovanje procedure RB-INSERT-FIXUP. (a) Čvor z poslije umetanja. Budući da su z i njegov roditelj p[z] oboje crveni, narušava se peto svojstvo. Budući da je z-ev ujak y crven, možemo primjeniti prvi slučaj u kodu. Čvorovi su prebojani i pokazivač z je pomaknut prema gore u stablu, što rezultira stablom prikazanim pod (b). Još jednom da ponovimo - z i njegov roditelj su crveni, ali z-ev ujak y je crn. Budući da je z desno dijete od p[z], slučaj dva se može primjeniti. Obavljena je rotacija ulijevo, i stablo koje rezultira njome je prikazano pod (c). Sada je z lijevo dijete svojih roditelja, i slučaj tri se može primjeniti. Desna rotacija stvara stablo pod (d), koje je ispravno crveno-crno stablo. ]]
 
Koje se od svojstava crveno-crnih stabala može prekršiti pri pozivu procedure RB-INSERT-FIXUP? <br>
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, budući da č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 zbog toga jer 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. <br>
While petlja u linijama 1-15 održava sljedeće trodijelne invarijante: <br>
Na početku svake iteracije petlje <br>
a. Čvor z je crven <br>
b. Ako je p[z] korijen , onda je p[z] crn. <br>
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. <br>
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. <br>
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. <br>
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. <br> <br>
 
• '''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: <br>
a. Kada je procedura RB-INSERT-FIXUP pozvana, z je crveni čvor koji je dodan. <br>
b. Ako je p[z] korijen, onda je p[z] crn i nije se promjenio 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. <br>
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. <br>
• '''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. <br>
• '''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, budući da 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. <br>
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, budući da je njegov roditelj p[z] crven, a svojstvo 4 se krši samo između z i p[z]. <br>
'''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.
[[Slika:Umetanje cvorova.jpg |thumb|350px|left |Slika 5: Slučaj 1 procedure RB-INSERT. Svojstvo 4 je narušeno jer su i z i njegov roditelj p[z] crveni. Isti postupak se ponovi ovosno o tome je li (a) z desno dijete ili (b) z lijevo dijete. Svako od podstabla α, β, γ, δ i ε ima crni korijen, i svaki ima istu crnu-visinu. Kod za slučaj 1 mijenja boju nekih čvorova, održavajući svojstvo 5. While petlja nastavlja s djedom p[p[z]] 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′]. <br>
'''Slučaj 2: z-ev ujak y je crn i z je desno dijete''' <br>
'''Slučaj 3: z-ev ujak y je crn i z je lijevo dijete''' <br>
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. <br>
[[Slika:Slucaj 2 i 3 umetanje.jpg|thumb|350px|left | Slika 6: Slučajevi 2 i 3 procedure RB-INSERT. Kao u slučaju 1, svojstvo 4 je prekršeno ili u slučaju 2 ili u slučaju 3 budući da su z i njegov roditelj p[z] oboje crveni. Svako od podstabala α, β, γ, i δ ima crni korijen (α, β, i γ iz svojstva 4, i δ zbog toga što bi inače bili u slučaju 1) i svaki ima istu crnu-visinu. Slučaj 2 je transformiran u slučaj 3 rotacijom uklijevo koja zadržava svojstvo5: svaki put prema dolje od čvora do lista ima isti broj crnih čvorova. Slučaj 3 uzrokuje neke promjene boje i rotaciju udesno, pri čemu je isto očuvano svojstvo 5. While petlja se tada prekida, pošto je je svojstvo 4 zadovoljeno: ne postoje dva crvena čvora jedan za drugim. ]]
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.)<br>
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. <br>
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. <br>
c. Kao u slučaju 1, svojstva 1, 3 i 5 su održavana se u slučajevima 2 i 3. <br>
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, budući da 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.
 
 
Line 148 ⟶ 237:
 
[[Slika:Brisanje crveno-crnoga stabla.jpg |thumb| 400px| left|
Slika 37: 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 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. <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 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. <br> <br>
Dobavljeno iz "https://hr.wikipedia.org/wiki/Crveno-crno_stablo"