Свойства красно-черных деревьев
Красно-черное дерево (red-black tree) — это двоичное дерево поиска, вершины которого разделены на красные (red) и черные (black). Таким образом каждая вершина хранит один дополнительный бит — её цвет.
При этом выполняются определённые требования, которые гарантируют, что глубины любых двух листьев отличаются не более чем в два раза.
Каждая вершина красно-черного дерева имеет поля color (цвет), key (ключ), left (левый ребенок), right (правый ребенок) и p (родитель). Если у вершины отсутствует ребенок или родитель, то соответствующее поле содержит NIL.
Двоичное дерево поиска называется красно-черным, если оно обладает следующими свойствами:
Каждая вершина — либо черная, либо красная
Каждый лист (NIL) — чёрный
Если вершина красная, оба её ребенка чёрные
Все пути, идущие вниз от корня к листьям, содержат одинаковое количество чёрных вершин
Рассмотрим произвольную вершину x красно-черного дерева и пути, ведущие вниз от неё к листьям. Все они содержат одно и то же число чёрных вершин. Число чёрных вершин в любом из них (саму вершину x не считаем) будем называть чёрной высотой (black-height) вершины x. Чёрной высотой дерева будем считать чёрную высоту его корня.
Вращения
Вращения представляют собой локальную операцию (меняются несколько указателей) и сохраняет свойство упорядоченности.
ЛЕВОЕ ВРАЩЕНИЕ возможно в любой вершине x, правый ребёнок которой (назовем его y) не является листом (NIL). После вращения y оказывается сверху, x становится левым ребёнком y, а бывший левый ребёнок y — правым ребенком x.
ПРАВОЕ ВРЕЩЕНИЕ возможно в любой вершине x, левый ребёнок которой (назовем его y) не является листом (NIL). После вращения y оказывается сверху, x становится правым ребёнком y, а бывший правый ребёнок y — левым ребенком x.
Поиск вершины
Процедура поиска выполняется следующим образом: в текущей вершине сравниваем ключи искомой вершины с ключом этой вершины. Если ключи совпадают — значит нашли вершину, иначе если ключ в этой вершине больше искомого, то идем к левому ребенку, иначе — к правому. Процедура заканчивается при нахождении вершины или если мы находимся в листе (NIL).
Добавление вершины
Добавление вершины в красно-черное дерево производится за время O(log n). Сначала спустимся вниз по дереву, так как это происходит при поиске, пока мы не окажемся в вершине не имеющий сына. Добавим вершину x с той стороны, куда мы должны были бы двинуться, если бы вершина имела детей. Красим новую вершину в красный цвет. После этого надо восстановить свойства красно-черного дерева, для чего приходится перекрасить некоторые вершины и произвести вращения.
После добавления вершины выполняются все свойства красно-черного дерева, кроме одного: красная вершина x может иметь красного родителя, и это нарушение единственно. Восстанавливается это свойство очень просто: пока вершина x не корень дерева и имеет красного родителя выполняем следующие действия:
· если дядя вершины x красного цвета, то красим его и отца вершины x в черный цвет, а дедушку вершины x в красный цвет. Далее вершиной x становится дедушка.
· если дядя вершины х черного цвета, то проверяем являются ли вершина x и его отец одинаковыми детьми (т. е. оба ЛЕВЫЕ или ПРАВЫЕ дети). Если не являются одинаковыми детьми, то делаем соответствующие вращение (становятся одинаковыми детьми). Красим отца в черный цвет. Далее делаем соответствующее вращение;
Будем полагать, что во всех красно-черных деревьях корень черный и поддерживать это свойство.
Удаление вершины
Как и другие операции, удаление вершины из красно-чёрного дерева требует времени O(log n). Удаление вершины несколько сложнее добавления.
Для начала находим вершину z в дереве, которую требуется удалить. Возможны три случая:
· если у вершины z нет детей, для удаления z достаточно поместить NIL в соответствующее поле его родителя (вместо z).
· если у z один ребенок, то можно вырезать z, соединив его родителя напрямую с его ребенком.
· если у z двое детей, то мы находим следующий (в смысле порядка на ключах) за z элемент y; у него нет левого ребенка. Теперь можно скопировать ключ и дополнительные данные из вершины y в вершину z, а саму вершину y удалить выше описанным способом.
Если была удалена черная вершина, то надо восстановить свойства красно-черного дерева (при удалении красной вершины свойства дерева не нарушаются). Пусть вершина x — ребенок удаленной вершины. Пока вершина x не корень дерева и она чёрная вершина выполняем следующие действия:
· если у вершины x брат красного цвета, то делаем ВРАЩЕНИЕ (брат становится родителем отца), при этом брата красим в черный, а отца в красный.
· если у вершины x брат чёрного цвета, то
· если у брата оба ребенка черные, то красим брата в красный цвет. Теперь вершиной x будет его отец.
· если у брата его "одинаковый" ребёнок черного цвета, то красим брата в красный цвет и делаем вращение.
· иначе красим брата в цвет отца, отца красим в черный цвет. Делаем вращение и выходим из цикла.
При восстановлении свойств красно-черного дерева будет выполнено не более трех вращений.