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

м
Разне исправке
м (Бот Мења: nl:Rood-zwartboom)
м (Разне исправке)
Појам '''црвено-црног стабла''' се у [[информатика|информатици]] везује за једну од [[бинарно стабло|бинарног стабла]] изведену [[структура података|структуру података]] која због пет правила, која свако црвено-црно стабло пре тренутка употребе треба да испуњава, гарантује одређену брзину приступа сваком од њених елемената, зависно од њиховог броја. Конкретно, балансираност, која следи из поменутих правила, гарантује да време приступа елементу стабла са -{n}- елемената неће бити веће од <math>O( \log_{2}{n})</math>, независно од измене количине података у стаблу.
 
О црвено-црним стаблима је по први пут говорио [[1972]]. године [[Рудолф Бајер]], који их је назвао „симетричним бинарним б-стаблима“. За данашње име су заслужни -{Leo J. Guibas}- и [[Роберт Седгевик]], који су [[1978]]. увели црвено-црну конвенцију.
Брзина приступа елементима бинарног стабла зависи од апсолутне висине стабла, јер је време потребно за досезање елемента стабла који је најудаљенији од корена њој пропорционално.
 
Горе је већ наведено да црвено-црна стабла имају загарантовано време претраживања не веће од <math>O( \log_{2}{n})</math>, при чему је -{n}- број њихових елемената. Следи доказ да је висина -{h}- једног црвено-црног стабла са -{n}- елемената увек мања или једнака од <math>2 \log_2(n+1)</math>.
 
Са циљем доказа ове особине, прво се мора увести лема о броју под-чворова стабла коју касније треба довести у везу са четвртом особином црвено-цних стабала.
</math>
 
Тиме је доказано да је максимална висина -{h}- једног црвено-црнг дрва са -{n}- елемената <math>2 \log_2(n+1)</math>, што значи да је брзина приступа неком од његових елеманата <math>O( \log_{2}{n})</math>.
 
== Спољашње везе ==
1.572.075

измена