Црвено-црно стабло — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
м →Доказ |
||
Ред 46:
=== Доказ ===
Разматрањем четврте особине црвено-црних стабала, следи да је на једном путу од корена до листа стабла висине -{h}- најмање половина чворова црна, што значи да је -{S}- од корена стабла најмање половина -{h}-. Према горе доказаној леми следи да је број елемената стабла увек већи или једнак <math>2^
Тиме је доказано да је максимална висина -{h}- једног црвено-црнг дрва са -{n}- елемената <math>2 \log_{2}{n+1}</math>, што значи да је брзина приступа неком од његових елеманата <math>O( \log_{2}{n})</math>.
| |||