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

1. Svaki cvor je ili crven ili crn. <br>

2. Korijen je crn. <br>

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

5. Za svaki cvor, svaki put od njegova cvora do listova koji su mu potomci sadržava isti broj crnih čvorova. <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>