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

Izbrisani sadržaj Dodani sadržaj
JAnDbot (razgovor | doprinosi)
Redak 49:
Mijenjamo strukturu pokazivača koristeći rotaciju, koja je lokalna operacija u pretraživačkom stablu koja održava svojstva binarnoga pretraživačkog stabla. <br>
Slika 2 pokazuje dvije vrste rotacija: rotacija ulijevo i rotacija udesno. Kada radimo rotaciju ulijevo na čvoru x, pretpostavljamo da desno dijete y nije nil[T] - x može biti bilo koji čvor u stablu čije desno dijete nije nil[T]. Lijeva se rotacija "vrti" oko veze od x prema y. Ona čini y novim korijenom podstabla, sa x kao y-ovo lijevo dijete, a staro y-ovo lijevo dijete postaje x-evo desno dijete. <br>
[[Datoteka:Rotacija stablaTree rotation.JPG png|mini300px|lijevo|Slika 2: Rotacija kao operacija na binarnom pretraživačkom stablu. Operacija ROTIRAJ-ULIJEVO (T, x) transformira konfiguraciju dva čvora na lijevoj strani u konfiguraciju na desnoj mijenjajući konstantni broj pokazivača. Konfiguracija na desnoj strani može biti transformirana u konfiguraciju na lijevoj strani inverznom operacijom ROTIRAJ-UDESNO (T, y) Slova α, β, i γ predstavljaju proizvoljna podstabla .Operacija rotacije čuva svojstva binarnih pretraživačkih stabala: ključevi u α prethode ključ[x], koji prethodi ključevima u β, koji pak prethodi ključ[y], koji prethodi ključevima u y ]]
 
Pseudokod za ROTIRAJ-ULIJEVO pretpostavlja da desno[x] ≠ nil[T] te da je korijenov roditelj nil[T].