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

нема резимеа измене
(са комонса слика)
<li> Сваки лист (нул-чвор) је црн
<li> Ни један црвени чвор нема црвене деце
<li> Број црних чворова на сваком путу од једног чвора стаблестабла до њему припадајућих листова је једнак.
</ol>
<br>
Ових пет услова осигурава најважнију особину једног црвено-црног стабла: Број чворова на најдужем путу од корена до једног листа стабла никада није већи од двоструког броја чворова на најкраћем путу од корана до једног листа стабла. Овиме је стабло увек приближно балансираноизбалансирано, што значи да је ефикасност операција претраживања стабла, додавање новог елемента и брисање елемента из стабла, које су његове главне функције, оптимална.
 
== Доказ ефикасности ==
Брзина приступа елементима бинарног стабла зависи од апсолутне висине стабла, јер је време потребно за досезање елемента стабла који је најудаљенији од корена њој пропорционално.
 
Горе је већ наведено да црвено-црна стабла имају загарантовано време претраживања не веће од <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>. Тиме је лема доказана.
 
=== Доказ ===
Разматрањем четврте особине црвено-црних стабала, следи да је на једном путу од корена до листа стабла висине -{h}- најмање половина чворова црна, што значи да је -{S}- од корена стабла најмање половина -{h}-. Према горе доказаној леми следи да је број елемената стабла увек већи или једнак <math>2^{h/2}-1</math>. Одавде следи рачун:
 
:<math>
Тиме је доказано да је максимална висина -{h}- једног црвено-црнг дрва са -{n}- елемената <math>2 \log_{2}{n+1}</math>, што значи да је брзина приступа неком од његових елеманата <math>O( \log_{2}{n})</math>.
\begin{matrix}
& n & \geq & 2^{\frac{h}{2}} - 1 \\
\Leftrightarrow & n + 1 & \geq & 2^{\frac{h}{2}} \\
\Leftrightarrow & \log_2(n+1) & \geq & \frac{h}{2} \\
\Leftrightarrow & 2 \log_2(n+1) & \geq & h \\
\Leftrightarrow & 2 \log_2(n+1) & \geq & h
\end{matrix}
</math>
 
Тиме је доказано да је максимална висина -{h}- једног црвено-црнг дрва са -{n}- елемената <math>2 \log_{2}{log_2(n+1})</math>, што значи да је брзина приступа неком од његових елеманата <math>O( \log_{2}{n})</math>.