Красно-чёрное дерево

Балансировка на основе высоты требует дополнительных вычислений и проверок на каждую модифицирующую операцию.

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

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

Итак, красно-чёрное дерево — бинарное дерево поиска, у которого

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

Чёрная высота узла $x$ — количество чёрных узлов на пути от узла $x$ до фиктивного листа (любого). При этом сам узел $x$ мы не считаем.

\bh x \defeq \text{количество чёрных узлов на пути от}~ x ~\text{до фиктивного листа}

Чёрной высотой дерева называется чёрная высота его корня.

Лемма о чёрной высоте

Красно-чёрное дерево с $n$ внутренними узлами имеет высоту не более $2 \lfloor \log_2 n \rfloor + 2$

Поддерево любого узла $x$ содержит как минимум $2^{\bh x} - 1$ внутренних узлов. Это утверждение доказывается индукцией по высоте узла $x$ .

Обозначим высоту дерева за $h$ . Тогда, согласно требованию для красных узлов, по крайней мере половина узлов на пути от корня к листу, не считая сам корень, должны быть чёрными. Значит, чёрная высота дерева должна быть минимум $h/2$ . Тогда

n \ge 2^{h/2} - 1

Отсюда получаем, что

h \le 2 \lfloor \log_2 n \rfloor + 2

Хранение красно-чёрного дерева

Красно-чёрное дерево будет реализовано нами на указателях. При этом в каждом узле помимо ссылок на левого и правого ребёнка будем хранить ссылку на родителя. Это нужно для реализации поворотов без использования стека.

Color = 'red' | 'black'

struct node:
    literal[Color] color
    node* left
    node* right
    node* parent

    object key

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

Повороты красно-чёрного дерева

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

Повороты здесь схожи с поворотами AVL деревьев.

function left_rotate(node x):
    node pivot = x.right  # устанавливаем pivot

    # перенос родителя x в pivot
    pivot.parent = x.parent
    if x.parent is not none:
        if x.parent.left == x:
            x.parent.left = pivot
        else:
            x.parent.right = pivot

    # левое поддерево pivot становится правым поддеревом x
    x.right = pivot.left
    if pivot.left is not none:
        pivot.left.parent = x

    # x становится левым дочерним узлом pivot
    pivot.left = x
    x.parent = pivot

function right_rotate(node x):
    node pivot = x.left  # устанавливаем pivot

    # перенос родителя x в pivot
    pivot.parent = x.parent
    if x.parent is not none:
        if x.parent.left == x:
            x.parent.left = pivot
        else:
            x.parent.right = pivot

    # правое поддерево pivot становится левым поддеревом x
    x.left = pivot.right
    if pivot.right is not none:
        pivot.right.parent = x

    # x становится правым дочерним узлом pivot
    pivot.right = x
    x.parent = pivot

Вставка

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

При вставке нового узла он встаёт на место одного из фиктивных листьев. Поэтому мы окрасим его в красный цвет и прикрепим к нему два фиктивных листа. Дальше действия зависят от цветов родственных узлов.

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

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

Перекрашивание дерева, когда дядя вставляемого узла красный

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

Перекрашивание дерева, когда дядя вставляемого узла чёрный

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

function fix_insertion(node x):
    if x.parent is none:  # если x является корнем, то просто красим его в чёрный
        x.color = 'black'
        return

    while x.parent.color is 'red':
        grandfather = x.parent.parent

        # родитель - левый ребенок деда
        if x.parent == grandfather.left:
            uncle = grandfather.right
            if uncle.color is 'red':
                x.parent.color = 'black'
                uncle.color = 'black'
                grandfather.color = 'red'
                x = grandfather
            else:
                if x == x.parent.right:
                    x = x.parent
                    left_rotate(x)
                x.parent.color = 'black'
                grandfather.color = 'red'
                right_rotate(grandfather)

        # родитель - правый ребенок деда
        else:
            uncle = grandfather.left
            if uncle.color is 'red':
                x.parent.color = 'black'
                uncle.color = 'black'
                grandfather.color = 'red'
                x = grandfather
            else:
                if x == x.parent.left:
                    x = x.parent
                    right_rotate(x)
                x.parent.color = 'black'
                grandfather.color = 'red'
                left_rotate(grandfather)

    root.color = 'black'

И теперь мы можем написать полный код вставки. При вставке мы спускаемся вниз, пока не дойдём до фиктивного листа. Далее заменяем этот фиктивный лист на новую вершину, добавляем её два фиктивных листа, красим её в красный и выполняем процедуру fix_insertion() для восстановления свойств красно-чёрного дерева.

function insert(node* root, object key)
    node x = new node(key, color='red', left=none, right=none)

    if root is none:  # дерево пустое
        root = x
        x.parent = none

    else
        Node p = root
        Node q = nil
        while p is not none:  # спускаемся вниз, пока не дойдем до подходящего листа
            q = p
            if p.key < x.key
                p = p.right
            else
                p = p.left

        x.parent = q

        # добавляем новый узел x
        if q.key < x.key
            q.right = x
        else
            q.left = x

     fix_insertion(x)