Просмотр исходного текста страницы Красное-чёрное дерево

[[File:rbtee_example.png|thumb|top|right|Пример КЧД]]
'''Красно-чёрное дерево'''(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:

# Каждая вершина имеет цвет: красный или чёрный
# Корень дерева - чёрный
# У каждой нелистовой вершины ровно два ребёнка
# Все листья чёрные и фиктивные
# У красной вершины оба ребёнка чёрные
# Чёрная высота каждой вершины определена корректно

<br>

== Чёрная высота ==
На пути от любой вершины красно-чёрного дерева до её потомка-листа одинаковое количество чёрных вершин.

'''Чёрная высота вершины $x$''' (Обозначаем $bh(x)$) - количество чёрных вершин на пути от $x$ до любого её потомка-листа, не считая самого $x$.

{{Template:Lemma
|What = Лемма 1
|Statement = В поддереве вершины $x$ как минимум $2^{bh(x)} - 1$ вершин.
|Proof = 
Пусть $c(x)$ - количество вершин в поддереве x.

Индукция по $h(x)$:
* База: $h(x) = 0$ - очевидное отверждение
* Переход: <br/> К потомкам $x$ - $y$ и $z$ применимо предположение индукции. <br/> Заметим также, что $bh(y) \geq bh(x) - 1$ и $bh(z) \geq bh(x) - 1$. <br/> Тогда $c(x) \geq 1 + 2^{bh(y)} - 1 + 2^{bh(z)} - 1 \geq 2^{bh(x) - 1} + 2^{bh(x) - 1} - 1 \eq 2^{bh(x)} - 1$
}}

== Высота красно-чёрного дерева ==

{{Template:Lemma
|What = Лемма 2
|Statement = Если $T$ - красно-чёрное дерево, то $h(T) \leq log_2 (n + 1)$.
|Proof = Из свойств дерева, на любом пути из вершины $x$ в лист красных вершин не больше чёрных. <br/> Отсюда $h(x) \leq 2 bh(x)$. Тогда по Л1 $n \geq 2^{bh(root)} - 1$. <br/> Отсюда $log_2 (n + 1) \geq bh(root) \geq 0.5 \cdot h(root) \rightarrow h(root) \leq 2 \cdot log_2 (n + 1)$
}}

== Вставка ==

Рассмотрим, как поддерживать свойства красно-чёрного дереве при операции ''insert''.

Производим вставку элемента в дерево как в любом BST и сразу красим его в красный цвет.

=== Тривиальные случаи ===

* $x$ - новый корень КЧД. Тогда красим его в чёрный цвет для поддрежания 2 свойства КЧД.
* Наш родитель $p$ - чёрный. Тогда вставка красного листа не нарушает свойств КЧД, а значит ничего делать не нужно.

Теперь если $p$ родитель $x$ оказался красным, то его родитель $gp$ обязан быть чёрным. Посмотрим на "дядюшку" $x$ - $u$.

=== Случай 1 ===

[[File:rbtee_insert_case1.png|thumb|top|right|Первый случай]]

$u$ - красный (не фиктивный). Тогда красим $u$ и $p$ в чёрный, а $gp$ - в красный. После этого количество чёрных вершин на любом пути, проходящем через $gp$ не изменяется. Но могло нарушиться свойство 4, если родитель $gp$ оказался красным, или свойство 2, если $gp$ оказался чёрным. В первом случае конфликт был поднят выше по дереву - его можно исправить рекурсивно. Во втором случае мы просто красим $gp$ в чёрный цвет.

=== Случай 2 ===

[[File:rbtee_insert_case2_subcase1.png|thumb|top|left|Подслучай 1]]

$u$ - чёрный (возможно фиктивный). Тогда далее будем считать, что $p$ - левый потомок $gp$. В ином случае дальнейшие действия следует отзеркалить.

Рассмотрим два подслучая:
* $x$ - правый потомок $p$. В таком случае совершаем левое вращение с центром в $p$ и сводим этот случай к следующему ($p$ - новый $x$).
* $x$ - левый потомок $p$. В этом случае совершаем правое вращение с центром в вершине $gp$, предварительно покрасив $gp$ в красный, а $p$ - в чёрный.

[[File:rbtee_insert_case2_subcase2.png|thumb|top|left|Подслучай 2]]

Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется. Каких-либо конфликтов так же не возникает.