AVL-деревья

К разделу

1. Инвариант сбалансированности

Проблема обычного BST в том, что его высота зависит от порядка вставки и в худшем случае вырождается в список — O(n) вместо O(log n).

AVL-дерево — это BST, которое после каждой операции восстанавливает баланс так, чтобы высота всегда оставалась O(log n), независимо от порядка операций.

Главное свойство в том, что в AVL-дереве высоты двух поддеревьев любой вершины отличаются максимум на 1.

Чтобы это отслеживать, у каждой вершины хранится дополнительное поле — высота ее поддерева

Баланс вершины — разница между высотой левого и правого поддерева.

struct Node {
    T key;          // ключ
    int height;     // высота поддерева
    Node* left;     // левое поддерево
    Node* right;    // правое поддерево
};

Для любой вершины v баланс balanceFactor(v) принадлежит {-1, 0, 1}.

Если после вставки или удаления баланс какой-то вершины стал равен 2 или -2 — дерево нужно перестроить локально с помощью поворотов (см. раздел 3), не трогая порядок ключей.

---

2. Оценка высоты через числа Фибоначчи

AVL-дерево с $n$ ключами имеет высоту $h=O(\log n)$.

Доказательство. Высоту поддерева с корнем $x$ будем обозначать как $h(x)$, высоту поддерева $T$ — как $h(T)$.

Лемма. Пусть $m_h$ — минимальное число вершин в AVL-дереве высоты $h$. Тогда $m_h=F_{h+2}-1$, где $F_h$ — $h$-е число Фибоначчи.

Доказательство. Так как $m_h$ — минимальное число вершин в AVL-дереве высоты $h$, легко видеть, что $m_{h+2}=m_{h+1}+m_h+1$. Равенство $m_h=F_{h+2}-1$ докажем по индукции.

База индукции: $m_1=F_3-1$ — верно, так как $m_1=1$, $F_3=2$.

Индукционный переход: пусть $m_h=F_{h+2}-1$ верно. Тогда

$$m_{h+1}=m_h+m_{h-1}+1=(F_{h+2}-1)+(F_{h+1}-1)+1=F_{h+3}-1$$

Значит, равенство $m_h=F_{h+2}-1$ доказано.

Известно, что $F_h=\mathrm{\Omega }({\phi }^h)$, где $\phi ={\displaystyle \frac{\sqrt{5}+1}{2}}$. То есть

$$n⩾{\phi }^h$$

Логарифмируя по основанию $\phi$, получаем

$${\log }_{\phi }n⩾h$$

Таким образом, высота AVL-дерева из $n$ вершин — $O(\log n)$.

3. Малые и большие повороты

Когда после вставки или удаления баланс какой-то вершины становится 2 или -2, дерево восстанавливают поворотами, которые сохраняют порядок ключей.

3.1. Малые повороты

Пусть $x$ и $y$ — вершины, а $A,B,C$ - поддеревья.

Если баланс вершины $p$ равен 2 (то есть перекос влево) и при этом ее левый ребенок сам не перекошен вправо, то используем один правый поворот: левый ребенок y поднимается на место x, а сам x становится его правым ребенком.

При этом, $B$ становится левым потомком $p$, так как надо сохранить свойство BST о том, что все элементы $A$ < $y$ < все элементы $B$ < $x$ < все элементы $C$

Node* rotateRight(Node* p) {           // малый правый поворот
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixHeight(p);                      // обновляем высоту p после балансировки
    fixHeight(q);                      // обновляем высоту q после балансировки
    return q;                          // q становится новым корнем поддерева
}

Аналогично выполняется левый поворот: если перекос вправо, а правый ребенок не перекошен влево:

Node* rotateLeft(Node* q) {            // малый левый поворот
    Node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixHeight(q);
    fixHeight(p);
    return p;
}

3.2. Большие повороты

Малые повороты работают, если в дереве перекос вправо(влево) и левый ребенок не перекошен влево(вправо). Если же такое происходит, то нужен двойной поворот: сначала малый поворот на ребенке, чтобы выпрямить перекос внутри него, а затем малый поворот на самой вершине p.

Node* rotateLeftRight(Node* p) {       // большой LR-поворот
    p->left = rotateLeft(p->left);
    return rotateRight(p);
}

Node* rotateRightLeft(Node* p) {       // большой RL-поворот
    p->right = rotateRight(p->right);
    return rotateLeft(p);
}

Любой поворот, малый или большой, выполняется за O(1) — переставляется фиксированное число ссылок. Вся стоимость восстановления баланса дерева — это число вершин, к которым применяется rebalance на пути от места изменения до корня, то есть O(h) = O(log n).

---

4. Вставка с восстановлением баланса

Вставка в AVL-дерево происходит в три этапа:

1. обычная BST-вставка — спускаемся по дереву и подвешиваем новый узел на свободное место
2. обновление высот — у всех предков вставленного узла, от родителя до корня, пересчитывается высота
3. проверка баланса и повороты — если у какого-то предка баланс стал 2 или -2, применяется соответствующий поворот (раздел 3).

Все три шага естественно объединяются в одну рекурсивную функцию — rebalance вызывается для каждой вершины на обратном пути рекурсии, что заодно обновляет и высоту:

Node* insert(Node* p, T k) {
    if (p == nullptr)
        return new Node(k);            // высота нового листа = 0
    if (k < p->key)
        p->left = insert(p->left, k);
    else
        p->right = insert(p->right, k);
    return rebalance(p);
}

При вставке достаточно не более одного поворота (малого или большого) на все дерево, чтобы полностью восстановить баланс. Это связано с тем, что после поворота высота перестроенного поддерева возвращается к тому значению, которое было до вставки — а значит, у более высоких предков баланс уже не мог измениться, и подниматься выше незачем.

---

5. Удаление с восстановлением баланса

Удаление начинается так же, как в обычном BST — с тем же разбором трех случаев (удаляемый ключ меньше/больше текущего, либо найден и заменяется преемником при двух детях). Разница в том, что после удаления на каждом уровне обратного пути рекурсии тоже вызывается rebalance

Ключевое отличие от вставки заключается в том, что удаление вершины может уменьшить высоту поддерева, и, в отличие от вставки, это нельзя исправить одним поворотом, так как удаление могло изменить баланс сразу у нескольких предков подряд, вплоть до корня.

Поэтому при удалении в худшем случае требуется $O(\log n)$ поворотов (по одному на каждом уровне пути до корня), а не $O(1)$, как при вставке.