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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.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 поворота для ребалансировки дерева.

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

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

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