| Strukture podataka i algoritmi |
| 8.2.1 Dodavanje u crveno-crno stablo |
Ovde je primer dodavanja u crveno-crno stablo (Cormen, str. 269).
 |
Ovde je originalno stablo. U sledecim dijagramima, crni strazarski (NULL) cvorovi su izostavljeni kako bi se pojednostavili dijagrami. |
 |
Pozvana je procedura tree_insert za dodavanje
cvora "4" u stablo. Ovo vise nije crveno-crno stablo - postoje dva uzastopna crvena cvora na putu 11 - 2 - 7 - 5 - 4 Oznacimo novi cvor sa x, i njegovog ujaka sa y. y je crven, pa imamo slucaj 1 ... |
 |
Promenimo boje cvorova 4, 7 i 8. |
 |
Postavimo x na mesto njegovog dede, cvora 7.
Roditelj cvora x (2) je crven, pa ovo jos uvek nije crveno-crno stablo. Oznacimo ujaka sa y. U ovom slucaju, ujak je crn, pa imamo slucaj 2 ... |
 |
Pomerimo x nagore i primenimo levu rotaciju. |
 |
Jos uvek nije crveno-crno stablo. Ujak je crn, ali je roditelj cvora x sa leve strane. |
 |
Promenimo boje cvorova 7 i 11 i primenimo desnu rotaciju. |
 |
Ovo je sada crveno-crno stablo,
pa smo zavrsili!
O(logn) koraka! |
|
Nazad na Crveno-crna stabla Nazad na Sadrzaj |