section_heading: Umetanje
paragraph_text: 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, jer 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.