Црвено-црно стабло — разлика између измена

<li> Број црних чворова на сваком путу од једног чвора стаблестабла до њему припадајућих листова је једнак.

Ових пет услова осигурава најважнију особину једног црвено-црног стабла: Број чворова на најдужем путу од корена до једног листа стабла никада није већи од двоструког броја чворова на најкраћем путу од корана до једног листа стабла. Овиме је стабло увек приближно балансираноизбалансирано, што значи да је ефикасност операција претраживања стабла, додавање новог елемента и брисање елемента из стабла, које су његове главне функције, оптимална.

Горе је већ наведено да црвено-црна стабла имају загарантовано време претраживања не веће од <math>O( \log_{2}{n})</math>, при чему је -{n}- број њихових елемената. Следи доказ да је висина -{h}- једног црвено-црног стабла са -{n}- елемената увек мања или једнака од <math>2 \log_{2}{log_2(n+1)}</math>.

'''Претпоставка (за -{S}- > 0}-)'''

Под претпоставком да је <math>x</math> један подчвор, он мора имати тачно двоје деце (<math>x_1</math> и <math>x_2</math> ). Уколико је <math>S(x) = k</math>, <math>S</math> сваког његовог детета је или <math>k</math> или <math>k-1</math> зависно од тога да ли је дете црвено или црно. Како је -{S}- свакога од деце чвора -{x}- мање или једнако -{S(x)}-, може се применити индукционаиндуктивна претпоставка да свако од деце има <math>2^{S(x)-1}-1</math> подчворова. С тиме следи да је број подчворова чвора -{x}- мањи или једнак <math>(2^{S(x)-1}-1) + (2^{S(x)-1}-1)+1 = 2^{S(x)}-1</math>. Тиме је лема доказана.