Пре него што сазнамо о разликама између стабла бинарног претраживања и АВЛ стабла, требало би да знамо о стаблу бинарне претраге и АВЛ стаблу одвојено.
Шта је стабло бинарног претраживања?
Тхе бинарно стабло претраге је дрво бинарно дрво . Као што знамо, то дрво може имати 'н' број деце, док; бинарно дрво може садржати највише два детета. Дакле, ограничење бинарног стабла је такође праћено бинарним стаблом претраге. Сваки чвор у бинарном стаблу претраге треба да има највише два детета; другим речима, можемо рећи да је стабло бинарног претраживања варијанта бинарног стабла.
Стабло бинарне претраге такође прати својства бинарне претраге. У бинарном претраживању, сви елементи у низу морају бити сортирани. Средњи елемент израчунавамо у бинарној претрази у којој леви део средњег елемента садржи вредност мању од средње вредности, а десни део средњег елемента садржи вредности веће од средње вредности.
У бинарном стаблу претраге, средњи елемент постаје коренски чвор, десни део постаје десно подстабло, а леви део постаје лево подстабло. Стога можемо рећи да је стабло бинарног претраживања комбинација а бинарно дрво и бинарно претраживање .
Напомена: Бинарно стабло претраге се може дефинисати као бинарно стабло у коме су сви елементи левог подстабла мањи од коренског чвора, а сви елементи десног подстабла већи од коренског чвора.
Временска сложеност у бинарном стаблу претраге
Ако је стабло бинарног претраживања скоро уравнотежено стабло онда ће све операције имати временску сложеност О(пријава) јер је претрага подељена или на лево или десно подстабло.
полицајци
Ако је стабло бинарне претраге нагнуто улево или удесно, онда ће све операције имати временску сложеност од На) јер треба да пређемо до н елемената.
Шта је АВЛ дрво?
Ан АВЛ дрво је самобалансирајуће бинарно стабло претраге где разлика између висина левог и десног подстабла не може бити већа од један. Ова разлика је позната као фактор равнотеже. У АВЛ стаблу, вредности фактора равнотеже могу бити или -1, 0 или 1.
Како се дешава самобалансирање бинарног стабла претраге?
Као што знамо да је АВЛ стабло самобалансирајуће бинарно стабло претраге. Ако стабло бинарног претраживања није избалансирано, може се самостално избалансирати са неким преуређивањем. Ова преуређења се могу урадити коришћењем неких ротација.
Хајде да разумемо самобалансирање кроз пример.
Претпоставимо да желимо да убацимо 10, 20, 30 у АВЛ стаблу.
10 на степен 6
Следећи начини уметања 10, 20, 30 у АВЛ стабло:
Корак 1: Прво, креирамо стабло бинарне претраге, као што је приказано у наставку:
Корак 2: На горњој слици можемо приметити да је дрво неуравнотежено јер је фактор равнотеже чвора 30 2. Да бисмо га учинили АВЛ стаблом, потребно је да извршимо неке ротације. Ако извршимо десну ротацију на чвору 20, онда ће се чвор 30 померити надоле, док ће се чвор 20 померити нагоре, као што је приказано испод:
Као што можемо приметити, коначно стабло прати својство стабла бинарног претраживања и уравнотеженог стабла; дакле, то је АВЛ дрво.
У случају, дрво је било лево неуравнотежено дрво, па вршимо праву ротацију на чвору.
Корак 1: Прво креирамо стабло бинарне претраге као што је приказано у наставку:
Корак 2: На горњој слици можемо приметити да је дрво неуравнотежено јер је фактор равнотеже чвора 10 -2. Да бисмо то учинили АВЛ стаблом, потребно је да извршимо неке ротације. То је десно неуравнотежено дрво, па ћемо извршити ротацију лево. Ако извршимо ротацију улево на чвору 20, онда ће се чвор 20 померити нагоре, а чвор 10 надоле, као што је приказано испод:
Као што можемо приметити, коначно стабло прати својство Стабло бинарног претраживања и а уравнотежено дрво ; дакле, то је АВЛ дрво.
Корак 1: Прво креирамо стабло бинарне претраге као што је приказано у наставку:
Корак 2: На горњој слици можемо приметити да је дрво неуравнотежено јер је фактор равнотеже коренског чвора 2. Да бисмо га учинили АВЛ стаблом, потребно је да извршимо неке ротације. Горњи сценарио је неуравнотежен лево-десно јер је један чвор лево од његовог родитељског чвора, а други је десно од његовог родитељског чвора. Прво ћемо извршити леву ротацију, а ротација се дешава између чворова 10 и 20. Након леве ротације, 20 ће се померити нагоре, а 10 надоле као што је приказано испод:
Ипак, дрво је неуравнотежено, па вршимо праву ротацију на стаблу. Када се изврши права ротација на стаблу, онда би дрво желело, као што је приказано у наставку:
Као што можемо приметити у горњем стаблу, дрво прати својство стабла бинарног претраживања и уравнотеженог стабла; дакле, то је АВЛ дрво.
Корак 1: Прво, креирамо стабло бинарне претраге, као што је приказано у наставку:
Корак 2: На горњој слици можемо приметити да је дрво неуравнотежено јер је фактор равнотеже коренског чвора 2. Да бисмо га учинили АВЛ стаблом, потребно је да извршимо неке ротације. Горњи сценарио је неуравнотежен десно-лево јер је један чвор десно од свог родитељског чвора, а други чвор лево од његовог родитељског чвора. Прво ћемо извршити десну ротацију која се дешава између чворова 30 и 20. Након десне ротације, 20 ће се померити нагоре, а 30 надоле као што је приказано испод:
Ипак, горе наведено стабло је неуравнотежено, тако да морамо да извршимо ротацију улево на чвору. Када се изврши лева ротација, чвор 20 ће се померити нагоре, а чвор 10 ће се померити надоле као што је приказано испод:
како претворити цхар у стринг
Као што можемо приметити у горњем стаблу, дрво прати својство стабла бинарног претраживања и уравнотеженог стабла; дакле, то је АВЛ дрво.
Разлике између стабла бинарног претраживања и АВЛ стабла
| Стабло бинарног претраживања | АВЛ дрво |
|---|---|
| Свако бинарно стабло претраге је бинарно стабло јер оба стабла садрже највише два детета. | Свако АВЛ стабло је такође бинарно стабло јер АВЛ дрво такође има највише два детета. |
| У БСТ-у не постоји термин који постоји, као што је фактор равнотеже. | У АВЛ стаблу, сваки чвор садржи фактор равнотеже, а вредност фактора равнотеже мора бити или -1, 0 или 1. |
| Свако стабло бинарне претраге није АВЛ стабло јер БСТ може бити или уравнотежено или неуравнотежено стабло. | Свако АВЛ стабло је бинарно стабло претраге јер АВЛ стабло прати својство БСТ-а. |
| Сваки чвор у стаблу бинарне претраге састоји се од три поља, тј. левог подстабла, вредности чвора и десног подстабла. | Сваки чвор у АВЛ стаблу састоји се од четири поља, тј. левог подстабла, вредности чвора, десног подстабла и фактора равнотеже. |
| У случају бинарног стабла претраге, ако желимо да убацимо било који чвор у стабло онда упоређујемо вредност чвора са основном вредношћу; ако је вредност чвора већа од вредности основног чвора, онда се чвор убацује у десно подстабло, иначе се чвор убацује у лево подстабло. Када је чвор уметнут, нема потребе за провером фактора равнотеже висине да би уметање било завршено. | У случају АВЛ стабла, прво ћемо пронаћи одговарајуће место за уметање чвора. Када је чвор уметнут, израчунаћемо фактор равнотеже сваког чвора. Ако је фактор равнотеже сваког чвора задовољен, уметање је завршено. Ако је фактор равнотеже већи од 1, онда морамо да извршимо неке ротације да уравнотежимо дрво. |
| У стаблу бинарне претраге, висина или дубина стабла је О(н) где је н број чворова у стаблу бинарне претраге. | У АВЛ стаблу, висина или дубина стабла је О(логн). |
| Једноставна је за имплементацију јер морамо да пратимо својства Бинарне претраге да бисмо убацили чвор. | Сложено је за имплементацију јер у АВЛ стаблу прво морамо да конструишемо АВЛ стабло, а затим морамо да проверимо равнотежу висине. Ако је висина неуравнотежена, онда морамо да извршимо неке ротације да уравнотежимо дрво. |
| БСТ није уравнотежено дрво јер не прати концепт фактора равнотеже. | АВЛ стабло је висинско избалансирано дрво јер прати концепт фактора равнотеже. |
| Претраживање је неефикасно у БСТ-у када постоји велики број доступних чворова у стаблу јер висина није избалансирана. | Претраживање је ефикасно у АВЛ стаблу чак и када постоји велики број чворова у стаблу јер је висина уравнотежена. |