AVL дерево

Все проблемы несбалансированных деревьев из-за высоты. Точнее, из-за большой разности высот поддеревьев. Давайте на основе этой разности введем фактор балансировки.

Для каждой узла $v$ определим height balance factor (фактор балансировки) — разницу высот правого и левого поддеревьев.

\bf v = \height(v.\code{left}) - \height(v.\code{right})

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

Давайте возьмём наименьшее из возможных требований для фактора балансировки. Потребуем, чтобы у всех узлов нашего дерева фактор балансировки по модулю не превосходил $1$ .

|\bf v| \le 1 \quad\text{для всех узлов}~ v

Это требование, как мы убедимся дальше, очень легко поддерживать. В 1962 году советские математики Георгий Максимович Адельсон-Вельский и Евгений Михайлович Ландис описали такой метод балансировки деревьев. Самобалансирующиеся деревья, которые мы с вами дальше будем строить и изучать, носят их имя — AVL-деревья.

Структура AVL дерева

Узел AVL-дерева содержит те же поля, что и узел обычного бинарного дерева поиска, плюс дополнительное поле balance для хранения своего фактора балансировки.

Также, для нормальной реализации всех алгоритмов без рекурсии, добавим поле parent, которое будет хранить ссылку на родителя узла.

struct node:
    ref node left
    ref node right
    ref node parent
    int balance

    key key
    some additional data

Можно, конечно, в узле хранить высоту его поддерева. Но если мы храним фактор балансировки, который может принимать только значения $0$ , $1$ и $-1$ , то мы дополнительно тратим всего $2$ бита вместо полного числа.

Итак, после операции вставки или удаления узла дерево может перестать быть сбалансированным, то есть у какой-то узла $|\bf v| > 1$ . Надо научиться возвращать дереву баланс.

Ключевое свойство, которое делает AVL-деревья эффективными: после вставки или удалении узла фактор балансировки может измениться только тех у узлов, которые лежат на пути от корня до вставленного или удаленного узла. И изменяется фактор балансировки на $1$ или на $-1$ . То есть это значит, что для восстановления баланса нам достаточно подняться от изменённого узла к корню, на каждом уровне проверить и при необходимости исправить баланс. Остановимся мы тогда, когда баланс перестанет меняться.

Повороты и восстановление баланса

Иногда так случается, что для какого-то узла $v$ перестаёт выполняться свойство $|\bf v| \le 1$ . Нужно это свойство восстанавливать.

Если у узла $v$ случилась разбалансировка, то обязательно $|\bf v| = 2$ . Связано это с тем, что у AVL-дерева всегда $|\bf v| \le 1$ , а модифицирующие операции (вставка узла и удаление узла) могут изменить фактор балансировки максимум на $1$ .

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

Повороты происходят относительно узла с нарушенным балансом и затрагивают только его детей и внуков — всего $O(1)$ узлов. При этом высота всего его поддерева обычно уменьшается на $1$ , что помогает восстановить баланс у родительских узлов при подъёме от изменённого узла к корню.

Обычные повороты.

Если знаки у факторов балансировки узла и его ребёнка одинаковые, то есть если направления разбалансировки совпадают, то нам достаточно просто совершить самый обычный поворот: ребёнок с перевешивающей стороны становится новым корнем поддерева, а разбалансированный узел сползает на место второго ребёнка.

Если фактор балансировки узла равен $2$ , а у его левого ребёнка фактор балансировки равен $1$ , то нужно выполнить правый поворот (на рисунке стрелка вправо).

Аналогично, если фактор балансировки узла равен $-2$ , а у его правого ребёнка фактор балансировки равен $-1$ , то нужно выполнить левый поворот (на рисунке стрелка влево). Результат симметричен результату правого поворота.

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

Если знаки у факторов балансировки узла и его ребёнка разные, то есть если направления разбалансировки не совпадают, то после обычного поворота узла дерево снова будет разбалансированным, но уже в другую сторону. Для того, чтобы исправлять такие ситуации, нам нужно совершать не один, а два поворота. Такой двойной поворот называется большим поворотом.

Большой правый поворот совершается, если поддерево разбалансировано влево, то есть если фактор балансировки у узла $2$ , а фактор балансировки у левого ребёнка узла равен $-1$ .

Большой правый поворот

Большой левый поворот совершается, если поддерево разбалансировано вправо, то есть если фактор балансировки у узла $-2$ , а фактор балансировки у правого ребёнка узла равен $1$ .

Большой левый поворот

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

Для удобства и чистоты реализации функции поворота должны возвращать новый корень поддерева.

function rotate_right(ref node a) -> ref node:
    ref node b = a.left

    assert a.balance == 2
    assert b.balance >= 0

    a.left = b.right

    if b.right is not null:
        b.right.parent = a

    b.right = a
    b.parent = a.parent
    a.parent = b

    if b.balance == 1:
        a.balance = 0
        b.balance = 0

    else if b.balance == 0:
        a.balance = 1
        b.balance = -1

    return b

function rotate_left(ref node a) -> ref node:
    ref node b = a.right

    assert a.balance == -2
    assert b.balance <= 0

    a.right = b.left

    if b.left is not null:
        b.left.parent = a

    b.left = a
    b.parent = a.parent
    a.parent = b

    if b.balance == -1:
        a.balance = 0
        b.balance = 0

    else if b.balance == 0:
        a.balance = -1
        b.balance = 1

    return b

Большие повороты можно явно реализовать по картинке, но, чтобы не мучаться с пересчётом факторов балансировки у вершин, можно реализовать каждый большой поворот через два обычных.

function big_rotate_left(ref node a) -> ref node:
    ref node b = a.right

    assert a.balance == -2
    assert b.balance == 1

    a.right = rotate_right(b)  # правый поворот вокруг b
    return rotate_left(a)      # левый поворот вокруг a

function big_rotate_right(ref node a) -> ref node:
    ref node b = a.left

    assert a.balance == 2
    assert b.balance == -1

    a.left = rotate_left(b)  # левый поворот вокруг b
    return rotate_right(a)   # правый поворот вокруг a

Вставка в AVL-дерево

Пусть нам надо добавить в дерево узел с ключом $t$ . Будем спускаться по дереву как при поиске ключа $t$ . Если мы стоим в узле $v$ и нам надо спуститься в поддерево, которого нет, то делаем новый узел листом, и узел $v$ его корнем.

Далее нам нужно подниматься вверх до корня, пересчитывая фактор балансировки у вершин и выполняя повороты. Если мы поднялись в вершину $w$ из левого поддерева, то $w.\code{balance}$ увеличивается на $1$ , а если из правого поддерева, то $w.\code{balance}$ уменьшается на $1$ .

После пересчёта фактора балансировки надо понять, что делать дальше. Если он равен $1$ или $-1$ , то мы продолжаем подниматься. Если он равен $0$ , то высота поддерева не изменилась, а значит можно заканчивать пересчёт. Если он оказался равным $2$ или $-2$ , делаем нужный поворот и снова смотрим на фактор балансировки нового корня поддерева.

Для каждого узла на пути от листа до корня мы сделаем не более одного поворота, и в любом случае будем подниматься вверх. Значит, на пересчёт факторов балансировки и на восстановление баланса мы потратим время $O(\text{высота дерева}) = O(\log n)$ , а точнее ...

function new_node(key t) -> ref node:
    return new node = {
        left = null,
        right = null,
        parent = null,
        balance = 0,
        key = t
    }

function insert(ref node root, key t) -> ref node:
    if root == null:
        return new_node(t)

    current = root
    while current is not null:
        if t < current.key:
            if current.left == null:
                current.left = new_node(t)
                current.left.parent = current
                current = current.left
                break
            current = current.left

        else if t > current.key:
            if current.right == null:
                current.right = new_node(t)
                current.right.parent = current
                current = current.right
                break
            current = current.right

        else:
            return root  # ключ уже существует

    # Поднимаемся вверх и балансируем
    while current is not null:
        parent = current.parent

        if parent is not null:  # Если есть родитель, обновляем его баланс
            if current == parent.left:
                parent.balance += 1
            else:
                parent.balance -= 1

            if parent.balance == 0: # высота не изменилась
                break

            else if parent.balance == 1 or parent.balance == -1:  # продолжаем подъем
                current = parent
                continue

            else if parent.balance == 2:  # нарушен баланс влево
                if parent.left.balance == 1:
                    new_root = rotate_right(parent)
                else:
                    new_root = big_rotate_right(parent)

            else if parent.balance == -2:  # нарушен баланс вправо
                if parent.right.balance == -1:
                    new_root = rotate_left(parent)
                else:
                    new_root = big_rotate_left(parent)

            # Обновляем ссылку у дедушки
            grandparent = parent.parent
            if grandparent is not null:
                if grandparent.left == parent:
                    grandparent.left = new_root
                else:
                    grandparent.right = new_root
            else:
                root = new_root  # обновили корень дерева

            # Решаем, продолжать ли подъем
            if new_root.balance == 0:
                break
            else:
                current = new_root

        else:  # current - корень, проверяем его баланс
            if current.balance == 2:
                if current.left.balance == 1:
                    root = rotate_right(current)
                else:
                    root = big_rotate_right(current)

            else if current.balance == -2:
                if current.right.balance == -1:
                    root = rotate_left(current)
                else:
                    root = big_rotate_left(current)

            break

    return root

Удаление вершины

Если удаляемый узел $d$ является листом, то удалим его. Если у него есть дети, то найдем ему замену $v$ — узел с наименьшим ключом в правом поддереве удаляемого узла $d$ , или узел с наибольшим ключом в левом поддереве удаляемого узла $d$ . Скопируем данные из $v$ в $d$ и удалим уже узел $d$ .

Далее нам нужно подниматься вверх от родителя фактически удалённого узла до корня, пересчитывая фактор балансировки у вершин и выполняя повороты. Если мы поднялись в вершину $w$ из левого поддерева, то $w.\code{balance}$ уменьшается на $1$ , а если из правого поддерева, то $w.\code{balance}$ увеличивается на $1$ .

После пересчёта фактора балансировки надо понять, что делать дальше. Если он равен $0$ , то высота поддерева уменьшилась, и мы продолжаем подниматься. Если он равен $1$ или $-1$ , то высота поддерева не изменилась, а значит можно заканчивать пересчёт. Если он оказался равным $2$ или $-2$ , делаем нужный поворот и снова смотрим на фактор балансировки нового корня поддерева.

function delete(ref node root, key t):
    if root == null:
        return

    # Поиск удаляемого узла
    current = root
    while current is not null:
        if t < current.key:
            current = current.left
        else if t > current.key:
            current = current.right
        else:
            break  # нашли узел для удаления

    if current == null:
        throw error  # узел не найден

    start_balance_from = null  # откуда начинать балансировку

    if current.left == null and current.right == null:  # узел - лист
        if current.parent is not null:
            if current.parent.left == current:
                current.parent.left = null
            else:
                current.parent.right = null
            start_balance_from = current.parent
        else:
            root = null  # удаляем единственный узел

        free current

    else if current.left == null:  # есть только правый ребёнок
        if current.parent is not null:
            if current.parent.left == current:
                current.parent.left = current.right
            else:
                current.parent.right = current.right
            current.right.parent = current.parent
            start_balance_from = current.parent
        else:
            root = current.right
            root.parent = null

        free current

    else if current.right == null:  # есть только левый ребёнок
        if current.parent is not null:
            if current.parent.left == current:
                current.parent.left = current.left
            else:
                current.parent.right = current.left
            current.left.parent = current.parent
            start_balance_from = current.parent
        else:
            root = current.left
            root.parent = null
        free current

    else:  # оба ребёнка
        successor = current.right
        while successor.left is not null:
            successor = successor.left

        copy from successor to current

        if successor.parent.left == successor:
            successor.parent.left = successor.right
        else:
            successor.parent.right = successor.right

        if successor.right is not null:
            successor.right.parent = successor.parent

        start_balance_from = successor.parent
        free successor

    if start_balance_from is null:
        return

    current = start_balance_from
    while current is not null:
        parent = current.parent

        if parent is not null:
            if current == parent.left:
                parent.balance -= 1
            else:
                parent.balance += 1

        if current.balance == 1 or current.balance == -1:  # высота не изменилась
            break

        else if current.balance == 0:  # продолжаем подъем
            current = current.parent
            continue

        else if current.balance == 2:  # нарушен баланс влево
            if current.left.balance >= 0:
                new_root = rotate_right(current)
            else:
                new_root = big_rotate_right(current)

        else if current.balance == -2:  # нарушен баланс вправо
            if current.right.balance <= 0:
                new_root = rotate_left(current)
            else:
                new_root = big_rotate_left(current)

        # Обновляем ссылки у родителя нового корня
        if new_root.parent is not null:
            if new_root.parent.left == current:
                new_root.parent.left = new_root
            else:
                new_root.parent.right = new_root
        else:
            root = new_root

        # Решаем, продолжать ли подъем
        if new_root.balance == 0:
            current = new_root.parent
        else:
            break

Разбалансировка деревьев

Пусть $|\bf v| \le b$ для всех узлов дерева. Давайте получим оценку высоты дерева.

Пусть $N(h)$ — минимальное количество узлов в дереве высоты $h$ . Из определения следует, что $N(0) = 0$ (пустое дерево) и $N(1) = 1$ (только один узел).

Для этого дерева выполнено условие баланса: $|\bf v| \le b$ для всех узлов дерева. Тогда для дерева высоты $h$ можно взять корень и разбить его на два поддерева. При этом для корня будет выполнено условие баланса. Значит,

N(h) = 1 + N(h-1) + N(h-1-b)

Решение уравнения этого экспоненциальное. Давайте найдем точную оценку для $N(h)$ , и, как следствие, для высоты $h$ .

Запишем сразу производящую функцию для $N(h)$ , учитывая, что $h \ge 0$ .

G(x) = \sum\limits_{h=0}^\oo N(h) \cdot x^h

Подставим внутрь функции уравнение $N(h) = 1 + N(h-1) + N(h-1-b)$

G(x) = \sum\limits_{h=0}^\oo \big(1 + N(h-1) + N(h-1-b) \big) \cdot x^h = \frac{1}{1-x} + x \cdot G(x) + x^{b+1} \cdot G(x)

Мы получили производящую функцию

G(x) = \frac{1}{(1-x) \cdot \big( 1 - x - x^{b+1} \big)}

Пусть полюсы функции $G(x)$ — точка $1$ и $b+1$ точка $\rho_k$ , при этом точки $\rho_k$ являются решением уравнения $1-x-x^{b+1} = 0$ . Тогда $G(x)$ можно разложить в сумму простых дробей

G(x) = - \frac{1}{1-x} + \sum\limits_{k=0}^b \frac{1}{(\rho_k - 1) \cdot (b \rho_k - b - 1)} \cdot \frac{1}{1-x/\rho_k}

Для удобства можно ввести другие переменные $\varphi_k = 1/\rho_k$ , которые являются корнями уравнения $\varphi_k^{b+1} - \varphi_k^b - 1 = 0$ . Тогда формула для $G(x)$ преобразуется в

G(x) = - \frac{1}{1-x} + \sum\limits_{k=0}^b \frac{\varphi_k^2}{(\varphi_k - 1) \cdot (b \varphi_k - b + \varphi_k)} \cdot \frac{1}{1 - \varphi_k \cdot x}

Коэффициент $N(h)$ при $x^h$ в производящей функции $G(x)$ вычисляются по теореме о представлении коэффициента рациональной производящей функции

N(h) = -1 + \sum\limits_{k=0}^b \frac{\varphi_k^{h+2}}{(\varphi_k - 1) \cdot (b \varphi_k - b + \varphi_k)}

Можно вывести отсюда грубоватую асимптотическую оценку $N(h)$ . Обозначим за $\varphi$ единственный действительный положительный корень. У него же будет максимальный модуль, а значит он вносит наибольший вклад в асимптотику.

N(h) = \frac{\varphi^2}{(\varphi - 1) \cdot (b \varphi - b + \varphi)} \cdot \varphi^h - 1 + O \big( \varphi^{-h} \big)

Теперь, зная $N(h) = n$ , мы можем получить оценку высоты сбалансированного дерева

h = \frac{1}{\log \varphi} \cdot \log n - \frac{1}{\log \varphi} \cdot \left( \frac{\varphi^2}{(\varphi - 1) \cdot (b \varphi - b + \varphi)} \right) + \frac{1}{n \cdot \log \varphi} + O \left( \frac{1}{n^2} \right)