AVL-дерево
Начните со случайного AVL-дерева и пошагово вставляйте, ищите или удаляйте значения: смотрите коэффициент баланса каждого узла, повороты LL, RR, LR и RL, представление в виде массива и подсветку кода C++.
Всё моделируется в этом браузере; ничего не отправляется на сервер.
Нет шагов
Нет шагов
AVL-дерево
Индекс в массиве · Коэффициент баланса
Представление в виде массива
Потомки индекса i находятся в 2i+1 и 2i+2.
- Не связан
- Уже пройден
- Сравнивается
- Найден
- Новый
- К удалению
- Преемник
- Разбалансирован
- Опорный
Нет шагов
Код
#include <iostream>
#include <algorithm>
using namespace std;
class Node { // Узел хранит значение и указатели на двух потомков
private: // Приватные атрибуты: к ним обращаются только методы
int value;
Node* left;
Node* right;
public:
Node(int v) : value(v), left(nullptr), right(nullptr) {}
int getValue() const { return value; }
Node* getLeft() const { return left; }
Node* getRight() const { return right; }
void setValue(int v) { value = v; }
void setLeft(Node* n) { left = n; }
void setRight(Node* n) { right = n; }
};
int height(Node* n) { // Высота: лист равен 1, пустое место (nullptr) равно 0
if (n == nullptr) return 0;
return 1 + max(height(n->getLeft()), height(n->getRight()));
}
int balanceFactor(Node* n) { // Коэффициент баланса: высота слева минус высота справа
return height(n->getLeft()) - height(n->getRight());
}
Node* rotateRight(Node* y) { // Простой поворот вправо: левый потомок x поднимается, y опускается
Node* x = y->getLeft();
y->setLeft(x->getRight());
x->setRight(y);
return x;
}
Node* rotateLeft(Node* x) { // Простой поворот влево: правый потомок y поднимается, x опускается
Node* y = x->getRight();
x->setRight(y->getLeft());
y->setLeft(x);
return y;
}
Node* rebalance(Node* n) { // Возвращает корень поддерева после балансировки
int bf = balanceFactor(n); // Вычисляется коэффициент баланса узла
if (bf > 1) { // Перекос влево. Если левый потомок не перекошен вправо, это случай LL
if (balanceFactor(n->getLeft()) < 0) // Левый потомок перекошен вправо: случай LR, сначала поворот влево
n->setLeft(rotateLeft(n->getLeft())); // Первый поворот случая LR
return rotateRight(n); // Поворот вправо: решает LL и вторую половину LR
}
if (bf < -1) { // Перекос вправо. Если правый потомок не перекошен влево, это случай RR
if (balanceFactor(n->getRight()) > 0) // Правый потомок перекошен влево: случай RL, сначала поворот вправо
n->setRight(rotateRight(n->getRight())); // Первый поворот случая RL
return rotateLeft(n); // Поворот влево: решает RR и вторую половину RL
}
return n; // Коэффициент от -1 до 1: поворот не нужен
}
Node* insert(Node* root, int v) { // Вставляет v в AVL-дерево и возвращает корень
if (root == nullptr) // Пустое место: новый узел помещается сюда
return new Node(v); // Создаёт новый узел
if (v < root->getValue()) // Меньшие значения идут влево, большие — вправо
root->setLeft(insert(root->getLeft(), v)); // Спускается в левое поддерево
else
root->setRight(insert(root->getRight(), v)); // Спускается в правое поддерево
return rebalance(root); // При возврате из каждого вызова проверяется баланс узла
}
int main() {
Node* root = buildTree(); // Показанное дерево, уже построенное
root = insert(root, v); // Первый вызов, из main
return 0; // Конец операции
}