Inačica od 14. prosinca 2007. u 03:27 uredi Metropolis (razgovor \| doprinosi) 149 edits Nema sažetka uređivanja ← Starija izmjena		Inačica od 31. prosinca 2007. u 13:05 uredi ukloni ovu izmjenu MayaSimFan (razgovor \| doprinosi) 25.134 edits →‎Umetanje: szb Novija izmjena →
Redak 114: 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> Line 161 ⟶ 159: === 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 ==

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