Изворни код странице Црвено-црно стабло

Појам '''црвено-црног стабла''' се у [[информатика|информатици]] везује за једну од [[бинарно стабло|бинарног стабла]] изведену [[структура података|структуру података]] која због пет правила, која свако црвено-црно стабло пре тренутка употребе треба да испуњава, гарантује одређену брзину приступа сваком од њених елемената, зависно од њиховог броја. Конкретно, балансираност, која следи из поменутих правила, гарантује да време приступа елементу стабла са -{n}- елемената неће бити веће од <math>O(\log_{2}{n})</math>, независно од измене количине података у стаблу.

О црвено-црним стаблима је по први пут говорио [[1972]]. године [[Рудолф Бајер]], који их је назвао „симетричним бинарним б-стаблима“. За данашње име су заслужни -{Leo J. Guibas}- и [[Роберт Седгевик]], који су [[1978]]. увели црвено-црну конвенцију.

== Особине ==
[[Слика:Red-black tree example.svg|450п|десно]]
Једно црвено-црно стабло има форму бинарног стабла, с тим што сваки његов чвор носи и додатни податак о својој боји - црвеној или црној. Свако овакво стабло задовољава и следећих пет услова:
<br><br>
<ol>
<li> Сваки чвор стабла је или црвен или црн
<li> Корен стабла је црн
<li> Сваки лист (нул-чвор) је црн
<li> Ниједан црвени чвор нема црвене деце
<li> Број црних чворова на сваком путу од једног чвора стабла до њему припадајућих листова је једнак.
</ol>
<br>
Ових пет услова осигурава најважнију особину једног црвено-црног стабла: Број чворова на најдужем путу од корена до једног листа стабла никада није већи од двоструког броја чворова на најкраћем путу од корана до једног листа стабла. Овиме је стабло увек приближно избалансирано, што значи да је ефикасност операција претраживања стабла, додавање новог елемента и брисање елемента из стабла, које су његове главне функције, оптимална.

== Доказ ефикасности ==
Брзина приступа елементима бинарног стабла зависи од апсолутне висине стабла, јер је време потребно за досезање елемента стабла који је најудаљенији од корена њој пропорционално.

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

Са циљем доказа ове особине, прво се мора увести лема о броју под-чворова стабла коју касније треба довести у везу са четвртом особином црвено-цних стабала.

=== Лема ===

Свако подстабло од чвора -{x}- садржи најмање <math>2^{S(x)} - 1</math> под-чворова где је -{S(x)}- заправо број црних чворова који се налазе испод чвора -{x}-.

=== Доказ леме ===
Помоћу математичке индукције се добија:

'''Почетак (-{S = 0}-)'''
У случају да је -{S=0}-, ради се о нул-чвору, који нема деце. Број подчворова оваквог чвора је искључиво нула.

<math>2^0 - 1 = 1 - 1 = 0</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>
\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
\end{matrix}
</math>

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

== Спољашње везе ==
{{Commonscat|Red-black trees}}
*[https://web.archive.org/web/20070311100421/http://fbim.fh-regensburg.de/~saj39122/gikasch/applet.html Графичка репрезентација понашања црвено-црног стабла] (јава-аплет, [https://web.archive.org/web/20070102085821/http://fbim.fh-regensburg.de/~saj39122/gikasch/start.html изворна страница])

== Види још ==
* [[Бинарно стабло]]
* [[АВЛ-стабло]]
* [[Б-стабло]]

== Литература ==
* Скрипта за предмет „Информатика 2“ са Универзитета Карлсруе, Немачка

{{подножје|Информатика и рачунарство}}
[[Категорија:Структуре података]]