Базовые структуры данных. Сбалансированные деревья, страница 2

·  y – черная, а x приходится правым ребенком своему родителю. В этом случае выполняется левое вращение. Так как x и родитель x красные, то черная высота не изменяется. После этого в качестве вершины x будет выступать бывший родитель x. Мы пришли к третьему варианту.

·  y – черная, а x приходится левым ребенком своему родителю. Здесь достаточно провести правое вращение родительской вершины родителя x, а затем перекрасить ее в красный цвет, а бывшего родителя x – в черный. Теперь родитель x черный, поэтому цикл больше не повторяется.

Высота красно-черного дерева составляет O(log n), если в дереве n вершин, поэтому добавление нового элемента в дерево займет O(log n) времени. Цикл повторяется, только если мы встречаем случай 1; при этом x сдвигается вверх по дереву. Таким образом, максимальное количество повторений цикла есть O(log n). Значит, общее время работы алгоритма есть O(log n). Обратите внимание, что при этом выполняется не более двух вращений (после которых происходит выход из цикла).

Удаление элемента

Как и другие операции, операция удаления элемента из дерева занимает время O(log n). Чтобы упростить обработку граничных условий, введем понятие фиктивного элемента (sentinel). Для красно-черного дерева фиктивный элемент имеет те же поля, что и обычная вершина дерева, причем он имеет черный цвет, а остальные поля могут иметь любые значения. Пусть все нулевые указатели заменены указателями на фиктивный элемент. Благодаря этим элементам мы можем считать пустой лист, являющийся ребенком вершины x, обычной вершиной, родителем которой является x. Мы используем одну фиктивную вершину для описания всех пустых листьев вместо резервирования памяти для каждого из них; обратите внимание, что перед использованием такой вершины необходимо проинициализировать указатель на ее родителя указателем на x.

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

Рассмотрим процедуру восстановления RB-свойств красно-черного дерева. Если удаленная вершина y была черной, то любой путь, проходящий через нее, содержит теперь на одну черную вершину меньше. Мы можем компенсировать это за счет вершины x, занявшей место удаленной. Если она красная, сделаем ее черной. Если же x – черная, объявим ее дважды черной и будем учитывать дважды при подсчете числа черных вершин на пути от корня к листьям. Конечно же, это лишь временный выход, так как концепция красно-черных деревьев не предусматривает дважды черных вершин. Поэтому нам необходимо избавиться от нее.

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

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