Изменения
Исправлен бесконечный цикл в псевдокоде 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>-тым ым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.
== Высота красно-черного дерева ==
Тогда черные высоты детей могут быть $hb(x)$ или $hb(x)-1$ {{---}} если потомок красный или черный соответственно.
Тогда по предположению индукции в каждом из поддеревьев не менее $2^{hb(x)-2}-1$ вершин. Тогда всего в поддереве не менее $2*\cdot(2^{hb(x)-2}-1)+1 = 2^{hb(x)-1}-1$ вершин ($+1$ {{---}} мы учли еще саму вершину $x$).
Переход доказан.
|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</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|]]
'''while''' "отец" красный <font color=green>// нарушается свойство <tex>3</tex> </font>
'''if''' "отец" {{---}} левый ребенок
'''if''' есть красный "дядя" '''if''' "дядя" красный parent = black uncle = black grandfather = red t = grandfather
'''else'''
'''if''' t {{---}} правый сын
t = parent
rightRotate(grandfather)
'''else''' <font color=green>// "отец" {{---}} правый ребенок </font>
'''if''' есть красный "дядя" '''if''' "дядя" красный parent = black uncle = black grandfather = red t = grandfather
'''else''' <font color=green>// нет "дяди" </font>
'''if''' t {{---}} левый ребенок
=== Удаление вершины ===
При удалении вершины могут возникнуть три случая в зависимости от количества её детей:
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
#Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более <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|]]