Crveno-crno stablo: razlika između inačica
Izbrisani sadržaj Dodani sadržaj
m →Umetanje: lektura, replaced: promjenio → promijenio using AWB |
|||
Redak 129:
• '''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
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>
| |||