AVL ДеревоTree

Фактор баланса узла x — это height(x.left) - height(x.right). Инвариант AVL требует, чтобы этот фактор был в множестве {-1, 0, 1} для каждого узла дерева. После обычной BST-вставки фактор баланса может нарушиться (стать 2 или -2) у одного или нескольких узлов на пути от нового узла к корню — восстановление идёт снизу вверх, и достаточно исправить самый нижний нарушенный узел: одна из четырёх ротаций (в зависимости от того, в какое поддерево внешнего или внутреннего потомка была сделана вставка) восстанавливает баланс на этом узле и — что важно — восстанавливает исходную высоту поддерева, поэтому дальнейшего распространения проверки вверх не требуется.A node x's balance factor is height(x.left) - height(x.right). The AVL invariant requires this factor to be in {-1, 0, 1} for every node in the tree. After a normal BST insertion, the balance factor can become violated (turn into 2 or -2) at one or more nodes on the path from the new node up to the root — the fix works bottom-up, and it's enough to fix the lowest violated node: one of four rotations (depending on which subtree of an outer or inner child the insertion landed in) restores balance at that node and — crucially — restores the subtree's original height, so no further upward propagation is needed.

Четыре случая: LL (вставка в левое поддерево левого ребёнка) — одна правая ротация; RR (симметрично) — одна левая ротация; LR (вставка в правое поддерево левого ребёнка) — левая ротация левого ребёнка, затем правая ротация самого узла; RL — симметрично, правая затем левая. При удалении может потребоваться до O(log n) ротаций вдоль всего пути до корня (в отличие от вставки, где хватает одной), потому что удаление способно уменьшить высоту поддерева, и это уменьшение может каскадом нарушать баланс у предков.Four cases: LL (insertion into the left subtree of a left child) — one right rotation; RR (symmetric) — one left rotation; LR (insertion into the right subtree of a left child) — a left rotation of the left child, then a right rotation of the node itself; RL — symmetric, right then left. Deletion can require up to O(log n) rotations along the entire path to the root (unlike insertion, where one suffices), because deletion can shrink a subtree's height, and that shrink can cascade balance violations up through the ancestors.

struct Node {
    int key, height = 1;
    Node* left = nullptr;
    Node* right = nullptr;
};

int h(Node* n) { return n ? n->height : 0; }
int balance(Node* n) { return n ? h(n->left) - h(n->right) : 0; }
void update(Node* n) { n->height = 1 + std::max(h(n->left), h(n->right)); }

Node* rotate_right(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    update(y); update(x);          // порядок важен: сначала старый корень// order matters: old root first
    return x;                        // x — новый корень поддерева// x is the new subtree root
}

Node* insert(Node* node, int key) {
    if (!node) return new Node{key};
    if (key < node->key) node->left = insert(node->left, key);
    else if (key > node->key) node->right = insert(node->right, key);
    else return node;
    update(node);
    int b = balance(node);
    if (b > 1 && key < node->left->key)  return rotate_right(node);              // LL// LL
    if (b < -1 && key > node->right->key) return rotate_left(node);               // RR// RR
    if (b > 1 && key > node->left->key)  { node->left = rotate_left(node->left); return rotate_right(node); }  // LR// LR
    if (b < -1 && key < node->right->key) { node->right = rotate_right(node->right); return rotate_left(node); } // RL// RL
    return node;
}

Вставка проигрывается автоматически: спуск до места вставки, затем подъём с пересчётом высот, и, если фактор баланса вышел за {-1,0,1} — ротация, подсвеченная отдельным шагом. Кнопки-пресеты специально вызывают каждый из четырёх случаев (LL, RR, LR, RL).Insertion auto-plays: descend to the insertion point, then climb back up recomputing heights, and if the balance factor falls outside {-1,0,1} — a rotation, highlighted as its own step. The preset buttons specifically trigger each of the four cases (LL, RR, LR, RL).

Наихудший случай AVL-дерева (дерево Фибоначчи, где каждый узел — минимально возможный по числу узлов для своей высоты) даёт высоту не более 1.4405 log₂(n+2) - 0.3277 — практически неотличимо от идеального log₂ n. Это самый строгий баланс среди деревьев поиска общего назначения, который обычно используется на практике: цена — потенциально больше ротаций на вставку/удаление, чем у более расслабленных схем вроде красно-чёрного дерева (2.3.2.3), потому что инвариант жёстче и нарушается чаще.An AVL tree's worst case (a Fibonacci tree, where every node is the minimum possible node count for its height) gives a height of at most 1.4405 log₂(n+2) - 0.3277 — practically indistinguishable from an ideal log₂ n. This is the strictest balance among general-purpose search trees commonly used in practice: the cost is potentially more rotations per insert/delete than looser schemes like a red-black tree (2.3.2.3), because the invariant is tighter and gets violated more often.