Црвено-црно стабло — разлика између измена
Садржај обрисан Садржај додат
Ред 41:
'''Претпоставка (за -{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>. Тиме је лема доказана.
|