Сбалансированные деревья поиска. Включение: повороты и балансировка

Модуль "Деревья поиска" • урок 4 из 8 • ~8 минут

Нарушение баланса при включении

Процесс включения нового узла в АВЛ-дерево начинается точно так же, как и в обычном дереве поиска: мы спускаемся от корня к листьям и добавляем новый элемент на свободное место. Однако добавление узла увеличивает высоту поддерева. Это может привести к тому, что для некоторого узла на пути от корня к новому элементу баланс станет равным +2 или -2.

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

Сбалансированные деревья поиска. Включение: четыре типа поворотов

В зависимости от того, в какую ветвь был добавлен новый узел, выделяют четыре случая нарушения баланса. Пусть C - узел, у которого нарушился баланс (он стал +2 или -2), B - его потомок со стороны перевеса, а A - новый узел. Именно так эти узлы названы и в коде ниже.

• LL-случай (Левое-Левое): Новый узел был добавлен в левое поддерево левого потомка узла C. Исправляется малым правым поворотом.
• RR-случай (Правое-Правое): Новый узел был добавлен в правое поддерево правого потомка. Исправляется малым левым поворотом.
• LR-случай (Левое-Правое): Новый узел добавлен в правое поддерево левого потомка. Исправляется большим поворотом: сначала левый поворот нижних узлов, затем правый поворот вокруг верхнего.
• RL-случай (Правое-Левое): Новый узел добавлен в левое поддерево правого потомка. Исправляется большим поворотом: сначала правый поворот, затем левый поворот.

Визуализация: малый правый поворот (случай LL)

В АВЛ-дерево из двух узлов 50 и 25 приходит ключ 10. Баланс узла 50 становится равным -2, а его левый потомок перевешивает влево - это и есть случай LL.

Визуализация: большой поворот (случай LR)

Если в то же дерево вместо 10 приходит ключ 35, левый потомок перевешивает вправо. Одним поворотом такой дисбаланс не снять: сначала левый поворот сводит случай LR к уже разобранному LL, и только потом работает правый поворот.

Реализация на языке C (правый поворот)

На уровне указателей операция поворота выполняется очень быстро O(1), так как нам нужно перебросить всего несколько связей.

typedef struct node {
    int key, height;
    struct node *l, *r;
} node;

int h(node* p) { return p ? p->height : 0; }
void fix(node* p) { p->height = 1 + (h(p->l) > h(p->r) ? h(p->l) : h(p->r)); }

// Малый правый поворот вокруг C (случай LL). Возвращает новый корень поддерева.
node* rotateRight(node* C) {
    node* B = C->l;     // B поднимается наверх
    C->l = B->r;        // правое поддерево B становится левым поддеревом C
    B->r = C;          // C опускается вправо вниз
    fix(C);            // пересчитать высоты (сначала нижний узел)
    fix(B);
    return B;          // возвращаем новый корень поддерева
}