АВЛ дрво су измислили ГМ Аделсон - Велски и ЕМ Ландис 1962. Дрво је названо АВЛ у част његових проналазача.
АВЛ стабло се може дефинисати као висинско уравнотежено бинарно стабло претраге у коме је сваки чвор повезан са фактором равнотеже који се израчунава одузимањем висине његовог десног подстабла од висине његовог левог подстабла.
За дрво се каже да је избалансирано ако је фактор равнотеже сваког чвора између -1 до 1, у супротном, дрво ће бити неуравнотежено и треба га избалансирати.
Фактор баланса (к) = висина (лево(к)) - висина (десно(к))
Ако је фактор равнотеже било ког чвора 1, то значи да је лево подстабло један ниво више од десног подстабла.
Ако је фактор равнотеже било ког чвора 0, то значи да лево подстабло и десно подстабло имају једнаку висину.
Ако је фактор равнотеже било ког чвора -1, то значи да је лево подстабло један ниво ниже од десног подстабла.
АВЛ стабло је дато на следећој слици. Видимо да је фактор равнотеже повезан са сваким чвором између -1 и +1. дакле, то је пример АВЛ стабла.
Сложеност
| Алгоритам | Просечан случај | Најгори случај |
|---|---|---|
| Спаце | на) | на) |
| Претрага | о(лог н) | о(лог н) |
| Уметните | о(лог н) | о(лог н) |
| Избриши | о(лог н) | о(лог н) |
Операције на АВЛ стаблу
Због чињенице да је АВЛ стабло такође бинарно стабло претраге, стога се све операције изводе на исти начин као што се изводе у бинарном стаблу претраге. Претраживање и прелазак не доводе до повреде својства АВЛ стабла. Међутим, уметање и брисање су операције које могу нарушити ово својство и стога их треба поново размотрити.
| СН | Операција | Опис |
|---|---|---|
| 1 | Инсертион | Уметање у АВЛ стабло се врши на исти начин као што се изводи у бинарном стаблу претраге. Међутим, то може довести до кршења својства АВЛ стабла и стога ће стаблу можда бити потребно балансирање. Дрво се може избалансирати применом ротација. |
| 2 | Брисање | Брисање се такође може извршити на исти начин као што се изводи у бинарном стаблу претраге. Брисање такође може пореметити равнотежу стабла, стога се за поновно балансирање дрвета користе различите врсте ротација. |
Зашто АВЛ дрво?
АВЛ стабло контролише висину бинарног стабла претраге тако што не дозвољава да буде искривљено. Време потребно за све операције у бинарном стаблу претраге висине х је О(х) . Међутим, може се проширити на На) ако БСТ постане искривљен (тј. у најгорем случају). Ограничавајући ову висину на лог н, АВЛ стабло намеће горњу границу за сваку операцију О(лог н) где је н број чворова.
АВЛ Ротатионс
Вршимо ротацију у АВЛ стаблу само у случају да је фактор баланса другачији од -1, 0 и 1 . У основи постоје четири врсте ротација које су следеће:
- Л Л ротација: Уметнути чвор је у левом подстаблу левог подстабла А
- Р Р ротација: Уметнути чвор је у десном подстаблу десног подстабла А
- Л Р ротација: Уметнути чвор је у десном подстаблу левог подстабла А
- Р Л ротација: Уметнути чвор је у левом подстаблу десног подстабла А
Где је чвор А чвор чији је фактор равнотеже другачији од -1, 0, 1.
Прве две ротације ЛЛ и РР су једноструке ротације, а следеће две ротације ЛР и РЛ су двоструке ротације. Да би дрво било неуравнотежено, минимална висина мора бити најмање 2, Хајде да разумемо сваку ротацију
1. РР Ротатион
Када БСТ постане неуравнотежен, због тога што је чвор уметнут у десно подстабло десног подстабла А, тада вршимо РР ротацију, РР ротација је ротација у супротном смеру казаљке на сату, која се примењује на ивици испод чвора који има фактор баланса -2
У горњем примеру, чвор А има фактор равнотеже -2 јер је чвор Ц уметнут у десно подстабло А десног подстабла. Изводимо РР ротацију на ивици испод А.
2. ЛЛ Ротатион
Када БСТ постане неуравнотежен, због тога што је чвор уметнут у лево подстабло левог подстабла Ц, тада вршимо ЛЛ ротацију, ЛЛ ротација је ротација у смеру казаљке на сату, која се примењује на ивици испод чвора који има фактор равнотеже 2.
У горњем примеру, чвор Ц има фактор равнотеже 2 јер је чвор А уметнут у лево подстабло Ц левог подстабла. Изводимо ЛЛ ротацију на ивици испод А.
3. ЛР ротација
Двоструке ротације су мало теже од једноструке ротације што је већ објашњено горе. ЛР ротација = РР ротација + ЛЛ ротација, тј. прво се врши РР ротација на подстаблу, а затим ЛЛ ротација се врши на пуном стаблу, под пуним стаблом подразумевамо први чвор са путање уметнутог чвора чији је фактор равнотеже другачији од -1 , 0 или 1.
Хајде да разумемо сваки корак веома јасно:
| Држава | поступак |
|---|---|
 | Чвор Б је уметнут у десно подстабло А лево подстабло Ц, због чега је Ц постао неуравнотежен чвор са фактором равнотеже 2. Овај случај је Л Р ротација где је: Уметнути чвор у десном подстаблу левог подстабла Ц |
 | Како је ЛР ротација = РР + ЛЛ ротација, стога се прво изводи РР (у смеру супротном од казаљке на сату) на подстаблу укорењеном у А. Вршењем РР ротације, чвор А , је постало лево подстабло Б . |
 | Након извођења РР ротације, чвор Ц је још увек неуравнотежен, тј. има фактор равнотеже 2, пошто је уметнути чвор А лево од лево од Ц |
 | Сада вршимо ЛЛ ротацију у смеру казаљке на сату на пуном стаблу, тј. на чвору Ц. чвор Ц је сада постало десно подстабло чвора Б, А је лево подстабло Б |
 | Фактор баланса сваког чвора је сада или -1, 0 или 1, тј. БСТ је сада уравнотежен. |
4. РЛ Ротација
Као што је већ речено, двоструке ротације су мало теже од једноструке ротације што је већ објашњено горе. Р Л ротација = ЛЛ ротација + РР ротација, тј. прво се врши ЛЛ ротација на подстаблу, а затим РР ротација се врши на пуном стаблу, под пуним стаблом подразумевамо први чвор са путање уметнутог чвора чији је фактор равнотеже другачији од -1 , 0 или 1.
| Држава | поступак |
|---|---|
 | Чвор Б је уметнуто у лево подстабло Ц десно подстабло од А , због чега је А постао неуравнотежен чвор са фактором равнотеже - 2. Овај случај је РЛ ротација где је: уметнути чвор у левом подстаблу десног подстабла А |
 | Како је РЛ ротација = ЛЛ ротација + РР ротација, дакле, ЛЛ (у смеру казаљке на сату) на подстаблу са кореном у Ц се прво изводи. Вршењем РР ротације, чвор Ц је постало право подстабло од Б . |
 | Након извођења ЛЛ ротације, чвор А је још увек неуравнотежен, тј. има фактор равнотеже -2, што је због десног подстабла чвора десног подстабла А. |
 | Сада изводимо РР ротацију (ротацију у супротном смеру казаљке на сату) на пуном стаблу, тј. на чвору А. чвор Ц је сада постало десно подстабло чвора Б, а чвор А је постао лево подстабло Б. |
 | Фактор баланса сваког чвора је сада или -1, 0 или 1, тј. БСТ је сада уравнотежен. |
П: Конструишите АВЛ стабло које има следеће елементе
Х, И, Ј, Б, А, Е, Ц, Ф, Д, Г, К, Л
1. Убацити Х, И, Ј
Убацивањем горњих елемената, посебно у случају Х, БСТ постаје неуравнотежен јер је фактор равнотеже Х -2. Пошто је БСТ искривљен удесно, извршићемо РР ротацију на чвору Х.
Резултантно стабло биланса је:
2. Уметак Б, А
Приликом уметања горњих елемената, посебно у случају А, БСТ постаје неуравнотежен јер је фактор равнотеже Х и И је 2, сматрамо први чвор из последњег уметнутог чвора, тј. Х. Пошто је БСТ из Х искривљен улево, извршићемо ЛЛ ротацију на чвору Х.
Резултантно стабло биланса је:
3. Убаците Е
повезана листа јава
Приликом уметања Е, БСТ постаје неуравнотежен јер је фактор равнотеже од И 2, пошто ако путујемо од Е до И откријемо да је уметнут у лево подстабло десног подстабла И, извршићемо ЛР ротацију на чвору И. ЛР = РР + ЛЛ ротација
3 а) Прво вршимо РР ротацију на чвору Б
Резултантно стабло након РР ротације је:
3б) Прво вршимо ЛЛ ротацију на чвору И
Резултантно уравнотежено стабло након ЛЛ ротације је:
4. Убаците Ц, Ф, Д
Приликом уметања Ц, Ф, Д, БСТ постаје неуравнотежен јер је фактор равнотеже Б и Х -2, пошто ако путујемо од Д до Б откријемо да је уметнут у десно подстабло левог подстабла Б, извршићемо РЛ Ротација на чвору И. РЛ = ЛЛ + РР ротација.
4а) Прво изводимо ЛЛ ротацију на чвору Е
Резултантно стабло након ЛЛ ротације је:
4б) Затим вршимо РР ротацију на чвору Б
Резултантно уравнотежено стабло након РР ротације је:
5. Убаците Г
Приликом уметања Г, БСТ постаје неуравнотежен јер је фактор равнотеже Х 2, пошто ако путујемо од Г до Х, нађемо да је уметнут у лево подстабло десног подстабла Х, извршићемо ЛР ротацију на чвору И. ЛР = РР + ЛЛ ротација.
5 а) Прво вршимо РР ротацију на чвору Ц
Резултантно стабло након РР ротације је:
5 б) Затим вршимо ЛЛ ротацију на чвору Х
Резултантно уравнотежено стабло након ЛЛ ротације је:
6. Уметнути К
Након уметања К, БСТ постаје неуравнотежен јер је фактор равнотеже од И -2. Пошто је БСТ десно искошен од И до К, стога ћемо извршити РР ротацију на чвору И.
Резултантно уравнотежено стабло након РР ротације је:
7. Убацити Л
Приликом уметања Л стабло је и даље уравнотежено јер је фактор равнотеже сваког чвора сада или -1, 0, +1. Дакле, дрво је балансирано АВЛ дрво
