Что такое красно черное дерево
Красно-чёрное дерево
Содержание
Введение
Здраствуйте. В этой статье мы разберемся что такое Черно-красные деревья и для чего они нужны.Начнем.
Красно-чёрное дерево (англ. Red-Black-Tree, RB-Tree) — это одно из самобалансирующихся двоичных деревьев поиска, гарантирующих логарифмический рост высоты дерева от числа узлов и быстро выполняющее основные операции дерева поиска: добавление, удаление и поиск узла. Сбалансированность достигается за счёт введения дополнительного атрибута узла дерева — «цвета». Этот атрибут может принимать одно из двух возможных значений — «чёрный» или «красный».
Изобретателем красно-чёрного дерева считают немца Рудольфа Байера. Название «красно-чёрное дерево» структура данных получила в статье Л. Гимпаса и Р. Седжвика (1978). В журнале были доступны две краски (красная и чёрная)[1] и дополнительный бит, «прикреплявшийся» к каждому из узлов, обозначался цветом.
Бинарное дерево(двоичное)
Двоичное дерево состоит из вершин и связей между ними. Конкретнее, у дерева есть выделенная вершина-корень и у каждой вершины может быть левый и правый сыновья. На словах звучит несколько сложно, но если взглянуть на картинку все становится понятным:
Пример бинарного дерева
У этого дерева корнем будет вершина A. Видно, что у вершины D отсутствует левый сын, у вершины B — правый, а у вершин G, H, F и I — оба. Вершины без сыновей принято называть листьями.
Каждой вершине X можно сопоставить свое дерево, состоящее из вершины, ее сыновей, сыновей ее сыновей, и т.д. Такое дерево называют поддеревом с корнем X. Левым и правым поддеревьями X называют поддеревья с корнями соответственно в левом и правом сыновьях X. Заметим, что такие поддеревья могут оказаться пустыми, если у X нет соответствующего сына.
Данные в дереве хранятся в его вершинах. В программах вершины дерева обычно представляют структурой, хранящей данные и две ссылки на левого и правого сына. Отсутствующие вершины обозначают null или специальным конструктором
Красно-черное дерево
Другие названия: Red-black tree, RB tree. В этой структуре баланс достигается за счет поддержания раскраски вершин в два цвета (красный и черный, как видно из названия :), подчиняющейся следующим правилам:
Модификация красно-черного дерева, в которой накладывается дополнительное ограничение: красная вершина может быть только правым сыном. Если красно-черное дерово изоморфно 2-3-4 дереву, то AA-дерево изоморфно 2-3 дереву.
Из-за дополнительного ограничения операции реализуются проще чем у красно-черного дерева (за счет уменьшения количества разбираемых случаев). Оценка на высоту деревьев остается прежней, 2*log2(n). Эффективность по времени у них примерно одинаковая, но так как в реализации вместо цвета обычно хранят другую характеристику («уровень» вершины), overhead по памяти достигает байта.
АВЛ-дерево
Названо так по фамилиям придумавших его советских математиков: Г.М. Адельсон-Вельского и Е.М. Ландиса.
Накладывает на дерево следующее ограничение: у любой вершины высоты левого и правого поддеревьев должны отличаться не более чем на 1. Легко доказать по индукции, что дерево с высотой h должно содержать как минимум F_h вершин, где F_i — i-ое число Фибоначчи. Так как F_i
phi^n (phi=(sqrt(5)+1)/2 — золотое сечение), высота дерева с n вершинами не может превысить log2(n)/log2(phi)
Реализация, как и у красно-черного дерева, основана на разборе случаев и достаточно сложна для понимания (хотя имхо проще красно-черного) и имеет сложность O(log(n)) на все основные операции. Для работы необходимо хранить в каждой вершине разницу между высотами левого и правого поддеревьев. Так как она не превосходит 1, достаточно использовать 2 бита на вершину.
Операции
Поворот
Левый и правый поворот дерева может быть выполнен так.
Вставка элемента
Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет nil (то есть этот сын — лист). Вставляем вместо него новый элемент с nil-потомками и красным цветом. Теперь проверяем балансировку.
Удаление вершины
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
Преимущества красно-чёрных деревьев
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
Балансировка красно-чёрных деревьев — Три случая
Двоичные деревья поиска — эта структура данных для хранения элементов с возможностью быстрого поиска. Идея проста и гениальна: «меньше – налево, больше – направо». На этом простота заканчивается и начинаются сложные вопросы балансировки дерева, чтобы оно не превратилось в длинную ветку.
В этой статье мы дадим определение, перечислим правила размещения элементов в красно-чёрном дереве, рассмотрим алгоритм балансировки и закрепим сказанное на примере. Более подробно эту тему, а также другие виды двоичных деревьев поиска мы изучаем на курсе «Алгоритмы для разработчиков».
Красно-чёрное дерево — самобалансирующиеся двоичное дерево поиска, которое гарантирует логарифмический рост высоты дерева от числа узлов и быстрое выполнение основных операций дерева поиска: добавление, удаление и поиск узла.
Красно-чёрное дерево не является полностью сбалансированным, в некоторых местах его высота может различаться почти в два раза. Такое допущение ассимптотически не влияет на скорость поиска элементов, но значительно ускоряет размещение новых элементов, потому что не нужно каждый раз при добавлении элементов «сильно трясти» дерево, иной раз достаточно просто добавить красный элемент, не трогая остальные и не изменяя «чёрную высоту».
Правила размещения элементов в красно-чёрном дереве
Рассмотрим правила балансировки для выполнения 3 и 4 пункта.
На каждом рисунке предполагается, что мы уже добавили элемент Х, который нарушает 3 правило, нужно так изменить структуру дерева, чтобы 3 правило выполнялось, а 4 не нарушилось.
Условные обозначения вершин:
Случай первый — красный дядя
Если и отец, и дядя красного цвета, то мы можем «спустить» чёрный цвет с уровня деда на уровень отца и перекрасить узлы, как показано на рисунке. В этом случае «чёрная высота» останется прежней, однако возможно нарушение 3 правила для элемента G, поэтому необходимо рекурсивно вызвать дальнейшую балансировку для этого узла.
Случай второй — чёрный дядя — папа и дед в разных сторонах.
Эту структуру необходимо привести к третьему случаю, когда папа и дед идут в одну сторону. Для этого нужно выполнить малый поворот от сына Х к его отцу (правила поворотов в этой статье не рассматриваются) и вызвать 3 случай для элемента Р.
Случай третий — чёрный дядя — папа и дед в одной стороне
В этом случае мы уже можем совершить большой поворот от отца через деда к чёрному дяде и перекрасить Р в чёрный, а G в красный. В результате этого поворота 3-правило будет выполнено.
Убедимся, что 4 правило тоже выполняется. Предположим, что до большого поворота чёрная высота элемента G была N+2. Тогда высота «подвешенных» элементов будет следующей:
A = N+1,
B = N+1,
C = N+1,
D = N,
E = N.
Убедитесь сами, что после поворота 4-правило выполняется для всех элементов.
Конкретный пример
Теперь рассмотрим процесс формирования красно-чёрного дерева при последовательной вставке элементов 1, 2, 3, 4, 5 и 6.
Так как элемент 1 является корнем — мы его просто перекрашиваем для выполнения 1 правила.
После добавления элемента 2 все правила выполняются.
При добавлении элемента 3 у нас нарушилось 3 правило. Так как у нас дядя чёрный, а дед и отец с одной стороны, то мы применяем третий случай — делаем поворот и перекрашиваем.
При добавлении элемента 4 у нас опять нарушается 3 правило. На этот раз дядя у нас красный, поэтому применим первый случай с перекрашиванием — чёрная высота дерева увеличится на 1. Обратите внимание. что алгоритм балансировки запускается ещё дополнительно для деда — элемента 2, который, как корень, просто перекрашивается в чёрный цвет.
При вставке элемента 5 мы снова применяем 3 случай — делаем большой поворот и перекрашиваем вершины. Обратите внимание, что чёрная высота не изменилась.
При добавлении элемента 6 мы снова нарушили 3 правило. Так как наш дядя красный, то применяем первый случай с перекрашиванием, чёрная высота не изменилась. Вызов балансировки для 4 элемента ничего не изменило в дереве, так как этот элемент не нарушает правил.
Итак, мы познакомились с вопросами балансировки красно-чёрного дерева, более подробно и с примерами алгоритмов эту тему, а также разновидности других двоичных деревьев поиска мы рассматриваем на курсе «Алгоритмы для разработчиков».
Понимаем красно-черное дерево. Часть 2. Балансировка и вставка
Часть 1. Введение
Часть 2. Балансировка и вставка
Это вторая часть из серии статей «Понимаем красно-черное дерево». Если вы пропустили первую часть, настоятельно рекомендую ознакомиться с ней здесь. Там мы разобрали причину появления кчд и расставили по полочкам некоторые его свойства.
В данной части мы разберем вставку и балансировку. Эти вещи идут бок о бок, без балансировки дерево будет терять свои свойства, и толка от него будет мало.
Все вставленные ноды, кроме корня дерева, вставляются с красным цветом. Объясняется это тем, что мы всегда сначала добавляем значение к уже существующей ноде и только после этого занимаемся балансировкой (вспомните ситуацию с получавшимися 4-нодами).
В первой части мы выяснили, что разбираем левостороннее красно-черное дерево, из этого следует, что красные ноды могут лежать только слева (обратный случай требует балансировки).
Также давайте разберемся с тремя операциями, которые понадобятся нам при балансировке. Я прошу не задумываться о них сейчас и вникнуть подробнее уже во время построения дерева. Я приведу их описание здесь, чтобы они не мешались потом:)
Если повороты будут для вас не понятны из этой статьи, то информации о них полно в интернете. Я же хочу показать, как ими пользоваться.
Левосторонний поворот(левый малый поворот)
Здесь мы будем поворачивать наш узел влево. Картинка иллюстрирует поворот операцию.
иллюстрация левого поворота
Правосторонний поворот(малый правый поворот)
Тот же поворот, но в другую сторону. Логика аналогична левостороннему.
иллюстрация правого поворота
Свап цвета
Важно сказать, что все три операции изменяют дерево только локально (свап цвета изменяет ноду на уровень выше, но мы считаем это локальным изменением), и вызываем мы их на уровне parentNode! Мы не теряем сбалансированность на других этажах (если она была). В этом вы можете убедиться самостоятельно.
Построение красно-черного дерева.
Итак, начнем построение нашего дерева.
Сначала добавим корень со значением 24. Тут как всегда все просто. Вы помните, что все добавленные ноды имеют красный цвет, кроме корня дерева.
Следующая нода, которую мы вставим, имеет значение 5. По правилу бинарного дерева, нода опускается влево и по правилу кчд становится красной нодой.
Нода со значением 1 становится потомком ноды 5. Здесь мы видим две идущие подряд красные ноды. В таком случае, нам нужно совершить нашу первую балансировку!
В конце этой части я приведу алгоритм и порядок проверок и выполнений операции балансировки для кчд. Но для того, чтобы вы поняли балансировку, а не просто запомнили, давайте попробуем покопаться сами.
Итак, в нашем арсенале 3 операции: правостороний поворот, левостороений поворот, свап цветов.
Теперь мы видим, что у корня два красных потомка. Вот здесь то нам и понадобится операция свапа цвета! Результат ниже. (По правилам свапа нода 24 должна была стать красной, но так как это корень, цвет снова стал черным)
В итоге у нас снова корректное левостороннее кчд (и даже без красных нод)! А вот как это выглядело бы в 2-3 дереве.
Двигаемся дальше. Вставляем значение 15. Нода уходит в левого потомка ноды 24. Здесь балансировка не нужна.
Вставляем 3. Нода будет меньше корня, но уже больше 1, поэтому нода становится правым потомком ноды-1.
Как мы видим, красная нода находится справа. И снова балансировка. В прошлый раз нас спасла комбинация правосторонний поворот + свап цвета. В этот раз поворот в право нас не спасет (как и свап цвета, я думаю, это очевидно). Сделаем поворот влево и посмотрим, что получится.
Вуаля! Наше дерево снова корректно.
Я думаю, что уже сейчас вырисовываются какие-то правила и закономерности действий, но давайте не будем торопиться и рассмотрим еще пару примеров.
Правосторонний поворот + свап цвета дает нам следующий результат.
Вам может показаться, что дерево перестроилось кардинальным образом. Но если приглядеться, то станет понятно, что это не так. Последний левосторонний поворот поменял наше дерево лишь на одном уровне. Все остальные ноды остались на месте.
Вот в целом и все. За исключением пары моментов, построение дерева будет выглядеть примерно так. Как и в случае 2-3 дерева попробуйте сейчас сами добавить пару значений в дерево (ноды 13 и 16, например, интересный случай).
Ниже в спойлере я приведу алгоритм, на который можно опираться при написании кода, а вы можете попробовать привести решение сами.
Алгоритм балансировки кчд
Теперь вы можете пробежаться по построению дерева еще раз и проанализировать, свериться со свойствами из первой статьи, задаться вопросами «а что будет если. » (поверьте, это очень полезно!). В целом, это все, что я хотел рассказать вам про вставку ноды в левостороннее красно-черное дерево.
Немного об операции поиска значения
Заключение
Красно-черное дерево
Красно-чёрное дерево (англ. red-black tree) — двоичное дерево поиска, в котором баланс осуществляется на основе «цвета» узла дерева, который принимает только два значения: «красный» (англ. red) и «чёрный» (англ. black).
При этом все листья дерева являются фиктивными и не содержат данных, но относятся к дереву и являются чёрными.
Для экономии памяти фиктивные листья можно сделать одним общим фиктивным листом.
Содержание
Свойства [ править ]
Оригинальные [ править ]
Красно-чёрным называется бинарное поисковое дерево, у которого каждому узлу сопоставлен дополнительный атрибут — цвет и для которого выполняются следующие свойства:
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей.
Альтернативные [ править ]
В книге Кормена «Алгоритмы: построение и анализ» дается немного иное определение красно-черного дерева, а именно:
Двоичное дерево поиска является красно-чёрным, если обладает следующими свойствами:
Высота красно-черного дерева [ править ]
| Определение: |
| Будем называть чёрной высотой (англ. black-height) вершины [math]x[/math] число чёрных вершин на пути из [math]x[/math] в лист. |
Следовательно, утверждение верно и для всего дерева.
| Теорема: |
| [math]\triangleleft[/math] |
Операции [ править ]
Вставка элемента [ править ]
Удаление вершины [ править ]
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева. Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращений.
Объединение красно-чёрных деревьев [ править ]
Разрезание красно-чёрного дерева [ править ]
Пройдем вниз как во время поиска. Все левые поддеревья вершин пути, корень которых не в пути, будут в первом поддереве. Аналогично правые — в правом. Теперь поднимаемся и последовательно сливаем деревья справа и слева с ответами.
За счет того, что функция $join$ работает за разницу высот, и мы объединяем снизу, то, благодаря телескопическому эффекту на работу времени будут влиять только крайние слагаемые, которые порядка глубины дерева.
Точно такой же алгоритм в разрезании AVL деревьев. Оно и понятно — нам нужна лишь корректная функция $join$, работающая за разницу высот.
Преимущества красно-чёрных деревьев [ править ]
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
Связь с 2-3 и 2-4 деревьями [ править ]
Изоморфизм деревьев [ править ]
Корректность сопоставления деревьев [ править ]
Сопоставив таким образом цвета узлам дерева, можно проверить, что полученное дерево удовлетворяет всем свойствам красно-черного дерева.
| Утверждение: |
| [math]\triangleright[/math] |
| В B-дереве глубина всех листьев одинакова, следовательно, одинаково и количество внутренних узлов на каждом пути. Мы сопоставляем чёрный цвет одному элементу внутреннего узла B-дерева. Значит, количество чёрных элементов на любом пути от листа до вершины одинаково. |
| [math]\triangleleft[/math] |
| Утверждение: |
| [math]\triangleright[/math] |
| Если в корне один элемент, то он — чёрный. Если же в корне несколько элементов, то заметим, что один элемент окрашен в чёрный цвет, остальные — в красный. Горизонтальные связи, соединяющие элементы внутри одного узнала, ведут из чёрного элемента в красный, следовательно, красные элементы будут подвешены к чёрному. Он и выбирается в качестве корня симметричного бинарного B-дерева. |
| [math]\triangleleft[/math] |
Сопоставление операций в деревьях [ править ]
Все операции, совершаемые в B-дереве, сопоставляются операциям в красно-черном дереве. Для этого достаточно доказать, что изменение узла в B-дереве соответствует повороту в красно-черном дереве.
В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Рассмотрим, как будет меняться структура B-дерева и, соответственно, красно-черного дерева при добавлении элемента: