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

Binarna pretraživacka stabla, ukljucujuci crveno-crna stabla, zadovoljava ogranicenje da svaki cvor sadržava vrijednost manju ili jednaku vrijednosti od vrijednosti desnog podcvora, a vecu ili jednaku od vrijednosti lijevog podcvora. Ovo omogucava brzo pretraživanje stabla za zadanu vrijednost i dopušta ucinkovito obilaženje (traversiranje) elemenata.

 

 

 

 

Crveno-crna stabla su binarna sortirana stabla s jednim dodatnim bitom prostora po cvoru: bojom koja može biti ili CRVENA ili CRNA. Nijedan put od korijena lista nije više od dva puta dulji od bilo koje drugog puta tako da je drvo otprilike balansirano. <br>

3. Svaki list (NIL) je crn. <br>

4. Ako je cvor crven, onda su oba njegova djeteta crna. <br>

 

 

''Slika 1: Crveno-crno stabla sa crnim cvorovima i crvenim cvorovima. Svaki cvor u crveno-crnom stablu je ili crven ili crn, a djeca od crvenoga cvora su oba crna te svaki a jednostavni put od cvora do lista potomka sadrži isti broj crnih cvorova. (a) Svaki list, prikazan kao NIL, je crn. Svaki ne-NIL cvor je oznacen svojom crnom-visinom. NIL ima crnu-visinu jednaku 0. (b) Isto crveno-crno stablo, ali sa svakim NIL zamijenjenim istom stražarskom oznakom nil[T] koja je uvijek crna. Takoder su u stablu izostavljene crne-visine cvorova. Korijenov roditelj je takoder stražarska oznaka. (c) Isto crveno crno stablo ali sa izostavljenim listovima i roditeljevim korijenom. Ovaj cemo stil koristiti u ostatku ovog rada.'' <br><br>

Kao pogodnost pri radu s ogranicenim uvjetima prilikom rada sa crveno-crnim stablima, koristimo jedinstvenu stražarsku oznaku da reprezentiramo NIL. Za crveno-crno stablo T stražarska oznaka nil[T] je objekt sa istim poljima kao obicni cvor u stablu. Njegovo polje boja je CRNA, dok njegova druga polja - p, lijevo, desno i kljuc mogu biti postavljane na proizvoljne vrijednosti. Kao što slika 1(b) pokazuje, svi pokazivaci na NIL su zamijenjeni pokazivacima na oznaku nil[T]. <br>

Koristimo stražarsku oznaku tako da možemo tretirati NIL dijete cvora x kao standardni cvor ciji je roditelj x. Iako smo umjesto toga mogli dodati razlicitu stražarsku oznaku za svaki NIL u stablu, tako da je roditelj svakoga NIL-a dobro definiran taj pristup bi trošio nepotreban prostor. Umjesto toga koristimo jednu stražarsku oznaku nil[T] da bismo predstavili sve NIL-ove listove i korijenov roditelj. Vrijednosti polja p, lijevo, desno i kljuc stražarske oznake su nevažni, iako ih možemo staviti ako nam cefne.