Красное-чёрное дерево — различия между версиями

Материал из Public ATP Wiki
Перейти к: навигация, поиск
(Создал определение)
 
 
(не показаны 23 промежуточные версии этого же участника)
Строка 1: Строка 1:
= Красно-чёрное дерево =
+
[[File:rbtee_example.png|thumb|top|right|upright=1.2|Пример КЧД]]
''Красно-чёрное дерево''(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:
+
 
* Каждая вершина имеет цвет: красный или чёрный
+
'''Красно-чёрное дерево'''(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:
* Корень дерева - чёрный
+
 
* У каждой нелистовой вершины ровно два ребёнка
+
# Каждая вершина имеет цвет: красный или чёрный
* Все листья чёрные и фиктивные
+
# Корень дерева - чёрный
* У красной вершины оба ребёнка чёрные
+
# У каждой нелистовой вершины ровно два ребёнка
* Чёрная высота каждой вершины определена корректно
+
# Все листья чёрные и фиктивные
 +
# У красной вершины оба ребёнка чёрные
 +
# Чёрная высота каждой вершины определена корректно
 +
 
 +
== Чёрная высота ==
 +
На пути от любой вершины красно-чёрного дерева до её потомка-листа одинаковое количество чёрных вершин.
 +
 
 +
'''Чёрная высота вершины $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]]
 +
 
 +
Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется. Остальные свойства КЧД так же выполняются. В частности, корень поддерева $a$ должен быть чёрным. Теперь дерево сбалансированно.

Текущая версия на 18:46, 15 апреля 2020

Пример КЧД

Красно-чёрное дерево(англ. red-black tree) - самобалансирующееся бинарное дерево поиска (англ. Binary Search Tree, BST) со следующими свойствами:

  1. Каждая вершина имеет цвет: красный или чёрный
  2. Корень дерева - чёрный
  3. У каждой нелистовой вершины ровно два ребёнка
  4. Все листья чёрные и фиктивные
  5. У красной вершины оба ребёнка чёрные
  6. Чёрная высота каждой вершины определена корректно

Чёрная высота

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

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

Лемма 1
В поддереве вершины $x$ как минимум $2^{bh(x)} - 1$ вершин.
Доказательство

Пусть $c(x)$ - количество вершин в поддереве x.

Индукция по $h(x)$:

  • База: $h(x) = 0$ - очевидное отверждение
  • Переход:
    К потомкам $x$ - $y$ и $z$ применимо предположение индукции.
    Заметим также, что $bh(y) \geq bh(x) - 1$ и $bh(z) \geq bh(x) - 1$.
    Тогда $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$

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

Лемма 2
Если $T$ - красно-чёрное дерево, то $h(T) \leq log_2 (n + 1)$.
Доказательство

Из свойств дерева, на любом пути из вершины $x$ в лист красных вершин не больше чёрных.
Отсюда $h(x) \leq 2 bh(x)$. Тогда по Л1 $n \geq 2^{bh(root)} - 1$.
Отсюда $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

Первый случай

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

Случай 2

Подслучай 1

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

Рассмотрим два подслучая:

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

Легко заметить, что при таких действиях количество чёрных вершин на любом пути, проходящем через это поддерево не меняется. Остальные свойства КЧД так же выполняются. В частности, корень поддерева $a$ должен быть чёрным. Теперь дерево сбалансированно.