Википедија

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

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Ред 7:
 
Једно црвено-црно стабло има форму бинарног стабла, с тим што сваки његов чвор носи и додатни податак о својој боји - црвеној или црној. Свако овакво стабло задовољава и следећих пет услова:
<br><br>
 
<ol>
1. Сваки чвор стабла је или црвен или црн
2.<li> КоренСваки чвор стабла је или црвен или црн
3.<li> СвакиКорен лист (нул-чвор)стабла је црн
<li> Сваки лист (нул-чвор) је црн
4.<li> Ни један црвени чвор нема црвене деце
5.<li> Број црних чворова на сваком путу од једног чвора стабле до њему припадајућих листова је једнак.
 
</ol>
<br>
Ових пет услова осигурава најважнију особину једног црвено-црног стабла: Број чворова на најдужем путу од корена до једног листа стабла никада није већи од двоструког броја чворова на најкраћем путу од корана до једног листа стабла. Овиме је стабло увек приближно балансирано, што значи да је ефикасност операција претраживања стабла, додавање новог елемента и брисање елемента из стабла, које су његове главне функције, оптимална.
 
 
== Доказ ефикасности ==
Преузето из „https://sr.wikipedia.org/wiki/Црвено-црно_стабло”