TechCodeview

Пре разумевања Црвено-црно дрво и АВЛ дрво разлике, требало би да знамо за црвено-црно стабло и АВЛ стабло одвојено.

Шта је црвено-црно дрво?

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

Својства

Ово су својства повезана са црвено-црним стаблом:

• Коренски чвор дрвета треба да буде црн.
• Црвени чвор може имати само црну децу. Или, можемо рећи да два суседна чвора не могу бити црвене боје.
• Ако чвор нема лево или десно дете, онда се за тај чвор каже да је листни чвор. Дакле, стављамо леву и десну децу испод лисног чвора познатог као нула

Дубина црне боје или висина црног чвора листа може се дефинисати као број црне боје на коју наилазимо када се крећемо од лисног чвора до коренског чвора. Једно од кључних својстава црвено-црног дрвета је да сваки чвор листа треба да има исту дубину црне боје.

Хајде да разумемо ово својство кроз пример.

У горњем стаблу постоји пет чворова, од којих је један црвени, а друга четири црна. У горњем дрвету постоје три чвора листа. Сада израчунавамо дубину црне боје сваког чвора листа. Као што можемо приметити да је дубина црне боје сва три листа листа 2; дакле, то је црвено-црно дрво.

Ако се дрво не повинује ниједном од три наведена својства, онда није црвено-црно дрво.

Висина црвено-црног дрвета

Размотрите х као висину стабла које има н чворова. Која би била најмања вредност н?. Вредност н је најмања када су сви чворови црни. Ако дрво садржи све црне чворове, онда би дрво било потпуно бинарно стабло. Ако је висина комплетног бинарног стабла х, онда је број чворова у стаблу:

н = 2х -1

Која би била највећа вредност н?

Вредност н је највећа када сваки црни чвор има два црвена детета, али црвени чвор не може имати црвену децу, тако да ће имати црну децу. На овај начин се наизменично налазе слојеви црне и црвене деце. Дакле, ако је број црних слојева х, онда је и број црвених слојева х; дакле, укупна висина дрвета постаје 2х. Укупан број чворова је:

н = 2*2х-1

Шта је АВЛ стабло?

Ан АВЛ дрво је самобалансирајуће бинарно стабло претраге ако посматрамо следећи случај, који је бинарно стабло претраге и уравнотежено стабло.

У горњем дрвету, временска сложеност у најгорем случају за претрагу елемента је О(х), тј. висина стабла. У горњем случају, број поређења направљених за претрагу 17 елемента је 4, а висина стабла је такође 4.

Ако узмемо у обзир искривљено бинарно стабло, као што је приказано у наставку:

У горњем десном искошеном стаблу, број поређења направљених за претрагу 17 елемента је 5, а број елемената присутних у стаблу је такође 5. Према томе, можемо рећи да ако је дрво искривљено бинарно стабло онда је временска сложеност би било О(н).

Сада, морамо да избалансирамо ова искривљена стабла тако да имају временску сложеност О(х). Постоји термин познат као а фактор равнотеже , који се користи за само-балансирање бинарног стабла претраге. Фактор баланса се може израчунати као:

Вредност фактора биланса може бити 1, 0 или -1. Ако сваки чвор у бинарном стаблу има вредност или 1, 0 или -1, онда се за то дрво каже да је уравнотежено бинарно дрво или АВЛ стабло.

Стабло је познато као савршено уравнотежено стабло ако је фактор равнотеже сваког чвора 0. АВЛ стабло је скоро избалансирано стабло јер сваки чвор у стаблу има вредност фактора равнотеже 1, 0 или -1.

Разлике између црвено-црног стабла и АВЛ стабла.

Следе разлике између црвено-црног стабла и АВЛ стабла:

Бинарно стабло претраге

Црвено-црно стабло је бинарно стабло претраге, а АВЛ стабло је такође бинарно стабло претраге.

Правила

У црвено-црном дрвету се примењују следећа правила:

1. Чвор у црвено-црном стаблу је црвене или црне боје.
2. Боја коренског чвора треба да буде црна.
3. Суседни чворови не би требало да буду црвени. Другим речима, можемо рећи да црвени чвор не може имати црвену децу, али црни чвор може имати црну децу.
4. Требало би да постоји исти број црних чворова на свакој путањи; тада се само дрво може сматрати црвено-црним дрветом.
5. Спољни чворови су нула чворови, који су увек црне боје.

Правило АВЛ стабла:

Сваки чвор треба да има фактор равнотеже као -1, 0 или 1.

нумерисано писмо

Пример

На горњој слици морамо да проверимо да ли је дрво црвено-црно дрво или не. Да бисмо ово проверили, прво морамо да проверимо да ли је дрво бинарно стабло претраге или не. Као што можемо приметити на горњој слици да она задовољава сва својства бинарног стабла претраге; дакле, то је бинарно стабло претраге. Друго, морамо да проверимо да ли задовољава горенаведена правила или не. Горње стабло задовољава свих горе наведених пет правила; стога закључује да је горе наведено дрво црвено-црно дрво.

На горњој слици морамо да проверимо да ли је дрво АВЛ стабло или не. Како сваки чвор има вредност фактора равнотеже као -1, 0 или 1, то је АВЛ стабло.

Како се дрво може сматрати уравнотеженим стаблом или не?

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

У случају АВЛ стабла, ако је фактор равнотеже -1, 0 или 1, онда се за горе наведено дрво каже да је АВЛ стабло.

Алати који се користе за балансирање

Ако дрво није уравнотежено, тада се користе два алата за балансирање стабла у црвено-црном стаблу:

Рецолоринг Ротација

Ако дрво није избалансирано, онда се користи један алат за балансирање стабла у АВЛ стаблу:

Ротација

Ефикасан за коју операцију

У случају црвено-црног стабла, операције уметања и брисања су ефикасне. Ако се стабло избалансира кроз поновно бојење, онда су операције уметања и брисања ефикасне у црвено-црном стаблу.

У случају АВЛ стабла, операција претраживања је ефикасна јер захтева само један алат за балансирање стабла.

Временска сложеност

У случају црвено-црног стабла, временска сложеност за све операције, тј. уметање, брисање и претраживање је О(логн).

У случају АВЛ стабла, временска сложеност за све операције, тј. уметање, брисање и претраживање је О(логн).

Хајде да разумемо разлике у табеларном облику.