Обяснение на AVL Tree Insertion, Rotation и Balance Factor

Какво е AVL дърво?

Дървото на AVL е подтип на двоично дърво за търсене. Името на изобретателите Adelson, Velskii и Landis, AVL дърветата имат свойството на динамично самобалансиране в допълнение към всички свойства, изложени от бинарни дървета за търсене.

BST е структура от данни, съставена от възли. Той има следните гаранции:

  1. Всяко дърво има корен възел (в горната част).
  2. Коренният възел има нула, един или два дъщерни възела.
  3. Всеки дъщерен възел има нула, един или два дъщерни възела и т.н.
  4. Всеки възел има до две деца.
  5. За всеки възел неговите леви потомци са по-малко от текущия възел, което е по-малко от десните потомци.

AVL дърветата имат допълнителна гаранция:

  1. Разликата между дълбочината на дясно и ляво поддървета не може да бъде повече от една. За да се поддържа тази гаранция, изпълнението на AVL ще включва алгоритъм за ребалансиране на дървото, когато добавянето на допълнителен елемент би нарушило тази гаранция.

AVL дърветата имат най-лошия случай на търсене, вмъкване и изтриване на времето на O (log n).

Право въртене

Дърво AVL Въртене

Ляво завъртане

Ляво завъртане на дърво AVL

Процес на въвеждане на AVL

Ще направите вмъкване, подобно на нормалното вмъкване на бинарно дърво за търсене. След вмъкването поправяте свойството AVL, като използвате ляво или дясно завъртане.

  • Ако има дисбаланс в лявото дете на дясно поддърво, тогава извършвате въртене наляво-надясно.
  • Ако има дисбаланс в лявото дете на лявото поддърво, тогава правите дясно завъртане.
  • Ако има дисбаланс в дясното дете на дясно поддърво, тогава извършвате ляво завъртане.
  • Ако има дисбаланс в дясното дете на лявото поддърво, тогава извършвате въртене надясно-наляво.

Дървото на AVL е самобалансиращо се двоично дърво за търсене. Дървото на AVL е двоично дърво за търсене, което има следните свойства: -> Поддърветата на всеки възел се различават по височина най-много с едно. -> Всяко поддърво е AVL дърво.

Дървото AVL проверява височината на лявото и дясното под-дървета и гарантира, че разликата не е по-голяма от 1. Тази разлика се нарича фактор на баланса. Височината на AVL дърво винаги е O (Logn), където n е броят на възлите в дървото.

Завъртания на дърво AVL

В дървото AVL, след извършване на всяка операция като вмъкване и изтриване, трябва да проверим коефициента на баланс на всеки възел в дървото. Ако всеки възел отговаря на условието за балансиращ фактор, тогава ние заключаваме операцията, в противен случай трябва да го направим балансиран. Използваме операции на въртене, за да направим дървото балансирано винаги, когато дървото става дисбалансирано поради някаква операция.

Операциите на въртене се използват за балансиране на дървото. Има четири завъртания и те се класифицират в два вида:

Единично ляво завъртане (LL завъртане)

При LL Rotation всеки възел се премества с една позиция наляво от текущата позиция.

Еднократно дясно завъртане (RR завъртане)

При RR Rotation всеки възел се придвижва с една позиция надясно от текущата позиция.

Ляво дясно завъртане (LR завъртане)

LR завъртането е комбинация от единично ляво завъртане, последвано от единично дясно завъртане. При LR завъртане първо всеки възел премества една позиция наляво, след това една позиция надясно от текущата позиция.

Въртене отдясно наляво (RL завъртане)

RL Rotation е комбинация от единично дясно завъртане, последвано от единично ляво завъртане. В RL Rotation, първо всеки възел премества една позиция надясно, след това една позиция наляво от текущата позиция.

Анализ на времето на AVL дървета

AVL дървото е двоично дърво за търсене с допълнително свойство, че разликата между височината на лявото поддърво и дясното поддърво на който и да е възел не може да бъде повече от 1.

Алгоритъм Средно Най-лош случай: Пространство:, O(n)Време:O(n)

Приложение на AVL дървета

AVL дърветата са полезни в случаите, когато проектирате някаква база данни, където вмъкванията и изтриванията не са толкова чести, но трябва често да търсите елементите, присъстващи там.