AVL-дерево — это самобалансирующееся бинарное дерево поиска, в котором:
• Баланс-фактор (разница высот левого и правого поддерева) каждого узла равен -1, 0 или 1.
• При нарушении баланса выполняется ротация (левая, правая или двойные) для восстановления баланса.
Баланс-фактор (BF) узла вычисляется так:
BF = Height(Left) - Height(Right)
• BF = 0, 1 или -1 — дерево сбалансировано.
• BF > 1 — перегрузка слева.
• BF < -1 — перегрузка справа.
🤔 Что такое ротация в деревьях?
Ротация — это операция, которая переставляет узлы в бинарном дереве, изменяя их структуру без нарушения свойств дерева.
Когда высота левого и правого поддерева отличается более чем на 1, дерево становится разбалансированным. Это снижает эффективность операций поиска, вставки и удаления.
Виды ротаций в AVL-дереве:
1️⃣ Правое вращение
Применяется, когда перегрузка слева (BF > 1) и новый узел добавлен в левое поддерево левого потомка.
Простой пример:
C
/
B
/
A
После правого вращения:
B
/ \
A C
2️⃣Левое вращение
Применяется, когда перегрузка справа (BF < -1) и новый узел добавлен в правое поддерево правого потомка.
Пример:
A
\
B
\
C
После левого вращения:
B
/ \
A C
3️⃣ Лево-правое вращение
Используется при перегрузке слева, если новый узел добавлен в правое поддерево левого потомка.
Сначала выполняется левое вращение для левого потомка.
Затем правое вращение для корня.
4️⃣ Право-левое вращение
Используется при перегрузке справа, если новый узел добавлен в левое поддерево правого потомка.
Сначала выполняется правое вращение для правого потомка.
Затем левое вращение для корня.