Изменения
→Высота красно-черного дерева
# Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов
# Чёрный узел может иметь чёрного родителя
[[Файл:konspkonspv2.jpg|350px|thumb|Ослабленное красно-чёрное дерево.]]
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться, и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится.
Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей. Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <tex>10, 6, 45, 4, 8</tex>. На примере можно видеть, что после добавления вершины с ключом <tex>F0</tex> и соответствующих перекрашиваний вершина с ключом <tex>B6</tex> становится красной с красным родителем. Дальше добавим вершину <tex>G5</tex>. Так как мы добавляем ее к черной вершине, все свойства дерева сохраняются без перекрашиваний. Но добавим после этого вершину <tex>H-3</tex>. Тогда вершина с ключом <tex>D4</tex> станет красной (<tex>F0</tex> и <tex>G5</tex> {{---}} черными) и у нас образуются три красные вершины подряд. Продолжая добавлять вершины таким образом, мы можем сделать сильно разбалансированное дерево.
===Альтернативные===
{{Лемма
|statement= В красно-черном дереве с черной высотой <tex>hb</tex> количество внутренних вершин не менее <tex>2^{hb+1}-1</tex>.
|proof=
По индукции докажем, что поддерево любого узла <tex>x</tex> с черной высотой <tex>hb(x)</tex> содержит не менее <tex>2^{hb(x)} - 1</tex> внутренних узлов. '''База индукции:''' Если рассмотреть высота узла <tex>x</tex> равна <tex>0,</tex> то <tex>x</tex> {{---}} это лист , <tex>hb(фиктивную вершинуx)= 0, то </tex> <tex>2^{0} - 1 = 0.</tex> '''Индукционный переход:''' Пусть наше предположение верно для нее лемма вернавысот до <tex>h'. Рассмотрим </tex> Теперь рассмотрим внутреннюю вершину <tex>x</tex>. Пусть с двумя потомками, для которой <tex>hb(x)=h'</tex>. Тогда если ее потомок <tex>p</tex> {{---}} черный, то его высота <tex>hb(p)=h'-1</tex>, а если красный, то <tex>hb(p) = h'</tex>. Таким образомНо поскольку высота потомка меньше, по предположению индукциичем высота узла <tex>x</tex>, для него выполняется индукционное предположение. В таком случае в поддеревьях содержится не менее поддереве узла <tex>2^{h'}-1x</tex> вершин, а во всём дереве, соответственно, содержится не менее чем <tex>2^{h'-1}-1 + 2^{h'-1}-1 + 1=2^{h'+1}-1</tex>. Следовательно, утверждение верно и для всего дерева.
}}
|statement=Красно-чёрное дерево с <tex>N</tex> ключами имеет высоту <tex>h = O(\log N)</tex>.
|proof=
Рассмотрим красно-чёрное дерево с высотой <tex>h.</tex> Так как у красной вершины чёрные дети <tex>(</tex>по свойству <tex>3),</tex> количество красных вершин не больше <tex>h / 2. </tex> Тогда чёрных вершин не меньше, чем <tex>h / 2 - 1.</tex>
<tex>N \geqslant 2^{h/2}-1</tex>
[[Файл:Untitled-2.png|250px|]]
'''Псевдокод:'''
'''func''' insert(key)
Node t = Node(key, red, ''nil'', ''nil'') <font color=green>// конструктор, в который передаем ключ, цвет, левого и правого ребенка </font>
'''if''' дерево пустое
root = t
t.parent = ''nil''
'''else'''
Node p = root
Node q = ''nil''
'''while''' p != ''nil'' <font color=green>// спускаемся вниз, пока не дойдем до подходящего листа </font>
q = p
'''if''' p.key < t.key
p = p.right
'''else'''
p = p.left
t.parent = q
<font color=green>// добавляем новый элемент красного цвета </font>
'''if''' q.key < t.key
q.right = t
'''else'''
q.left = t
fixInsertion(t) <font color=green>// проверяем, не нарушены ли свойства красно-черного дерева </font>
'''func''' fixInsertion(t: '''Node''')
'''if''' t {{---}} корень
t = black
'''return'''
<font color=green>// далее все предки упоминаются относительно t </font>
'''while''' "отец" красный <font color=green>// нарушается свойство <tex>3</tex> </font>
'''if''' "отец" {{---}} левый ребенок
'''if''' есть "дядя"
'''if''' "дядя" красный
parent = black
uncle = black
grandfather = red
t = grandfather
'''else'''
<font color=green>// случай, когда нет "дяди" </font>
'''if''' t {{---}} правый сын
t = parent
leftRotate(t)
parent = black
grandfather = red
rightRotate(grandfather)
'''else''' <font color=green>// "отец" {{---}} правый ребенок </font>
'''if''' есть "дядя"
'''if''' "дядя" красный
parent = black
uncle = black
grandfather = red
t = grandfather
'''else''' <font color=green>// нет "дяди" </font>
'''if''' t {{---}} левый ребенок
t = t.parent
rightRotate(t)
parent = black
grandfather = red
leftRotate(grandfather)
root = black <font color=green>// восстанавливаем свойство корня </font>
=== Удаление вершины ===
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращений.
'''Псевдокод:'''
'''func''' delete(key)
Node p = root
<font color=green>// находим узел с ключом key</font>
'''while''' p.key != key
'''if''' p.key < key
p = p.right
'''else'''
p = p.left
'''if''' у p нет детей
'''if''' p {{---}} корень
root = ''nil''
'''else'''
ссылку на p у "отца" меняем на ''nil''
'''return'''
Node y = ''nil''
Node q = ''nil''
'''if''' один ребенок
ссылку на у от "отца" меняем на ребенка y
'''else'''
<font color=green>// два ребенка</font>
y = вершина, со следующим значением ключа <font color=green>// у нее нет левого ребенка </font>
'''if''' y имеет правого ребенка
t.right.parent = y.parent
'''if''' y {{---}} корень
root = t.right
'''else'''
у родителя ссылку на y меняем на ссылку на первого ребенка y
'''if''' y != p
p.colour = y.colour
p.key = y.key
'''if''' y.colour == black
<font color=green>// при удалении черной вершины могла быть нарушена балансировка</font>
fixDeleting(q)
'''func''' fixDeleting(p: '''Node''')
<font color=green>// далее родственные связи относительно p</font>
'''while''' p {{---}} черный узел и не корень
'''if''' p {{---}} левый ребенок
'''if''' "брат" красный
brother = black
parent = red
leftRotate(parent)
'''if''' у "брата" черные дети <font color=green>// случай <tex>1:</tex> "брат" красный с черными детьми</font>
brother = red
'''else'''
'''if''' правый ребенок "брата" черный <font color=green>// случай, рассматриваемый во втором подпункте:</font>
brother.left = black <font color=green>// "брат" красный с черными правым ребенком</font>
brother = red
rightRotate(brother)
brother.colour = parent.colour <font color=green>// случай, рассматриваемый в последнем подпункте</font>
parent = black
brother.right = black
leftRotate(parent)
p = root
'''else''' <font color=green>// p {{---}} правый ребенок</font>
<font color=green>// все случаи аналогичны тому, что рассмотрено выше</font>
'''if''' "брат" красный
brother = black
parent = red
rightRotate(p.parent)
'''if''' у "брата" черные дети
brother = red
'''else'''
'''if''' левый ребенок "брата" черный
brother.right = black
brother = red
leftRotate(brother);
brother = parent
parent = black
brother.left = black
rightRotate(p.parent)
p = root
p = black
root = black
=== Объединение красно-чёрных деревьев ===
Объединение двух красно-чёрных деревьев <tex>T_{1}</tex> и <tex>T_{2}</tex> по элементу <tex>x</tex> выполняется, когда <tex>key[T_{1}] \leqslant x</tex> и <tex>x \leqslant key[T_{2}]</tex>, где <tex>key[T]</tex> {{---}} максимальные ключи дерева <tex>T</tex>.
Найдём чёрные высоты деревьев. Предположим также, что <tex>hb[T_{1}] \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>.
Осталось восстановить свойства красно-черного дерева, чтобы у красной вершины не было красных детей. Делается аналогично алгоритму добавления вершины.
== Преимущества красно-чёрных деревьев ==
#При Самое главное преимущество красно-черных деревьев в том, что при вставке выполняется не более <tex>O(1)</tex> вращений.#Алгоритм вставки и удаления может быть написан в один проход сверху внизЭто важно, вместо алгоритманапример, который использует рекурсивный проход внизв алгоритме построения [[Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)|динамической выпуклой оболочки]]. Ещё важно, родительские указатели или явный стек для обеспечения возможности пройти назад вверх, чтобы провести перебалансировкучто примерно половина вставок и удалений произойдут задаром.
#Процедуру балансировки практически всегда можно выполнять параллельно с процедурами поиска, так как алгоритм поиска не зависит от атрибута цвета узлов.
#Сбалансированность этих деревьев хуже, чем у АВЛ, но работа по поддержанию сбалансированности в красно-чёрных деревьях обычно эффективнее. Для балансировки красно-чёрного дерева производится минимальная работа по сравнению с АВЛ-деревьями.
#Использует всего 1 бит дополнительной памяти для хранения цвета вершины. Но на самом деле в современных вычислительных системах память выделяется кратно байтам, поэтому это не является преимуществом относительно, например, АВЛ-дерева, которое хранит 2 бита. Однако есть реализации красно-чёрного дерева, которые хранят значение цвета в бите. Пример {{---}} Boost Multiindex. В этой реализации уменьшается потребление памяти красно-чёрным деревом, так как бит цвета хранится не в отдельной переменной, а в одном из указателей узла дерева.
Красно-чёрные деревья являются наиболее активно используемыми на практике самобалансирующимися деревьями поиска. В частности, ассоциативные контейнеры библиотеки STL(map, set, multiset, multimap) основаны на красно-чёрных деревьях.TreeMap в Java тоже реализован на основе красно-чёрных деревьев. == Связь с 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|]] === Корректность сопоставления деревьев === Сопоставив таким образом цвета узлам дерева, можно проверить, что полученное дерево удовлетворяет всем свойствам красно-черного дерева.{{Утверждение|statement=У красного узла родитель не может быть красного цвета.|proof=В узле 2-4 дерева содержится не более трех элементов, один из которых обязательно красится в черный при переходе к симметричному бинарному B-дереву. Тогда оставшиеся красные элементы, если они есть, подвешиваются к черному. Из этих элементов могут идти ребра в следующий узел 2-4 дерева. В этом узле обязательно есть черная вершина, в нее и направляется ребро. Оставшиеся элементы узла, если они есть, подвешиваются к черной вершине аналогично первому узлу. Таким образом, ребро из красной вершины никогда не попадает в красную, значит у красного элемента родитель не может быть красным.}}{{Утверждение|statement=Число черных узлов на любом пути от листа до вершины одинаково.|proof=В B-дереве глубина всех листьев одинакова, следовательно, одинаково и количество внутренних узлов на каждом пути. Мы сопоставляем чёрный цвет одному элементу внутреннего узла B-дерева. Значит, количество чёрных элементов на любом пути от листа до вершины одинаково.}}{{Утверждение|statement=Корень дерева {{---}} черный.|proof=Если в корне один элемент, то он {{---}} чёрный. Если же в корне несколько элементов, то заметим, что один элемент окрашен в чёрный цвет, остальные {{---}} в красный. Горизонтальные связи, соединяющие элементы внутри одного узнала, ведут из чёрного элемента в красный, следовательно, красные элементы будут подвешены к чёрному. Он и выбирается в качестве корня симметричного бинарного B-дерева.}} === Сопоставление операций в деревьях === Все операции, совершаемые в B-дереве, сопоставляются операциям в красно-черном дереве. Для этого достаточно доказать, что изменение узла в B-дереве соответствует повороту в красно-черном дереве.{{Утверждение|statement=Изменение узла в B-дереве соответствует повороту в красно-черном дереве.|proof=В 2-4 дереве изменение узла необходимо при добавлении к нему элемента. Рассмотрим, как будет меняться структура B-дерева и, соответственно, красно-черного дерева при добавлении элемента: * Если в узле содержался один элемент, то происходит добавление второго элемента, соответствующее добавлению красного элемента в красно-черное дерево. * Если в узле содержалось два элемента, то происходит добавление третьего элемента, что соответствует повороту и перекрашиванию вершин в красно-черном дереве. * Если в узле содержалось три элемента, то один из элементов узла становится самостоятельным узлом, к которому подвешиваются узел из пары элементов и узел из одного элемента. Эта операция соответствует перекрашиванию яруса красно-черного дерева из красного в черный цвет. [[Файл:Rbtree2.png|1000px|]] При удалении элемента из узла B-дерева совершаются аналогичные процессы поворота и окраски вершин в красно-черном дереве, только в обратном направлении. Так как все операции в 2-4 дереве происходят за счет изменения узлов, то они эквивалентны соответствующим операциям в красно-черном дереве.}} {{Теорема|statement=Приведенное выше сопоставление B-деревьев и красно-черных деревьев является изоморфизмом.|proof=Доказательство следует непосредственно из приведенных выше утверждений.}}
==См. также==
* [[АВЛ-дерево|АВЛ-дерево]]
* [[2-3 дерево|2-3 дерево]]
== Примечания ==
<references/>
==Источники информации==
* [http://nord.org.ua/static/course/algo_2009/lecture10.pdf Курс kiev-clrs {{---}} Лекция 10. Красно-чёрные деревья]
* [http://rain.ifmo.ru/cat/view.php/vis/trees/red-black-2002 Визуализатор]
* [http://rflinux.blogspot.ru/2011/10/red-black-trees.html Абстрактные типы данных {{---}} Красно-чёрные деревья (Red black trees)]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]
