Удаление в красно-черном дереве

Тема не так нова, но почему-то все имеющиеся статьи либо с ошибками, либо сложны для понимания (например, фразами «ребенок удаленной вершины без детей»), либо кривыми иллюстрациями, поэтому для себя я решил заново полностью понять всю схему, а заодно и оформить это все в более-менее рабочий пост-заметку с пояснениями.

Важно: данная статья только удаления узлов в дереве, и то достаточно поверхностно. В ней рассматриваются конкретные возможные случаи, и не рассматривается связь с 2-3 деревом (смиренно ждем продолжение от @imicah). То есть я попытаюсь достигнуть понимание частных случаев, вместо общей идеи.

Напоминание о структуре красно-черного дерева

Красно-черное дерево (в его конечной реализации) — это прежде всего Бинарное Дерево Поиска (BST), а значит основные правила «меньшее — влево, большее — вправо» (конечно, можно использовать и произвольный компаратор) так же соблюдаются.

Во-вторых, это самобалансирующихся дерево, наподобии AVL, однако балансировка происходит не после каждого добавления и удаления, а только при необходимости.

Критерии этой «необходимости» следуют из правил построения красно-черного дерева. Напомним их:

  • Вершины окрашиваются в два цвета — Красный и Черный.

  • Корень и листья (NULL-вершины) дерева всегда черные.

  • Две красные вершины не могут идти подряд.

  • Во всем дереве поддерживается одинаковая Черная высота.

Таким образом, мы получили набор базовых правил, к которым будем возвращаться раз за разом.

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

Итак, ситуация: нам нужно удалить конкретную вершину из дерева. Сложность в том, чтобы соблюдать правила построения дерева, иначе красно-черное дерево перестанет быть таковым. То есть тот самый критерий «необходимости» балансировки — нарушение правил красно-черного дерева при добавлении или удалении вершин.

Рассмотрим для начала простейшие случаи с удалением Красной вершины, дополнительно разделим их на случаи с количеством детей (NULL-вершины не в счёт!):

1) Удаление красной вершины с 0 детьми

Для удобства удаляемую (или уже удаленную, понадобится в дальнейшем) вершину будем обозначать с крестом на ней.

NULL-вершины здесь и далее -- маленькие черные вершины
NULL-вершины здесь и далее — маленькие черные вершины

В этом случае мы просто заменяем данную вершину на NULL-вершину. Никакие пункты из вышеописанных правил не нарушены (та же черная высота не нарушается), дерево все еще корректно.

Кстати, может ли родительская вершина быть красной?

Очевидно, нет, иначе у нас было бы две красные вершины подряд и дерево было бы некоректно. Однако подобными вопросами, «а реален ли данный случай в корректном дереве?», мы будем задаваться все чаще.

2) Удаление красной вершины с 1 ребенком

Возможно кто-то уже из заголовка подпункта понял подвох, но если все же уточнять — данный случай невозможен. Но мы еще рассмотрим, почему:

Родитель удаляемой вершины тут только для наглядности (красная вершина не может быть корнем)
Родитель удаляемой вершины тут только для наглядности (красная вершина не может быть корнем)

Логично, что ребенок Красной вершины может быть только Черным. Но если такая вершина является единственным ребенком, то у нас происходит нарушение черной высоты — на изображении подсчитана черная высота левого и правого поддерева (слева и справа от удаляемой вершины соответственно; для красоты значение указано с учетом NULL вершин).

Таким образом, еще перед удалением как таковым, у нас имеется некорректное дерево. Если балансировка при добавлении у нас написана верно, то такой случай невозможен.

3) Удаление красной или черной вершины с 2 детьми

Да, тут мы уже рассматриваем не только Красные вершины, но и Черные. Все из-за метода, который здесь можно применить:

Так как у вершины есть два ребенка (а то и поддерева), чтобы сделать наиболее безболезненное удаление, стоит найти кого поставить в качестве замены на это же место. Эту замену мы можем найти в этих самых поддеревьях: из левого мы можем искать максимальное, а из правого — минимальное:

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

Чтобы найти максимальный элемент в поддереве, из-за свойств бинарного дерева нам достаточно просто постоянно спускаться по правой ветви. То же и для минимального — спускаться до конца по левой ветви.

Также стоит сделать оговорку: «минимальный/максимальный» в данном контексте — это скорее «самый левый, правый», так как никто нам не запрещает использовать другой компаратор («большие — влево, меньшие — право»)

Имея на руках двух кандидатов, нам нужно выбрать из них. Есть несколько вариантов:

  • Ориентироваться на цвет (красные удалять мы уже умеем, и, как мы узнаем далее, они проще)

  • Ориентироваться на «дальность» — на какой глубине относительно удаляемой вершины находится кандидат.

  • Ориентироваться на модуль, то есть брать ближайшую по значению вершину.

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

Наиболее оптимальный вариант из приведенных зависит от реализации, хочется ли быстрое удаление (предпочтение «красных» кандидатов), или равномерное дерево (выбирать самых дальних, чтобы не было длинных красно-черных ветвей), или что-то иное.

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

Таким образом, нам останется удалить вершину, с которой мы произвели замену, а у нее уже точно один или ноль детей (иначе , то есть мы перешли к более простому варианту:

4) Удаление черной вершины с 1 ребенком

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

Итак, рассмотрим, как выглядит подобный вариант:

То есть опять же, мы можем поменять значения (не цвета!) и начать удалять вершину с одним или нулем детей. Черная высота (по крайней мере в пределах этой замены) остается той же.

5) Удаление черной вершины с 0 детей

А вот и буря. Сразу спойлер: самый сложный случай (на самом деле только в сравнении с предыдущими, сейчас мы его раскидаем по полочкам).

Здесь и далее вершины с любым цветом обозначаются как белые со знаком вопроса.
Здесь и далее вершины с любым цветом обозначаются как белые со знаком вопроса.

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

Так что мы удаляем вершину, заменяя ссылку на него на NULL, и производим ребалансировку.

Ребалансировка дерева при удалении черной вершины с 0 детьми

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

Теперь мы будем рассматривать структуру не как «удаляемая вершина-дети», а как «родитель — брат — дети брата». В зависимости от их цветов (нам же надо черную высоту выровнять) мы будем производить те или иные операции.

Warning: начиная с этого момента рассматривается случай с левой удаляемой вершиной. Очевидно, если вершина была правым ребенком, все случаи просто отзеркаливаются (в реализации можно использовать схему «вершина с той же ветки (левой/правой)» и «вершина с другой ветки«):

Отец, брат (sibling -- брат/сестра), дети брата. Удаленная вершина все так же помечена крестом.
Отец, брат (sibling — брат/сестра), дети брата. Удаленная вершина все так же помечена крестом.

А еще впредь мы не особо будем утруждаться вырисовывать все NULL вершины отдельно (с некоторыми исключениями в виде рассмотрения частных случаев). Надо будет помнить, что черные вершины могут быть как NULL вершины, так и вершинами со значениями!

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

1) Брат черный

1.1) Хотя бы один ребенок брата красный

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

Однако, мы так же разделим этот случай на два в зависимости от положения красного ребенка:

1.1.а) Правый ребенок красный (левый — любой)

Путь к решению

Цель в том, чтобы увеличить черную высоту левого поддерева, при этом не особо трогая корень. Для этого мы можем перекрасить родителя в черный, а брата в цвет родителя, и сделать поворот. Казалось бы, победа.

Однако, теперь в правой части у нас нет черной вершины (и черная высота уменьшилась). Впрочем, мы можем просто перекрасить того самого правого красного ребенка в черный. Так мы получаем выровненную черную высоту!

А действительно ли вторая вершина любого цвета?

На самом деле, если помнить, что удаляемая вершина не имела детей, то для одинаковой черной высоты она должна быть тоже красной или NULL (да, она тоже черная, но без значения).

Однако, не забываем о предстоящей рекурсии. Может получиться так, что и красный правый ребенок — корень целого поддерева, и следовательно вершина второго ребенка может быть в том числе черной со значением.

Но в общем случае, сам окрас данной вершины влияет только на абсолютное значение черной высоты, но не на изменение на ±1 после удаления и поворота, так что мы можем смело говорить о «любом цвете вершины».

Мы перекрашиваем брата в родительский цвет, а его отца и красного ребенка — в черный (цвет второго ребенка остается тем же). Далее требуется только сделать поворот влево:

У знаков вопроса теперь появились цифры!
В данном случае они подчеркивают, что цвет на данной позиции остается тот же.
У знаков вопроса теперь появились цифры!
В данном случае они подчеркивают, что цвет на данной позиции остается тот же.

Черная высота точно выравнена, дальнейшая ребалансировка не требуется.

Насчет поворотов

Подобные повороты использовались при вставке, так что рандомному читателю плюс-минус будет о них известно. Поворот выше можно обозначить как «поворот вокруг α влево«.

Однако, я хотел бы заметить, что поворот как таковой не меняет цвет родителя α и ребенка β, и уж тем более внуков. Мы их меняем впоследствии самостоятельно при необходимости. То есть опять же, происходит перекидывания указателей, но цвета остаются те же.

1.1.б) Левый ребенок красный (правый — черный)

Мы обмениваем цвета красного ребенка и брата, и делаем поворот вправо вокруг брата:

По изображению видно, что этого недостаточно, НО зато мы перешли к уже известному случаю — брат стал черным, с правым красным ребенком. То есть переход к пункту 1.1.а).

Снова про цвета и рассчет черной высоты

Опять же вопрос в том, а возможен ли этот случай и не нарушена ли у нас черная высота в этом правом поддереве? Как бы ни казалось иначе, на самом деле нет!

Рассмотрим случаи:

  • Если мы в первый раз запускаем ребалансировку, то высота левого (а значит и нашего правого) поддерева — 2 (с учетом NULL вершины). Значит, так как вершина «c» — красная, вершина «d» должны быть черной NULL-вершиной:

До и после поворота.
До и после поворота.
  • Если мы рассматриваем общий случай, то пусть поддерево с «d» в качестве вершины имеет черную высоту «h», тогда и поддерево с «c» так же изначально должно быть с такой же черной высотой «h», и при повороте происходит следующее:

До и после поворота.
До и после поворота.

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

В общем-то, именно поэтому повороты так спокойно используют при добавлении вершин.

1.2) Оба ребенка брата — черные

В данном случае у нас не остается красных вершин для манипуляций, так что мы.. сделаем брата красным?

Обозначение удаляемой вершины сместилось на родительскую вершину... Почему -- читайте ниже.
Обозначение удаляемой вершины сместилось на родительскую вершину… Почему — читайте ниже.

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

  • Если родительская вершина была красной, то мы заканчиваем алгоритм (черная высота выравнена засчет родительской вершины);

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

Таким образом, мы наконец получаем ту самую рекурсивность удаления.

2) Брат красный

Но это еще не всё. У нас остались случаи с красным братом — это было сделано потому, что этот случай сводится, опять же, к предыдущим. Но благо, что под конец это достаточно удобный и простой случай.

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

Простой — потому что достаточно перекрашивания вершин (родитель в красный, брат в черный) и одного поворота так, чтобы брат стал корнем данного поддерева:

Так мы переместили разность черных высот с корневой вершины данного поддерева на уровень ниже (мы ведь действительно просто переместили корень вниз…). То есть далее нам требуется разрешить конфликт черных высот в области «удаленной» вершины и вершины «c».

Пояснение к «смещению конфликта черных высот»

Да, это все звучит страшно и странно, но на деле все достаточно логично. Возможно, следующая картинка с пояснением высот сработает:

Пусть у вершин «c», «d» и «удаляемой» изначально была некоторая черная высота «h». Тогда после удаления вершины, в той ветви черная высота будет «h-1».

Можно заметить, что несовпадение черных высот левого и правого поддерева до поворота находится у корневой вершины «α». После поворота же эта разница остается у этой же вершины (и действительно, почему вдруг изменится черная высота вершины «c» и «удаляемой» вершины — следовательно несовпадение остается), однако сама она уже смещена вниз.

Для окончательной ребалансировки мы переходим к пункту 1) черный брат.

Окончание рекурсии

Тут все просто:

Так мы будем делать вызовы, пока вершина черная и не корневая. Теоретически, нам потребуется максимум 3 поворота для ребалансировки дерева.

Вместо заключения

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

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

Читайте так же: