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

С Википедије, слободне енциклопедије
Садржај обрисан Садржај додат
Ред 7: Ред 7:


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

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

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



== Доказ ефикасности ==
== Доказ ефикасности ==

Верзија на датум 31. август 2006. у 20:28

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

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


Особине

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

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


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

Доказ ефикасности

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

Горе је већ наведено да црвено-црна стабла имају загарантовано време претраживања не веће од , при чему је n број њихових елемената. Следи доказ да је висина h једног црвено-црног стабла са n елемената увек мања или једнака од .

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

Лема

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

Доказ леме

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

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

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


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

Под претпоставком да је један подчвор, он мора имати тачно двоје деце ( и ). Уколико је , сваког његовог детета је или или зависно од тога да ли је дете црвено или црно. Како је S свакога од деце чвора x мање или једнако S(x), може се применити индукциона претпоставка да свако од деце има подчворова. С тиме следи да је број подчворова чвора x мањи или једнак . Тиме је лема доказана.

Доказ

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

Тиме је доказано да је максимална висина h једног црвено-црнг дрва са n елемената , што значи да је брзина приступа неком од његових елеманата .