Корень красно черного дерева

Понимаем красно-черное дерево. Часть 1. Введение

Довольно долгое время я воевал с красно-черным деревом (далее — кчд). Вся информация, которую я находил, была в духе «листья и корень дерева всегда черные, ПОТОМУ ЧТО», «топ 5 свойств красно-черного дерева» или «3 случая при балансировке и 12 случаев при удалении ноды». Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют «черной высотой»?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево, с которого мы и начнем.

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

1. В этой статье не будет информации про плюсы и минусы дерева, его применение и т.д.: информации об асимптотике дерева и работе с ним в интернете полно.
2. Материал предназначен для тех, кто уже знаком с кчд и теперь хочет их понять, а также для тех, кто только знакомится с ними.
3. Статья не будет содержать деталей реализации структуры.
4. Можно считать что эта статья — перевод английского видео материала в упрощенный русский текстовый вариант. Все ссылки я оставляю в конце статьи.

Два-три дерево

Чтобы понять красно-черное дерево, нужно понять два-три дерево

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

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

1. Добавляя элемент, мы всегда спускаемся вниз по дереву.
2. Дерево отсортировано классически — меньшие значения находятся слева, бОльшие — справа.
3. Два-три дерево — отсортированное, сбалансированное дерево.

Итак, начнем с первой ноды, это число 5. Тут все просто — 5 становится корнем.

Добавим число 12. Число 12 мы так же добавляем в корень (помним, что нода может иметь два значения), но теперь нам нужно «отсортировать» нашу ноду (сортировать два элемента, ха), т.е. уложить их в порядке возрастания. В итоге получается нода 5-12.

Добавим следующее число. Пусть это будет 17. Давайте пока добавим наш элемент в единственную ноду и снова отсортируем ее. Получилась нода 5-12-17.

Внимательный читатель заметит тут подвох — выше я говорил о том, что наши ноды могут содержать не более двух элементов. Вот тут и происходит магия! Мы берем средний элемент нашей ноды и «просачиваем» его наверх. Итог виден на картинке. Корнем стало число 12, левым сыном число 5, правым — 17.

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

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

Второй и третий случай балансировки будут рассмотрены ниже.

Окей, идем дальше. Давайте добавим число 3. Так как теперь мы не ограничиваемся одной нодой, спускаемся вниз. Понятно, что спуститься надо влево и добавить 3 к ноде со значением 5. Не забываем расставить 3 и 5 в нужном порядке. В итоге получилась нода 3-5.

Потерпите, мы близимся к самому интересному:)

Давайте добавим число 4 которое также пойдет влево и присоединится к ноде 3-5. Получится нода 3-4-5, которую, как мы уже знаем, нужно привести к нужному виду. Что делаем? Балансируем наше дерево, т.е. «просачиваем» значение 4 наверх.

Теперь самое интересное. Помимо того, что мы добавим 4 к корню, мы так же добавим корню третьего потомка — это будет нода, которая была больше 4. В нашем случае это 5. Картина будет выглядеть так:

Почему 5 не могла остаться на месте в своей ноде? Тут мы вспоминаем правило отсортированного дерева: значения меньше — слева, значения больше — справа. И так как 5 больше 4, мы не можем оставить 5 слева, т.к. это нарушит наш инвариант. Поэтому ноде со значением 5 ничего не остается, как «переехать», и стать потомком ноды 4-12 (кстати, если бы у 5 были потомки, они так же «переехали» бы вместе с родителем).

Тут нужно сделать небольшую паузу и объяснить, как ориентироваться в нодах с тремя потомками. Все просто:

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

А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное два-три дерево. Значения меньше лежат слева, значения больше — справа (тут, как и в случае со значениями 4-5-12, мы считаем, что 5 лежит справа от 4 и слева от 12). Корень имеет два значения и три потомка, что абсолютно соответствует описанию дерева выше. Сейчас вы можете сами попробовать добавить любое значение, чтобы удостовериться, что вы поняли логику (что произойдет с деревом, если добавить значение 7? А затем 9?).

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

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

Красно-черное дерево

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

Чтобы добиться этого, нам нужно простое представление для 3-ноды. Давайте разделим 3-ноду на две 2-ноды и свяжем их ссылками. Пометим эти ссылки каким-нибудь свойством, например, цветом, (возьмём красный), чтобы отличать такие ссылки в дереве от всех остальных.

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

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

Свойства красно-черного дерева

Фактически мы разбираем не просто кчд, а левосторонне кчд — одна из имплементаций кчд, в которой красные ноды могут находится только слева, то есть от 3-ноды мы всегда отделям значение меньше (что и было сделано выше). По сути своей левостороннее кчд ничем не отличается от обычного, за исколючением того, что это более простая и понятная имплементация. Аналогично левостороннему кчд, существует и правостороннее кчд(логику его додумайте сами).

Две красные ноды не могут идти подряд. Это свойство приобретает смысл, если мы знаем, что красная нода — это по сути часть 3-ноды в 2-3 дереве. Ну а если две красные ноды идут подряд, то получается 4-нода, которой у нас не существует:)

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

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

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

Высота дерева измеряется только по черным нодам и называется «черной высотой». Тут опять все в целом становится очевидным: красная нода является только дополнением к ноде черной, является ее частью, поэтому высоту принято считать по черным нодам.

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

Источник

Красно-чёрное дерево (удалить)

Доказательство: Докажем по индукции. При [math]h=1[/math] получаем дерево, в котором чёрными являются только листья, а их больше одного. Иначе пусть корень — чёрный, тогда оба его поддерева имеют чёрную высоту h-1 и, следовательно, не менее, чем [math]2^[/math] элементов. Тогда всё дерево имеет более [math]2^[/math] элементов. В случае, если корень красный, то оба его поддерева имеют чёрные корни и чёрную высоту [math]h[/math] , то есть, как только что было показано, не менее [math]2^[/math] элементов. Таким образом, дерево будет иметь более [math]2^[/math] элементов.

Доказательство: Возьмём самый длинный путь в дереве. Всего в нём [math]h+1[/math] узлов. По крайней мере половина узлов чёрные, поскольку двух подряд идущих красных узлов быть не может, а лист чёрный. Поэтому чёрная высота дерева не меньше [math](h-1)/2[/math] , и, по первому утверждению, [math]2^[/math] элементов.

Отсюда также получаем, что высота дерева не более [math]2log_2 N+1[/math] , где N — число элементов дерева, т.е. [math]O(log N)[/math]

Операции

• Вставка элемента. Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil(т.е. этот сын — лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента красный, то достаточно рассмотреть только два случая:

1. «Дядя» этого узла тоже красный. Тогда просто перекрашиваем «отца» и «дядю» в чёрный цвет, а «деда» — в красный. Проверяем, не нарушает ли он теперь балансировку. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет.

2. «Дядя» чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком.

• Удаление вершины.При удалении вершины могут возникнуть три случая в зависимости от количества её детей:

1. Если у вершины нет детей, то изменяем указатель на неё у родителя на nil.
2. Если у неё только один ребёнок, то делаем у родителя ссылку на него вместо этой вершины.
3. Если же имеются оба ребёнка, то находим вершину со следующим значением ключа. У такой вершины нет левого ребёнка. Удаляем уже эту вершину описанным во втором пункте способом, скопировав её ключ в изначальную вершину.

Проверим балансировку дерева. Т.к. при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.

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

2. Если брат текущей вершины был чёрным, то получаем три случая:

• Если у брата правый ребёнок чёрный,а левый красный, то перекрашиваем брата и его левого сына и делаем вращение.

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

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

• Объединение красно-чёрных деревьев. Объединение двух красно-чёрных деревьев [math]T_[/math] и [math]T_[/math] по элементу x выполняется, когда [math]key[T_] \leqslant x[/math] и [math]x \leqslant key[T_][/math] .

Найдём чёрные высоты деревьев. Предположим также, что [math]bh[T_] \geqslant bh[T_][/math] . Тогда в дереве [math]T_[/math] ищем среди чёрных вершин, имеющих чёрную высоту [math]bh[T_][/math] , вершину y с наибольшим ключом. Пусть [math]T_[/math] — поддерево с корнем y. Объединяем это дерево с [math]T_[/math] в одно с красным корнем x. Теперь родителем вершины x становится бывший отец вершины y. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.

Т.к. общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за [math]O(\log)[/math] .

Источник