Красно черное дерево преимущества

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Структуры данных: бинарные деревья. Часть 2: обзор сбалансированных деревьев

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

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

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

Пример:

Давайте посмотрим, какой может быть максимальная глубина корректного красно-черного дерева с n вершинами.
Возьмем самый глубокий лист. Пусть он находится на глубине h. Из-за правила 1, как минимум половина вершин на пути из корня будет черными, то есть черная высота дерева будет не меньше h/2. Можно показать, что в таком дереве будет не менее 2^(h/2)-1 черных вершин (так как у каждой черной вершины с черной глубиной k, если она не лист, должно быть как минимум два потомка с черной глубиной k+1). Тогда 2^(h/2)-1

Все основные операции с красно-черным деревом можно реализовать за O(h), то есть O(log n) по доказанному выше. Классическая реализация основана на разборе большого количества случаев и довольно трудна для восприятия. Существуют более простые и понятные варианты, например в статье Криса Окасаки. К сожалению, в ней описана только операция вставки в дерево. Простота по сравнению с классической реализацией получается за счет ориентации на понятность, а не на оптимизацию количества элементарных модификаций дерева (вращений).

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

Красно-черные деревья широко используются — реализация set/map в стандартных библиотеках, различные применения в ядре Linux (для организации очередей запросов, в ext3 etc.), вероятно во многих других системах для аналогичных нужд.

Красно-черные деревья тесно связаны с B-деревьями. Можно сказать, что они идентичны B-деревьям порядка 4 (или 2-3-4 деревьям). Более подробно об этом можно прочитать в статье на википедии или в книге «Алгоритмы: построение и анализ», упомянутой в прошлой статье.

AA-дерево

Модификация красно-черного дерева, в которой накладывается дополнительное ограничение: красная вершина может быть только правым сыном. Если красно-черное дерово изоморфно 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) ~ 1.44*log2(n)

Реализация, как и у красно-черного дерева, основана на разборе случаев и достаточно сложна для понимания (хотя имхо проще красно-черного) и имеет сложность O(log(n)) на все основные операции. Для работы необходимо хранить в каждой вершине разницу между высотами левого и правого поддеревьев. Так как она не превосходит 1, достаточно использовать 2 бита на вершину.

Подробное описание можно найти в книге Н. Вирта «Алгоритмы + структуры данных = программы» или в книге А. Шеня «Программирование: теоремы и задачи»

Декартово дерево

Другие названия: Cartesian tree, treap (tree+heap), дуча (дерево+куча).

Если рисовать дерево на плоскости, ключ будет соответствовать x-координате вершины (за счет упорядоченности). Тогда можно ввести и y-координату (назавем ее высотой), которая будет обладать следующим свойством: высота вершины больше высоты детей (такое же свойство имеют значения в другой структуре данных на основе двоичных деревьев — куче (heap). Отсюда второй вариант названия той структуры)

Оказывается, если высоты выбирать случайным образом, высота дерева, удовлетворяющего свойству кучи наиболее вероятно будет O(log(n)). Численные эксперименты показывают, что высота получается примерно 3*log(n).

Реализация операций проста и логична, за счет этого структура очень любима в спортивном программировании). По результатам тестирования, признана наиболее эффективной по времени (среди красно-черных, AA и АВЛ — деревьев, а так же skip-list’ов (структура, не являющаяся двоичным деревом, но с аналогичной областью применения) и radix-деревьев). К сожалению, обладает достаточно большим overheadом по памяти (2-4 байта на вершину, на хранение высоты) и неприминима там, где требуется гарантированная производительность (например в ядре ОС).

Splay-дерево

Эта структура данных сильно отличается от всех перечисленных до этого. Дело в том, что оно не накладывает никаких ограничений на структуру дерева. Более того, в процессе работы дерево может оказаться полностью разбалансированным!

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

Зная магию операции splay, эти деревья реализуются не легко, а очень легко, поэтому они тоже очень популярны в ACM ICPC, Topcoder etc.

Ясно, что в таком дереве нельзя гарантировать сложность операций O(log(n)) (вдруг нас попросят найти глубоко залегшую вершину в несбалансированном на данный момент дереве?). Вместо этого, гарантирается амортизированная сложность операции O(log(n)), то есть любая последовательность из m операций с деревом размера n работает за O((n+m)*log(n)). Более того, splay-дерево обладает некоторыми магическими свойствами, за счет которого оно на практике может оказаться намного эффективнее остальных вариантов. Например, вершины, к которым обращались недавно, оказываются ближе к корню и доступ к ним ускоряется. Более того, доказано что если вероятности обращения к элементам фиксированы, то splay-дерево будет работать асимптотически не медленней любой другой реализации бинарных деревьев. Еще одно преимущество в том, что отсутствует overhead по памяти, так как не нужно хранить никакой дополнительной информации.

В отличие от других вариантов, операция поиска в дереве модифицирует само дерево, поэтому в случае равномерного обращения к элементам splay-дерево будет работать медленней. Однако на практике оно часто дает ощутимый прирост производительности. Тесты это подтверждают — в тестах, полученных на основе Firefox’а, VMWare и Squid’а, splay-дерево показывает прирост производительности в 1.5-2 раза по сравнению с красно-черными и АВЛ- деревьями. В тоже время, на синтетических тестах splay-деревья работают в 1.5 раза медленней. К сожалению, из-за отсутствия гарантий на производительность отдельных операций, splay-деревья неприминимы в realtime-системах (например в ядре ОС, garbage-collector’ах), а так же в библиотеках общего назначения.

Scapegoat-дерево

Коэффициент жесткости сильно влияет на баланс производительности: чем «жестче» дерево, тем меньше у него будет высота и тем быстрее будет работать поиск, но тем сложнее будет поддерживать порядок в операциях модификации. Например, так как АВЛ-дерево «жестче» красно-черного, поиск в нем работает быстрее, а модификация медленней. Если же пользоваться scapegoat-деревом, баланс между этими операциями можно выбирать в зависимости от специфики применения дерева.

Еще пара слов

Два последних дерева сильно отличаются от своих конкурентов. Например, только они могут использоваться в эффективной реализации структуры данных link/cut tree, использующейся в основе наиболее быстрого известного алгоритма поиска потока в графе. С другой стороны из-за их амортизационной сути они не могут использоваться во многих алгоритмах, в частности для построения ropes. Свойства этих деревьев, особенно splay-дерева, в настоящее время активно изучаются теоретиками.

Кроме сбалансированных деревьев, можно использовать следующий трюк: реализовать обычное бинарное дерево и в процессе работы периодически делать ребалансировку. Для этого существует несколько алгоритмов, например DSW algorithm, работающий за O(n)

В следующей серии

Я расскажу более подробно про декартовы деревья и их реализацию

Источник