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

 

== Razlike izmedu crveno-crnih stabala i binarnih pretraživačkih stabala ==

[[crvena|Crveno]]-[[crna]] stabla su binarna sortirana stabla s jednim dodatnim bitom prostora po čvoru: [[boja|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.

 

# 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].

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. <br>

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. <br>

 

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

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.

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.

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>

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>