Увод у АВЛ стабло у структури података
Дрво АВЛ у структури података односи се на дрво Аделсон, Велски и Ландис. Ово је побољшана верзија стабла бинарног претраживања. Има све карактеристике као Бинарно стабло претраживања, али разликује се само по томе што одржавају разлику између висине левог потбла и десног пот дрвета, а такође гарантују да је његова вредност <= 1 на дрвету, то је познато као баланс Фактор.
Balance Factor = height(left-subtree) − height(right-subtree)
На пример: Размотрите следећа стабла
У горњем примјеру, висина десног пот дрвета = 2 и лијева = 3 тако је БФ = 2 што је <= 1, па се каже да је дрво уравнотежено.
Зашто нам треба ДСЛ стабло у ДС-у?
Док радимо са Бинарним стаблом претраживања, наилазимо на сценарио где су елементи поредани. У таквим су случајевима сви елементи матрице распоређени на једној страни коријена, што доводи до повећања временске сложености претраживања елемента у низу и сложеност постаје -О (н), тј. Најгора сложеност стабла . Да би се решили такви проблеми и смањило време тражења, АВЛ стабла су изумили Аделсон, Велски и Ландис.
Пример:
На горњој слици висина левог поддрева = 3 била је једнака
Висина десног поддрева = 0
Тако је фактор равнотеже = 3-0 = 3. Стога тражење елемента у таквом дрвету има сложеност О (н) која је слична линеарној претрази. Да би се избегла сложена претрага АВЛ стабло је уведено тамо где сваки чвор на стаблу мора да одржава
фактор равнотеже <= 1, иначе се морају извршити различите технике ротације да би се уравнотежило такво дрво.
Struct AVLNode
(
int data;
struct AVLNode *left, *right;
int ball factor;
);
Врсте ротација
Када фактор равнотеже за дрво не задовољава <= 1 услов, тада треба вршити ротације на њима да би га претворили у уравнотежено стабло.
Постоје 4 врсте ротације:
1. Лева ротација: Ако додавање чвора десно од стабла прави неравнотежу, у том случају треба извршити ротацију улево.
2. Десна ротација: Ако додавање чвора лево од стабла прави чвор неравнотежу, тада треба да се изврши десна ротација. Другим речима, када се број левова повећава на левој страни, појављује се потреба да се елементи померају на десну страну да би се то уравнотежило, па се каже да је то десна ротација.
3. Ротација лево-десно: Ова врста ротације је комбинација горе објашњених 2 ротације. Ова врста ротације се дешава када се један елемент дода у десно под дрво левог стабла.
У таквом случају прво изведите ротацију улево на поддрвету, а затим десну ротацију левог стабла.
4. Десно-лево окретање : Ова врста ротације је такође састављена од низа изнад 2 ротације. Ова врста ротације је потребна када се дода елемент са леве стране десног поддрева и дрво постане неуравнотежено. У таквом случају прво извршавамо десну ротацију у десној подлози, а затим леву ротацију на десном стаблу.
Операције на АВЛ стаблу у ДС-у
Испод 3 операције које се могу извести на АВЛ стаблу: -
1. Тражи
Ова операција је слична претраживању у Бинарном стаблу за претрагу. Следећи кораци су следећи:
- Прочитајте елемент који је дао корисник рецимо к.
- Упоредите елемент из корена, ако је исти онда изађите у супротном пређите на следећи корак.
- Ако је к
Идите код правог детета и упоредите поново.
Пратите процесе Б и Ц док не пронађете елемент и изађете.
Овај процес има сложеност О (лог н).
Пример:
 | Размотрите ово Дрво где морамо да претражимо вредност чвора 9. Прво пустите к = 9, вредност роот-а (12)> к, а вредност мора бити у левом подрему коријенског елемента. |
 | Сада се к упоређује са вредности чвора 3 к> 3 стога морамо кренути према правом подрези. |
 | Сада се к упоређује са чвором (9), где је 9 == 9 враћа тачно. Дакле, тражење елемената се завршава на дрвету. |
2. Убацивање
Приликом уметања елемента у АВЛ стабло морамо пронаћи одређени елемент који мора бити уметнут и затим је елемент везан исто као и уметање у БСТ, али након тога се проверава је ли дрво још увек уравнотежено или не тј. фактор равнотеже чвора је <= 1. И одређене ротације се изводе по потреби.
Сложеност је О (лог н).
Пример: Размотрите доле стабло,
 | Сваки чвор има фактор равнотеже као 0, -1 или 1 тако да је дрво уравнотежено. Сада дозвољавамо шта се дешава када се убаци чвор са вредностом 1. Прво стабло се прелази да би пронашло место где га треба убацити… 1 <2 се тако пише као лево дете од чвора (2). |
 | Након уметања, чвор (9) постаје неуравнотежен са фактором равнотеже = 2. Сада је подвргнут правој ротацији. |
 | Дрво постаје равнотежа након ротације десно и на тај начин операција уметања је успешно завршена. |
3. Брисање
Брисање елемента у стаблу АВЛ такође укључује претраживање елемента у стаблу и његово брисање. Операција претраге иста је као и БСТ, а након проналаска елемента који се брише уклања се елемент са стабла и елементи се прилагођавају тако да поново постану БСТ. Након провере ових елемената да има фактор равнотеже 0, -1 или 1 и на тај начин се извршавају погодне ротације како би се он уравнотежио.
Сложеност ако је О (лог н).
 | Размотрите дано стабло, чији сви имају фактор равнотеже 0, -1 или 1. Сада ћемо избрисати чвор са вриједношћу 16. Прво стабло се прелази да би пронашло чвор са вредношћу 16 исто као алгоритам за претраживање. |
 | Чвор 16 ће бити замењен претходним редоследом овог чвора који је највећи елемент са левог поддрвета тј. 12 Дрво је постало неуравнотежено, па је потребно извршити ротацију ЛЛ. |
 | Сада је сваки чвор постао уравнотежен. |
Закључак - АВЛ стабло у структури података
АВЛ стабло је потомак Бинарног стабла за претраживање, али превазилази недостатак повећане сложености у случају да се елементи сортирају. Она прати фактор равнотеже дрвета да буде 0 или 1 или -1. У случају да стабло постане неуравнотежено, одговарајуће технике ротације се изводе за балансирање стабла.
Препоручени чланци
Ово је водич за АВЛ стабло у структури података. Овде смо разговарали о уводу, операцијама на АВЛ стаблу у ДС-у и врстама ротација. Можете и да прођете кроз остале сродне чланке да бисте сазнали више -
- јКуери Елементс
- Шта је наука о подацима
- Врсте стабала у структури података
- Ц # типови података