Красно черные деревья хабр

Понимаем красно-черное дерево. Часть 2. Балансировка и вставка

Это вторая часть из серии статей «Понимаем красно-черное дерево». Если вы пропустили первую часть, настоятельно рекомендую ознакомиться с ней здесь. Там мы разобрали причину появления кчд и расставили по полочкам некоторые его свойства.

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

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

1. Все вставленные ноды, кроме корня дерева, вставляются с красным цветом. Объясняется это тем, что мы всегда сначала добавляем значение к уже существующей ноде и только после этого занимаемся балансировкой (вспомните ситуацию с получавшимися 4-нодами).
2. В первой части мы выяснили, что разбираем левостороннее красно-черное дерево, из этого следует, что красные ноды могут лежать только слева (обратный случай требует балансировки).

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

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

Если повороты будут для вас не понятны из этой статьи, то информации о них полно в интернете. Я же хочу показать, как ими пользоваться.

Левосторонний поворот(левый малый поворот)

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

В первую очередь мы видим, что parentNode (здесь parentNode — это x, childNode — y) не только меняется местом с childNode, но и цветом. Но! Важно уточнить, что, если childNode принимает цвет своего родителя, то цвет parentNode всегда определяется как красный, независимо от предыдущего цвета потомка (левосторонний поворот просходит только тогда, когда цвет childNode — красный, поэтому нам легче сказать, что parentColor = RED, нежели свапать значения). Также обратите внимание на «переезд» левых потомков childNode (да, вам понадобится tempNode). Тут все так же логично, и это не нарушает баланс. Те потомки, что меньше childNode, больше parentNode, и childNode, соответственно, имеют такое же отношение (меньше/больше) к parentNode, как parentNode к своему родителю.

Правосторонний поворот(малый правый поворот)

Тот же поворот, но в другую сторону. Логика аналогична левостороннему.

Свап цвета

Свап цвета применяется тогда, когда у parentNode два красных потомка. Потомки становятся черными, а parentNode — красным. Операция легкая, обсуждать тут нечего.

Важно сказать, что все три операции изменяют дерево только локально (свап цвета изменяет ноду на уровень выше, но мы считаем это локальным изменением), и вызываем мы их на уровне parentNode! Мы не теряем сбалансированность на других этажах (если она была). В этом вы можете убедиться самостоятельно.

Построение красно-черного дерева.

Итак, начнем построение нашего дерева.

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

Следующая нода, которую мы вставим, имеет значение 5. По правилу бинарного дерева, нода опускается влево и по правилу кчд становится красной нодой.

Нода со значением 1 становится потомком ноды 5. Здесь мы видим две идущие подряд красные ноды. В таком случае, нам нужно совершить нашу первую балансировку!

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

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

Итак, в нашем арсенале 3 операции: правостороний поворот, левостороений поворот, свап цветов.

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

Давайте пока просто попробуем подставить наши операции. Свап цвета нам не подходит — для свапа нужно два потомка с красным цветом. Левостороний поворот не имеет смысла, так как красных нод справа нет. Остается один вариант — правосторонний поворот в ноде 24. Итог вы видите на картинке.

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

В итоге у нас снова корректное левостороннее кчд (и даже без красных нод)! А вот как это выглядело бы в 2-3 дереве.

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

Двигаемся дальше. Вставляем значение 15. Нода уходит в левого потомка ноды 24. Здесь балансировка не нужна.

Вставляем 3. Нода будет меньше корня, но уже больше 1, поэтому нода становится правым потомком ноды-1.

Как мы видим, красная нода находится справа. И снова балансировка. В прошлый раз нас спасла комбинация правосторонний поворот + свап цвета. В этот раз поворот в право нас не спасет (как и свап цвета, я думаю, это очевидно). Сделаем поворот влево и посмотрим, что получится.

Вуаля! Наше дерево снова корректно.

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

Последнее наше значение — 8. Куда оно встанет, догадайтесь сами. Результат мы видим на картинке. Такая ситуация нам уже встречалась, и мы знаем, что делать.

Правосторонний поворот + свап цвета дает нам следующий результат.

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

Ожидаемый итог — снова корректное левостороннее красно-черное дерево.

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

Вот в целом и все. За исключением пары моментов, построение дерева будет выглядеть примерно так. Как и в случае 2-3 дерева попробуйте сейчас сами добавить пару значений в дерево (ноды 13 и 16, например, интересный случай).

Как я уже говорил выше — операция балансировки это дело локальное, поэтому мы не думаем и не должны думать о том, что происходит на этаж выше\ниже. Это очень удобно при написании кода.

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

Алгоритм балансировки кчд

1. если правая нода красная и левая нода черная — левосторонний поворот
2. если левая нода красная и левая нода левой ноды красная — правосторонний поворот
3. если левая нода красная и правосторонняя нода красная — делаем свап цвета.

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

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

Немного об операции поиска значения

Операция получения ничем не будет отличаться от поиска в любом другом бинарном дереве — цвет тут никак не участвует.

Заключение

На этом я закончу нашу вторую часть про вставку и балансировку кчд. Задавайте свои вопросы, критикуйте и дополняйте статью ниже! В заключительной, третьей, части я расскажу про самую сложную тему красно-черного дерева — удаление элемента. До встречи:)

Источник

Красно-черные деревья: коротко и ясно

Итак, сегодня хочу немного рассказать о красно-черных деревьях. Рассказ будет кратким, без рассмотрения алгоритмов балансировки при вставке/удалении элементов в красно-черных деревьях.

Красно-черные деревья относятся к сбалансированным бинарным деревьям поиска.

Как бинарное дерево, красно-черное обладает свойствами:

1) Оба поддерева являются бинарными деревьями поиска.

2) Для каждого узла с ключом выполняется критерий упорядочения:

ключи всех левых потомков

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

Свойства красно-черных деревьев:

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

2) Корень окрашен в черный цвет.

3) Листья(так называемые NULL-узлы) окрашены в черный цвет.

4) Каждый красный узел должен иметь два черных дочерних узла. Нужно отметить, что у черного узла могут быть черные дочерние узлы. Красные узлы в качестве дочерних могут иметь только черные.

5) Пути от узла к его листьям должны содержать одинаковое количество черных узлов(это черная высота).

Ну и почему такое дерево является сбалансированным?

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

Пусть у нас есть красно-черное дерево. Черная высота равна (black height).

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

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

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

Как производится вставка?

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

Свойство 1 не нарушается, поскольку новому узлу сразу присваивается красный цвет.

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

Свойство 3 также не нарушается, поскольку при добавлении узла он получает черные листовые NULL-узлы.

В основном встречаются 2 других нарушения:

1) Красный узел имеет красный дочерний узел (нарушено свойство ).

2) Пути в дереве содержат разное количество черных узлов (нарушено свойство ).

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

Это вообще где-то используется?

Да! Когда в институте на третьем курсе нам читали «Алгоритмы и структуры данных», я и не могла представить, что красно-черные деревья где-то используются. Помню, как мы не любили тему сбалансированных деревьев. Ох уж эти родственные связи в красно-черных деревьях («дядя», «дедушка», «чёрный брат и крестный красный отец»), прям Санта-Барбара какая-то. Правые и левые, малые и большие повороты АВЛ-деревьев – сплошные американские горки. Вы тоже не любите красно-черные деревья? Значит, просто не умеете их готовить. А кто-то просто взял и приготовил. Так, например, ассоциативные массивы в большинстве библиотек реализованы именно через красно-черные деревья.

Это все, что я хотела рассказать.

Источник