section_heading: Umetanje
paragraph_text: •	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 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. <br> Ako je narušeno svojstvo 4, onda zbog činjenice što su djeca čvora z crne stražarske oznake, kao i zbog toga što stablo nema drugih narušavanja prije nego što 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, 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. <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, jer 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. mini|350px|lijevo|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 ovisno 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 roditelja, ako je 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 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> 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 jer 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 ulijevo koja zadržava svojstvo 5: 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 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.)