В этой статье мы дадим определение, перечислим правила размещения элементов в красно-чёрном дереве, рассмотрим алгоритм балансировки и закрепим сказанное на примере. Более подробно эту тему, а также другие виды двоичных деревьев поиска мы изучаем на курсе «Алгоритмы для разработчиков».
Красно-чёрное дерево — самобалансирующиеся двоичное дерево поиска, которое гарантирует логарифмический рост высоты дерева от числа узлов и быстрое выполнение основных операций дерева поиска: добавление, удаление и поиск узла.
Красно-чёрное дерево не является полностью сбалансированным, в некоторых местах его высота может различаться почти в два раза. Такое допущение ассимптотически не влияет на скорость поиска элементов, но значительно ускоряет размещение новых элементов, потому что не нужно каждый раз при добавлении элементов «сильно трясти» дерево, иной раз достаточно просто добавить красный элемент, не трогая остальные и не изменяя «чёрную высоту».
Правила размещения элементов в красно-чёрном дереве
- Каждый узел либо красный, либо чёрный, NIL-листья всегда чёрные.
- Корень дерева всегда чёрный
- Оба потомка каждого красного узла — чёрные
- Путь вниз от любого узла до любого листа-потомка содержит одинаковое число чёрных узлов.
При вставке нового элемента ему присваивается красный цвет. Для выполнения первых двух правил достаточно просто перекрашивать новые вершины в нужный цвет.
Рассмотрим правила балансировки для выполнения 3 и 4 пункта.
На каждом рисунке предполагается, что мы уже добавили элемент Х, который нарушает 3 правило, нужно так изменить структуру дерева, чтобы 3 правило выполнялось, а 4 не нарушилось.
Условные обозначения вершин:
- X — добавленный элемент, который нарушает 3 пункт правил.
- P — папа элемента Х
- G — дедушка элемента Х, папа элемента Р
- U — дядя элемента Х, брат элемента Р, второй сын элемента G.
Случай первый — красный дядя
Если и отец, и дядя красного цвета, то мы можем «спустить» чёрный цвет с уровня деда на уровень отца и перекрасить узлы, как показано на рисунке. В этом случае «чёрная высота» останется прежней, однако возможно нарушение 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 элемента ничего не изменило в дереве, так как этот элемент не нарушает правил.
Итак, мы познакомились с вопросами балансировки красно-чёрного дерева, более подробно и с примерами алгоритмов эту тему, а также разновидности других двоичных деревьев поиска мы рассматриваем на курсе «Алгоритмы для разработчиков».
Комментарии (28)
vintage
19.10.2019 11:43Красно-чёрное дерево — это как сортировка пузырьком в мире деревьев. Более расточительную по памяти структуру придумать сложно.
FFormula Автор
19.10.2019 13:19+1В чём же расточительство? Элемент NIL хранится в единственном экземпляре и подвешивается везде, где нужно, увеличение объёма только в одном бите цвета на каждую вершину. Или вы в чём-то ещё видите расточительство?
vintage
19.10.2019 16:25NIL вообще не хранится и является нулевым указателем, что даёт нам +8 байт на каждый узел в дереве, а число узлов равно числу ключей. Даже если мы введём 4 типа узлов разного размера (разветвление, левая полуветка, правая полуветка, лист), то это даст +2 бита на каждый узел (вместе с цветом =3). И при этом балансировка оставляет желать лучшего.
vintage
19.10.2019 16:31Для сравнения: 2-3 B-дерево потребует всего 1 бит на каждый узел для указания его размера, число узлов будет в среднем в полтора раза меньше числа ключей, а с балансировкой там всё в порядке.
Barbaresk
19.10.2019 19:42Число узлов в полтор раза меньше, но при этом число указателей меньше лишь на четверть. Половина узлов — одинарные, имеют два указателя. Половина узлов — двойные, имеют три указателя. Т.е. в среднем на 3 ключа 5 указателей и бит размера. В кч — 6 указателей на 3 ключа и бит цвета. И это всё при условии, что у нас узлы 2-3 дерева динамически меняются по размеру, что требует постоянных обращений к аллокатору памяти. А если мы делаем все узлы 2-3 дерева размером под максимальное число элементов для ускорения вставки, то преимущества по памяти вообще теряются. И не забывайте, для чего вообще эти деревья нужны — для ускорения поиска и вставки всё же. Если же необходим размер — можно пихать всё в упорядоченный/неупорядоченный массив. Там вообще ничего лишнего.
vintage
19.10.2019 21:07Половина узлов — одинарные, имеют два указателя.
Половина узлов — листовые, не имеют указателей. Указатели имеют лишь ветви. Так как глубина листьев всегда одинаковая, достаточно отдельно хранить глубину дерева, чтобы понимать какие ссылки указывают на ветки, а какие на листья.
И это всё при условии, что у нас узлы 2-3 дерева динамически меняются по размеру, что требует постоянных обращений к аллокатору памяти.
Уменьшать нет смысла (всё-равно придётся снова увеличивать или удалять целиком), а если только увеличивать, то число аллокаций в худшем случае будет равным rb-tree. Но даже если выделять памяти с запасом, экономия на листьях с лихвой перекроет эти затраты.
И не забывайте, для чего вообще эти деревья нужны — для ускорения поиска и вставки всё же.
Так с поиском у rb-tree тоже всё плохо. Вот на скринах, например, для поиска 14 узла нужно сделать 5 хопов против 2.
Barbaresk
19.10.2019 22:15+1Половина узлов — листовые, не имеют указателей. Указатели имеют лишь ветви. Так как глубина листьев всегда одинаковая, достаточно отдельно хранить глубину дерева, чтобы понимать какие ссылки указывают на ветки, а какие на листья.
Ок, тогда можно сделать как, собственно вы же и написали — хранить два бита для определения типа узла.
Уменьшать нет смысла (всё-равно придётся снова увеличивать или удалять целиком), а если только увеличивать, то число аллокаций в худшем случае будет равным rb-tree. Но даже если выделять памяти с запасом, экономия на листьях с лихвой перекроет эти затраты.
Если мы не будем уменьшать, то тогда у нас лишняя память как раз и будет стоить те самые выигранные биты.
Так с поиском у rb-tree тоже всё плохо. Вот на скринах, например, для поиска 14 узла нужно сделать 5 хопов против 2.
А как в 2-3 дереве получили 2 сравнения? Те же самые 5 операций сранения:
14? 4, 14? 8, 14? 10, 14? 12, 14? 13. Да и вообще, считать по таким примерам число сравнений довольно сомнительно. Важно как характеристика ведёт себя логарифмически на больших числах.vintage
19.10.2019 23:37Ок, тогда можно сделать как, собственно вы же и написали — хранить два бита для определения типа узла.
И тогда мы получим те же проблемы с аллокациями памяти.
Если мы не будем уменьшать, то тогда у нас лишняя память как раз и будет стоить те самые выигранные биты.
В худшем случае.
А как в 2-3 дереве получили 2 сравнения?
Сравнения ничего не стоят. Стоят хопы — переходы по указателям.
Важно как характеристика ведёт себя логарифмически на больших числах.
Интуитивная оценка: до двух крат разницы по глубине между узлами, что даёт в среднем процентов на 30 больше хопов по сравнению с оптимально сбалансированным деревом.
Barbaresk
20.10.2019 19:32Если считать по числу обащений памяти, то, пожалуй, да. Хотя всё же это слишком громко называть «сортировкой пузырькой». Разница на некий постоянный коэффициент, а не на поведение функции в целом. Но, кстати, следуя вашим же аргументам, выгоднее использовать B-дерево с бо'льшим основанием. Тогда число обращений к участкам памяти, расположенным не рядом, будет ещё меньше.
GlukKazan
19.10.2019 13:38Легко. AVL-деревья более расточительные, поскольку им требуется хранить большее количество служебной информации, для выполнения балансировки.
vintage
19.10.2019 16:07Там нужно хранить лишь 2 бита для разницы высот вместо 1 бита цвета. В этом плане разница с красно-чёрным незначительна.
Barbaresk
19.10.2019 13:52+3Справедливости ради, никакой ценности данная статья не представляет. Википедия. На вики всё описано очень подробно, но еще в добавок есть код реализации дерева на С, описана операция удаления из дерева. А данная статья, судя по всему, является рерайтом статьи с вики. Причём в статье на хабре намеренно не было рассмотрено удаление, а ведь удаление это всегда самый гемор в балансированных деревьях. И, кстати, о рерайте говорит то, что если забить статью в text.ru, выдаётся 15% плагиата в разных местах с той же вики. Ах да, ещё и картинка с вики)) В общем, статья ради рекламы сервиса…
Magikan
За статью спасибо.
Правда мне всегда было интересно зачем все это извращение с бинарными деревьями(кроме фана для души), когда существует более эффективное семейство B-деревьев.
GlukKazan
Красно-чёрное дерево можно рассматривать (немножко под другим углом) как 2-3 дерево — частный случай B-дерева. Широко используется для хранения данных в оперативной памяти. В STL, если мне склероз не изменяет, использовались.
igor_suhorukov
Каждой задаче свой инструмент: для структур в памяти подходят почти сбалансированные двоичные деревья, а B-деревьев для внешней памяти. Как часто используемый пример красно-черных деревьев в стандартной библиотеке Java -TreeMap
https://docs.oracle.com/javase/8/docs/api/java/util/TreeMap.html
bgnx
Что внешняя память что оперативка имеет один и тот же параметр — размер блока и понятие локальности когда работать с размерами меньше этого блока не имеет смысла потому что любое обращение к памяти будет грузить или записывать весь этот блок. Соотвественно B-деревья походят не только для внешней памяти а и для структур в памяти поскольку нет смысла делать узел меньше чем размер блока (для оперативной памяти вместо блока используется название "кеш-линия") — то есть для современных процессоров нет смысла делать узел дерева размером меньше 64 байта (размер кеш-линии в x64 и arm). И узнать какой будет ранг у б-дерева можно просто поделив 64 байта на размер указателя на другие узлы (указатели тоже можно закодировать более компактно если ограничить их общее количество)
ukt
Можно уточнить по какому именно параметру B-деревья эффективнее?
bgnx
B-деревья эффективнее работают с кешем процессора
FFormula Автор
Все эти «извращения» возникают из желания придумать простой способ балансировки для такой простой идеи, как двоичное дерево поиска. К сожалению, просто не получается. Лично мне из всех попыток балансировки больше всего нравится рандомизированные деревья, которые уравновешиваются законом распределения случайных чисел.