Изменения
→Высота красно-черного дерева
# Все простые пути из любого узла x до листьев содержат одинаковое количество чёрных узлов
# Чёрный узел может иметь чёрного родителя
[[Файл:konspv2.jpg|350px|thumb|Ослабленное красно-чёрное дерево.]]
Определим ослабленное красно-чёрное дерево как красно-чёрное дерево, корень которого может быть как чёрным, так и красным. Останется ли оно после этого Докажем, что при таком условии не будут выполняться и некоторые другие свойства красно-черным? черных деревьев. При добавлении вершины около корня могут возникнуть повороты, и корневая вершина перейдет в какое-то поддерево. Из-за этого может возникнуть ситуация, в которой подряд будут идти две красные вершины. То же самое может произойти из-за перекрашиваний возле корня. Если мы продолжим вставлять элементы подобным образом, свойства дерева перестанут выполняться , и оно перестанет быть сбалансированным. Таким образом, время выполнения некоторых операций ухудшится. Перед тем, как перейдем к примеру, договоримся, что мы разрешим в ослабленном красно-чёрном дереве при первом добавлении вершин (обеих, правой и левой) к красному корню делать их черными (немного модифицированный алгоритм вставки). Предыдущее условие можно заменить на другое, позволяющее корню иметь красных детей. Рассмотрим пример справа. Получим такое дерево добавляя ключи в следующем порядке: <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>-тым свойством говорит о том, что корень дерева должен быть черным, а значит определения можно считать эквивалентными.
== Высота красно-черного дерева ==
{{Лемма
|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>
Узел, с которым мы работаем, на картинках имеет имя <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 = 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>
=== Удаление вершины ===
Проверим балансировку дерева. Так как при удалении красной вершины свойства дерева не нарушаются, то восстановление балансировки потребуется только при удалении чёрной. Рассмотрим ребёнка удалённой вершины.
1. Если брат этого ребёнка красный, то делаем вращение вокруг ребра между отцом и братом, тогда брат становится родителем отца. Красим его в чёрный, а отца {{- --}} в красный цвет, сохраняя таким образом черную высоту дерева. Хотя все пути по-прежнему содержат одинаковое количество чёрных узлов, сейчас <tex>x</tex> имеет чёрного брата и красного отца. Таким образом, мы можем перейти к следующему шагу.
[[Файл:Untitled-3.png|400px|]]
2. Если брат текущей вершины был чёрным, то получаем три случая:
* Оба ребёнка у брата чёрные. Красим брата в красный цвет и рассматриваем далее отца вершины. Делаем его черным, это не повлияет на количество чёрных узлов на путях, проходящих через <tex>b</tex>, но добавит один к числу чёрных узлов на путях, проходящих через <tex>x</tex>, восстанавливая тем самым влиянние удаленного чёрного узла. Таким образом, после удаления вершины черная глубина от отца этой вершины до всех листьев в этом поддереве будет одинаковой.
[[Файл:Untitled-4.png|400px|]]
* Если у брата правый ребёнок чёрный, а левый красный, то перекрашиваем брата и его левого сына и делаем вращение. Все пути по-прежнему содержат одинаковое количество чёрных узлов, но теперь у <tex>x</tex> есть чёрный брат с красным правым потомком, и мы переходим к следующему случаю. Ни <tex>x</tex>, ни его отец не влияют на эту трансформацию.
[[Файл:Untitled-5.png|400px|]]
* Если у брата правый ребёнок красный, то перекрашиваем брата в цвет отца, его ребёнка и отца - в чёрный, делаем вращение . Поддерево по-прежнему имеет тот же цвет корня, поэтому свойство <tex>3</tex> и выходим <tex>4</tex> не нарушаются. Но у <tex>x</tex> теперь появился дополнительный чёрный предок: либо <tex>a</tex> стал чёрным, или он и был чёрным и <tex>b</tex> был добавлен в качестве чёрного дедушки. Таким образом, проходящие через <tex>x</tex> пути проходят через один дополнительный чёрный узел. Выходим из алгоритма.
[[Файл:Untitled-6.png|400px|]]
Продолжаем тот же алгоритм, пока текущая вершина чёрная и мы не дошли до корня дерева.
Из рассмотренных случаев ясно, что при удалении выполняется не более трёх вращений.
'''Псевдокод:'''
'''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>hb[T_{1}] \leqslant hb[T_{2}]</tex>, то слияние происходит аналогично, только теперь мы ищем в дереве <tex>T_{2}</tex> среди чёрных вершин, имеющих чёрную высоту <tex>hb[T_{1}]</tex>, вершину <tex>y</tex> с наименьшим ключом.
Так как общее время выполнения каждой из операций порядка высоты дерева ,то все они выполняются за <tex>O(\log{n})</tex>.
== Преимущества красно-чёрных деревьев ==
==См. также==
* [[АВЛ-дерево|АВЛ-дерево]]
* [[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)]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Деревья поиска]]