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

Использовано изображение портала cartoonbank.ru

В прошлой статье мы рассмотрели правила формирования красно-чёрного дерева поиска и рассмотрели случаи балансировки при добавлении элементов.

Теперь поговорим об удалении элементов.

Возьмём, для примера, вот такое красно-чёрное дерево:



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

Разделяй и властвуй

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

Сначала разделим задачу по двум категориям:

• цвет удаляемого узла: К или Ч
• количество дочерних узлов: 2, 1 или 0

В результате у нас получится матрица из 6 вариантов: К2, Ч2, К1, Ч1, К0, Ч0.
Для каждого варианта указан соответствующий узел нашего дерева.
Рассмотрим процесс удаления для каждого варианта.

К2 — красный узел с двумя детьми

Задача удаления узла с двумя дочерними элементами сводится к задаче удаления узла с одним или нулём дочерних элементов.

Для этого необходимо найти ближайший элемент, который меньше или больше удаляемого и поменять их местами.



Обратите внимание, что при обмене элементов местами нужно изменять только значения в узлах, а цвет оставлять прежним, чтобы не нарушать структуру дерева и не изменять чёрную высоту.
После обмена нужно удалить элемент из его нового места. Это будет либо самый правый элемент в левой ветке (максимальный слева), либо самый левый в правой (минимальный справа), в любом случае у него не будет одного ребёнка слева или справа. Таким образом, задача удаления узла с 2 детьми сводится к задаче удаления элемента с 1 или 0 детьми:

• К2 => K1 или K0

Ч2 — чёрный узел с двумя детьми

Аналогично предыдущему случаю, приведём пример удаления чёрного узла 16.



Как видим, после обмена задача сводится к удалению элемента с одним ребёнком:

• Ч2 => Ч1 или Ч0

К1 — красный узел с одним ребёнком

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

Таким образом, К1 случай не имеет места быть.

Ч1 — чёрный узел с одним ребёнком

Если у чёрного элемента нет одного ребёнка, значит, вместо него находится чёрный NIL-элемент с чёрной высотой 1. Следовательно, с другой стороны должен быть красный узел без детей. Для удаления такого элемента достаточно перенести значение красного элемента в чёрный узел, чёрная высота при этом сохранится.

К0 — красный узел без детей

Самый простой случай. Мы просто удаляем элемент, заменяя его ссылкой на NIL:



Удаление красного элемента не изменяет чёрную высоту.

Ч0 — чёрный узел без детей

Удалить чёрный узел без детей тоже очень просто: заменяем его ссылкой на NIL.

Думаете, это уже почти всё? Ха-ха, шесть раз.



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

Удалённый элемент на рисунках обозначается х, его высота – h. Когда мы только начинаем балансировку, то h = 1, но при рекурсивных вызовах она может увеличиться.

Для определённости установим, что удалённый элемент был правым сыном. После удаления его высота уменьшилась и стала h. Значит, высота левого сына осталась h+1. Нам необходимо выровнять высоту левого и правого поддерева и сделать их равными h+1.

Предлагаю снова разделить задачу на несколько частей. Какие у нас могут быть варианты?
Родитель может быть красным или чёрным. Левый сын также может быть чёрным или красным. А правый сын всегда чёрный — именно оттуда мы пришли к балансировке после удаления.

Всего нужно рассмотреть 6 разных случаев:

• КЧ1 и КЧ2 – родитель красный, левый ребёнок чёрный.
• ЧК3 и ЧК4 – родитель чёрный, левый ребёнок красный.
• ЧЧ5 и ЧЧ6 – родитель чёрный, левый ребёнок чёрный.

Запасемся терпением и попкорном, впереди самое интересное и загадочное.

КЧ1 — родитель красный, левый ребёнок чёрный с чёрными внуками

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



Обязательно перепроверьте по рисунку, что чёрная высота узлов a и b сохранилась, а высота всего поддерева стала одинаковой и равной h+1.

КЧ2 — родитель красный, левый ребёнок чёрный с левым красным внуком.

В этом случае одного перекрашивания недостаточно. Нам нужно выполнить малый поворот направо между узлами 3-7. В результате мы сможем увеличить высоту правого поддерева до h+1:



Зелёный цвет узла означает, что он может быть, как чёрным, так и красным.
Примечание. Если узел “1” будет чёрным, а “с” красным, то задача может быть сведена к варианту ЧЧ5.

ЧК3 — родитель чёрный, левый сын красный, у правого внука чёрные правнуки

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



Обратите внимание, что красный узел 5 не увеличивает чёрную высоту.

ЧК4 — родитель чёрный, левый сын красный, у правого внука левый правнук красный

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



В этом случае нужно выполнить большой поворот налево, который состоит из двух малых поворотов 5-3 и 5-7. Узел b поменял свой цвет с красного на чёрный и таким образом увеличил свою высоту на 1. Убедитесь, что чёрная высота стабилизировалась.

ЧЧ5 — родитель чёрный, левый сын чёрный с правым красным внуком.

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



Проверьте, что чёрная высота поддерева стабилизировалась.

ЧЧ6 — родитель чёрный, левый сын чёрный, его внуки тоже чёрные

И вот настал момент, когда красные дрова закончились. Делать нечего, придётся чёрный узел покрасить в красный и таким образом выровнять чёрную высоту узла 7, но не за счёт увеличения чёрной высоты правого поддерева, а за счёт уменьшения чёрной высоты левого поддерева. В результате чёрная высота всей нашей структуры уменьшится на 1 и мы должны рекурсивно воззвать балансировку к праотцам.

Пример удаления с балансировкой и рекурсией

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

Первый шаг — просто удаляем узел 30.

Второй шаг — запускаем балансировку на его родителя — узел 25.

Имеет место случай ЧЧ6:



С горем пополам стабилизировали высоту узла 25.

Третий шаг — балансировка на дедушкином уровне — для узла 20.

Чтобы было веселее и нагляднее, нарисуем всё дерево до и после балансировки. Имеет место случай ЧК4:



Обратите внимание, как изменилось красно-чёрное дерево после балансировки, часть элементов из левого поддерева перешла в правое, высота стабилизировалась, элемент удалён, все счастливы!

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

Читать ещё

• Балансировка красно-чёрных деревьев — Три случая