Crveno-crno stablo: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
m uklonjena promjena suradnika 2A00:F41:1C0D:1EF0:DC59:4597:8A2B:3E53 (razgovor), vraćeno na posljednju inačicu suradnika Dexbot Oznaka: brzo uklanjanje |
m lektura (budući da -> jer) |
||
Redak 2:
'''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 [[podatak]]a, kao što su [[broj]]evi. 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 [[Korijen (biljke)|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 [[stablo|stablu]].
Ako čvor nema djece, zovemo ga listovni čvor ili [[list]] (engl. ''leaf node''),
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.
Redak 24:
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,
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.
Redak 95:
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,
RB-INSERT-FIXUP(T, z)
Redak 117:
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,
While petlja u linijama 1-15 održava sljedeće trodijelne invarijante: <br>
Na početku svake iteracije petlje <br>
Redak 134:
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,
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,
'''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.
Redak 150:
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>
[[Datoteka:Slucaj 2 i 3 umetanje.jpg|mini|350px|lijevo| 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
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,
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.
| |||