Црвено-црно стабло

Из Википедије, слободне енциклопедије

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

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


Особине[уреди]

Red-black tree example.svg

Једно црвено-црно стабло има форму бинарног стабла, с тим што сваки његов чвор носи и додатни податак о својој боји - црвеној или црној. Свако овакво стабло задовољава и следећих пет услова:

  1. Сваки чвор стабла је или црвен или црн
  2. Корен стабла је црн
  3. Сваки лист (нул-чвор) је црн
  4. Ни један црвени чвор нема црвене деце
  5. Број црних чворова на сваком путу од једног чвора стабла до њему припадајућих листова је једнак.


Ових пет услова осигурава најважнију особину једног црвено-црног стабла: Број чворова на најдужем путу од корена до једног листа стабла никада није већи од двоструког броја чворова на најкраћем путу од корана до једног листа стабла. Овиме је стабло увек приближно избалансирано, што значи да је ефикасност операција претраживања стабла, додавање новог елемента и брисање елемента из стабла, које су његове главне функције, оптимална.

Доказ ефикасности[уреди]

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

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

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

Лема[уреди]

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

Доказ леме[уреди]

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

Почетак (S = 0)

У случају да је S=0, ради се о нул-чвору, који нема деце. Број подчворова оваквог чвора је искључиво нула.

2^0 - 1 = 1 - 1 = 0


Претпоставка (за S > 0)

Под претпоставком да је x један подчвор, он мора имати тачно двоје деце (x_1 и x_2 ). Уколико је S(x) = k, S сваког његовог детета је или k или k-1 зависно од тога да ли је дете црвено или црно. Како је S свакога од деце чвора x мање или једнако S(x), може се применити индуктивна претпоставка да свако од деце има 2^{S(x)-1}-1 подчворова. С тиме следи да је број подчворова чвора x мањи или једнак (2^{S(x)-1}-1) + (2^{S(x)-1}-1)+1 = 2^{S(x)}-1. Тиме је лема доказана.

Доказ[уреди]

Разматрањем четврте особине црвено-црних стабала, следи да је на једном путу од корена до листа стабла висине h најмање половина чворова црна, што значи да је S од корена стабла најмање половина h. Према горе доказаној леми следи да је број елемената стабла увек већи или једнак 2^{h/2}-1. Одавде следи рачун:


\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}

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

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Црвено-црно стабло

Види још[уреди]

Литература[уреди]

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