Изменения
Исправлен бесконечный цикл в псевдокоде fixInsertion
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корю корню иметь красных детей.
Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <tex>$10$, $6$, $45$, $4$, $8</tex>$. На примере можно видеть, что после добавления вершины с ключом <tex>0</tex> и соответствующих перекрашиваний вершина с ключом <tex>6</tex> становится красной с красным родителем. Дальше добавим <tex>5</tex>. Так как мы добавляем к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого <tex>(-3)</tex>. Тогда вершина с ключом <tex>4</tex> станет красной (<tex>0</tex> и <tex>5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
===Альтернативные===
# Все пути, идущие от корня к листьям, содержат одинаковое количество черных вершин
То, что только черная вершина может иметь красных детей, совместно с <tex>4</tex>-тым ым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.
== Высота красно-черного дерева ==
{{Определение
|definition=Будем называть '''чёрной высотой''' (англ. ''black-height'') вершины <tex>x</tex> число чёрных вершин на пути из <tex>x</tex> в лист, не учитывая саму вершину <tex>x</tex>.
}}
{{Лемма
|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+-1}-1</tex>.
|proof=
}}
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Рассмотрим красно-чёрное дерево с высотой <tex>h</tex>. Так как у красной вершины чёрные дети (по свойству $3$) количество красных вершин не больше $\dfrac{h}{2}$.
Тогда чёрных вершин не меньше, чем <tex>\dfrac{h}{2} - 1</tex>.
<tex>N \geqslant 2^{h/2}-1</tex>
Прологарифмировав неравенство, имеем:
<tex>\log(N+1) \geqslant \dfrac{h/}{2}</tex>
<tex>2\log(N+1) \geqslant h</tex>
Узел, с которым мы работаем, на картинках имеет имя <tex>x</tex>.
=== Вставка элемента ===
Каждый элемент вставляется вместо листа, поэтому для выбора места вставки идём от корня до тех пор, пока указатель на следующего сына не станет <tex>nil</tex> (то есть этот сын {{---}} лист). Вставляем вместо него новый элемент с <tex>nil</tex>-нулевыми потомками и красным цветом. Теперь проверяем балансировку. Если отец нового элемента черный, то никакое из свойств дерева не нарушено. Если же он красный, то нарушается свойство <tex>3</tex>, для исправления достаточно рассмотреть два случая: 1. # "Дядя" этого узла тоже красный. Тогда, чтобы сохранить свойства <tex>3</tex> и <tex>4</tex>, просто перекрашиваем "отца" и "дядю" в чёрный цвет, а "деда" {{---}} в красный. В таком случае черная высота в этом поддереве одинакова для всех листьев и у всех красных вершин "отцы" черные. Проверяем, не нарушена ли балансировка. Если в результате этих перекрашиваний мы дойдём до корня, то в нём в любом случае ставим чёрный цвет, чтобы дерево удовлетворяло свойству <tex>2</tex>. [[Файл:Untitled-1.png|200px]] 2. # "Дядя" чёрный. Если выполнить только перекрашивание, то может нарушиться постоянство чёрной высоты дерева по всем ветвям. Поэтому выполняем поворот. Если добавляемый узел был правым потомком, то необходимо сначала выполнить левое вращение, которое сделает его левым потомком. Таким образом, свойство <tex>3</tex> и постоянство черной высоты сохраняются.
[[Файл:Untitled-2.png|250px|]]
'''func''' insert(key)
Node t = Node(key, red, ''nil'', ''nil'') <font color=green>// конструктор, в который передаем ключ, цвет, левого и правого ребенка </font>
'''if''' root == ''nil''дерево пустое
root = t
t.parent = ''nil''
Node p = root
Node q = ''nil''
'''while''' p != ''nil''<font color=green>// спускаемся вниз, пока не дойдем до подходящего листа </font>
q = p
'''if''' p.key < t.key
p = p.left
t.parent = q
<font color=green>// добавляем новый элемент красного цвета </font>
'''if''' q.key < t.key
q.right = t
'''func''' fixInsertion(t: '''Node''')
'''if''' root == t{{---}} корень t.colour = black
'''return'''
<font color=green>// далее все предки упоминаются относительно t </font> '''while''' t.parent !"отец" красный <font color= ''nil'' '''and''' t.parent.colour == red Node grandfather = t.parent.parent Node uncle = ''nil''green>// нарушается свойство <tex>3</tex> </font> '''if''' grandfather.left == t.parent "отец" {{---}} левый ребенок '''if''' grandfather.right != ''nil'' uncle = grandfather.right '''if''' uncle.colour == red <font color=green>// случай, когда есть красный "дядя" красный </font> t. parent.colour = black uncle.colour = black grandfather.colour = red t = grandfather
'''else'''
'''if''' t.{{---}} правый сын t = parent leftRotate(t) parent = black grandfather = red rightRotate(grandfather) '''else''' <font color=green>// "отец" {{---}} правый ребенок </font> '''if''' есть красный "дядя" parent.right =black uncle = black grandfather = red t = grandfather '''else''' <font color= green>// нет "дяди" </font> '''if''' t{{---}} левый ребенок
t = t.parent
=== Удаление вершины ===
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
'''else'''
p = p.left
root = ''nil''
'''else'''
'''return'''
Node y = ''nil''
Node q = ''nil''
'''if''' p.left == ''nil'' '''or''' p.right == ''nil'' <font color=green>// один ребенок</font> ссылку на у от "отца" меняем на ребенка y = p
'''else'''
<font color=green>// два ребенка</font>
'''else'''
у родителя ссылку на y меняем на ссылку на первого ребенка y.parent.right = q
'''if''' y != p
p.colour = y.colour
'''if''' y.colour == black
<font color=green>// при удалении черной вершины могла быть нарушена балансировка</font>
fixDeleting(q);
'''func''' fixDeleting(p: '''Node''')
'''else'''
'''if''' brother.right isBlackправый ребенок "брата" черный <font color=green>// случай, рассматриваемый во втором подпункте:</font> brother.left.colour = black <font color=green>// "брат" красный с черными правым ребенком</font> brother.colour = red
rightRotate(brother)
p = root
'''else''' <font color=green>// p is rightChild {{---}} правый ребенок</font> brother <font color= p.parent.leftgreen>// все случаи аналогичны тому, что рассмотрено выше</font> '''if''' brother isRed"брат" красный brother.colour = black p.parent.colour = red
rightRotate(p.parent)
'''else'''
'''if''' brother.left isBlackлевый ребенок "брата" черный brother.right.colour = black brother.colour = red
leftRotate(brother);
rightRotate(p.parent)
p = root
p.colour = black root.colour = black
=== Объединение красно-чёрных деревьев ===
Объединение двух красно-чёрных деревьев <tex>T_{1}</tex> и <tex>T_{2}</tex> по элементу ключу <tex>xk</tex> выполняетсявозвращает дерево с элементами из $T_2$, когда <tex>key[T_{1}] \leqslant x</tex> $T_1$ и <tex>x \leqslant key[T_{2}]</tex>, где <tex>key[T]</tex> $k$. Требование: ключ $k$ {{---}} максимальные ключи дерева <tex>T</tex>разделяющий.Найдём чёрные высоты деревьев. Предположим такжеТо есть $\forall k_1\in T_1, что <tex>hb[T_{1}] k_2 \in T_2: k_1\leqslant k\geqslant hb[T_{2}]</tex>. Тогда в дереве <tex>T_{1}</tex> ищем среди чёрных вершин, имеющих чёрную высоту <tex>hb[T_{2}]</tex>, вершину <tex>y</tex> с наибольшим ключом. Пусть <tex>T_{y}</tex> — поддерево с корнем <tex>y</tex>. Объединяем это дерево с <tex>T_{2}</tex> в одно с красным корнем <tex>x</tex>. Теперь родителем вершины <tex>x</tex> становится бывший отец вершины <tex>y</tex>. Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершиныleqslant k_2$.
Если <tex>hb[T_{оба дерева имеют одинаковую черную высоту, то результатом будет дерево с черным корнем $k$, левым и правым поддеревьями $k_1$ и $k_2$ соответствено. Теперь пусть у $T_1$ черная высота больше (иначе аналогично). * Находим в дереве $T_1$ вершину $y$ на черной высоте, как у дерева $T_2$ вершину с максимальным ключом. Это делается несложно (особенно если мы знаем черную высоту дерева): спускаемся вниз, поддерживая текущую черную высоту.*:Идем вправо. Когда высота станет равной высоте $T_2$, остановимся.*:Заметим, что черная высота $T_2\geqslant 2$. Поэтому в дереве $T_1$ мы не будем ниже, чем $2$. Пусть мы не можем повернуть направо (сын нулевой), тогда наша высота $2$ (если мы в черной вершине) или $1}] $ (если в красной). Второго случая быть не может, ибо высота $T_2\leqslant hb[T_{geqslant 2}]</tex>$, а в первом случае мы должны были завершить алгоритм, когда пришли в эту вершину.*:Очевидно, мы окажемся в черной вершине (ибо следующий шаг даст высоту меньше). Очевидно, мы оказались на нужной высоте.*:Теперь пусть мы попали не туда. То есть существует путь от корня до другой вершины. Посмотрим на то слияние происходит аналогичноместо, только теперь где мы не туда пошли. Если мы ищем пошли вправо, а надо бы влево, то $x$ имеет больший ключ (по свойству дерева поиска). А если пошли влево, а не вправо, значит правого сына и нет (точнее, есть, но он нулевой), значит в правом поддереве вообще нет вершин.*:Более того, все вершины с высотами меньше $y$, которые имеют ключ больше $y$, будут находиться в дереве <tex>T_поддереве $y$. Действительно, мы всегда идем вправо. Инвариант алгоритма на каждом шаге {{2---}}</tex> среди чёрных вершинв поддереве текущей вершины содержатся все вершины, ключ которых больше текущего. Проверяется очевидно.*:Еще поймем, имеющих чёрную как будем хранить черную высоту <tex>hb[T_{1}]</tex>дерева. Изначально она нулевая (в пустом дереве). Далее просто поддерживаем ее при операциях вставки и удаления.* Объединим поддерево. $k$ будет корнем, левым и правым сыновьями будут $T_y$ и $T_2$ соответственно.*:Покажем, вершину <tex>что свойства дерева поиска не нарушены.*:Так как все ключи поддерева $y</tex> $ не более $k$ и все ключи $T_2$ не менее $k$, то в новом поддереве с наименьшим ключомкорнем $k$ свойства выполняются.*:Так как $k$ больше любого ключа из $T_1$, то выполняется и для всего дерева.* Красим $k$ в красный цвет. Тогда свойство $4$ будет выполнено. Далее поднимаемся вверх, как во вставке операциях, поворотами исправляя нарушение правила $3$.* В конце корень красим в черный, если до этого был красный (это всегда можно сделать, ничего не нарушив). '''Псевдокод:''' '''func''' join(T_1, T_2, k) '''if''' черные высоты равны return Node(k, black, T_1, T_2) '''if''' высота T_1 больше T' = joinToRight(T_1, T_2, k) T'.color = black return T' '''else''' T' = joinToLeft(T_1, T_2, k) T'.color = black return T' '''func''' joinToRight(T_1, T_2, k) Y = find(T_1, bh(T_2)) T' = Node(k, red, Y, T_2) '''while''' нарушение действуем как во вставке return T' '''func''' find(T, h) curBH = bh(T) curV = T '''while''' curBH != h curV = curV.right '''if''' curV. color == black --curBH return curV
== Преимущества красно-чёрных деревьев ==
#Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более <tex>O(1)</tex> вращений. Это важно, например, в алгоритме построения [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)|динамической выпуклой оболочки]]. Ещё важно, что примерно половина вставок и удалений произойдут задаром.
#Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
#Сбалансированность этих деревьев хуже, чем у [[АВЛ-дерево | АВЛ]], но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.#Использует всего $1 $ бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит $2 $ бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях. TreeMap в Java тоже реализован на основе красно-чёрных деревьев.
== Связь с [[2-3_дерево | 2-3 и 2-4 деревьями ]] ==
=== Изоморфизм деревьев ===
Красно-черные деревья изоморфны [[B-дерево | B-деревьям]] $4 $ порядка. Реализация B-деревьев трудна на практике, поэтому для них был придуман аналог, называемый симметричным бинарным B-деревом<ref>[http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]</ref>. Особенностью симметричных бинарных B-деревьев является наличие горизонтальных и вертикальных связей. Вертикальные связи отделяют друг от друга разные узлы, а горизонтальные соединяют элементы, хранящиеся в одном узле B-дерева. Для различения вертикальных и горизонтальных связей вводится новый атрибут узла {{---}} цвет. Только один из элементов узла в B-дереве красится в черный цвет. Горизонтальные связи ведут из черного узла в красный узел, а вертикальные могут вести из любого узла в черный.
[[Файл:Rbtree.png|750px|]]
Число черных узлов на любом пути от листа до вершины одинаково.
|proof=
В B-дереве глубина всех листьев одинакова. Из каждого узла B-дерева выбирается только один элемент для окраски в черный цвет, следовательно, одинаково и путь в симметричным бинарным B-дереве состоит только из элементов, лежащих количество внутренних узлов на одном каждом пути в . Мы сопоставляем чёрный цвет одному элементу внутреннего узла B-дереведерева. Значит , количество черных чёрных элементов на любом пути от листа до вершины одинаково.
}}
{{Утверждение
Корень дерева {{---}} черный.
|proof=
}}