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

== TL;DR ==

Красно-чёрное дерево — это двоичное дерево поиска, в котором каждому узлу приписан цвет (красный или чёрный), а на раскраску наложены правила, удерживающие высоту дерева на уровне <math>O(\log n)</math>. В отличие от строго сбалансированных [[авл-дерево|АВЛ-деревьев]], где разность высот поддеревьев не превышает единицы, здесь допускается «перекос» до двукратного, зато вставка и удаление требуют заметно меньше поворотов. Именно красно-чёрное дерево лежит в основе <code>std::map</code> и <code>std::set</code> в C++, <code>TreeMap</code> в Java и <code>SortedDictionary</code> в .NET. Все операции поиска, вставки и удаления выполняются за <math>O(\log n)</math> в худшем случае, а не только в среднем.

{| class="wikitable"
|-
! Свойство !! Значение
|-
| Класс || Двоичное дерево поиска (binary search tree, BST) с балансировкой
|-
| Изобретение || Байер, 1972 (симметричные двоичные B-деревья); Гибас и Седжвик, 1978 (термин «красно-чёрное дерево») [2][3]
|-
| Поиск (худший / средний) || <math>O(\log n)</math> / <math>O(\log n)</math>
|-
| Вставка (худший / средний) || <math>O(\log n)</math> / <math>O(\log n)</math>; не более 2 поворотов
|-
| Удаление (худший) || <math>O(\log n)</math>; не более 3 поворотов
|-
| Обход в порядке возрастания || <math>O(n)</math>
|-
| Память || <math>O(n)</math>; 1 бит цвета сверх обычного узла BST (ключ, указатели на родителя и двух детей)
|-
| Упорядоченность || Да; итерация даёт ключи по возрастанию
|-
| Детерминированность || Да; рандомизация не требуется
|-
| Стабильность || Не применимо (нет понятия стабильности для дерева)
|-
| Альтернативы || АВЛ-дерево, B-дерево / B⁺-дерево, splay-дерево, декартово дерево (treap), хеш-таблица
|-
| Где встречается || <code>std::map</code> / <code>std::set</code> (C++), <code>java.util.TreeMap</code>, .NET <code>SortedDictionary</code>, ядро Linux (планировщик, таймеры высокого разрешения, <code>epoll</code>)
|}

== Определения ==

'''Красно-чёрное дерево (red-black tree, RB-дерево)''' — двоичное дерево поиска, каждый узел которого окрашен в красный или чёрный цвет и удовлетворяет пяти свойствам (RB-свойствам):

# Каждый узел либо красный, либо чёрный.
# Корень дерева чёрный.
# Каждый лист (<code>NIL</code>, внешний узел-часовой) чёрный.
# Оба ребёнка красного узла чёрные (эквивалентно: нет двух красных узлов, соединённых ребром).
# Для любого узла все простые пути от него вниз до листьев содержат одинаковое число чёрных узлов.

'''Чёрная высота (black-height)''' узла <math>x</math>, обозначается <math>bh(x)</math> — число чёрных узлов на любом пути от <math>x</math> (не включая сам <math>x</math>) вниз до листа включительно; лист <code>NIL</code> чёрный и учитывается. По свойству 5 это число не зависит от выбора пути, поэтому определение корректно. Число <math>bh(T) = bh(root)</math>, где <math>root</math> — корень дерева.

'''Высота дерева (height)''' <math>h</math> — число рёбер на самом длинном пути от корня до листа.

'''Внутренний узел''' — узел, хранящий ключ. '''Внешний узел / <code>NIL</code>-лист''' — специальный узел-часовой (sentinel), обозначающий отсутствие ребёнка. В реализации обычно используется один общий объект <code>T.nil</code>, на который указывают все «пустые» ссылки; его цвет всегда чёрный.

'''Обозначения.''' <math>n</math> — число внутренних узлов (хранимых ключей). <math>\log</math> всюду означает логарифм по основанию 2. Ключи хранятся в узлах, и для любого узла <math>x</math> выполнено <math>\text{key}[\text{left}[x]] < \text{key}[x] < \text{key}[\text{right}[x]]</math> (в смысле порядка натуральных чисел/строк; при возможности дубликатов вводят счётчик или договорённость о стороне).

== Мотивация и интуиция ==

Обычное [[двоичное-дерево-поиска|BST]] выполняет поиск за время, пропорциональное высоте, и лишь при удачном порядке вставки высота близка к <math>\log n</math>. Если вставлять ключи по возрастанию (<math>1, 2, 3, \dots</math>), дерево вырождается в связный список высоты <math>n-1</math>, и поиск становится линейным: для <math>n = 10^6</math> это до миллиона сравнений вместо примерно 20. Хуже того, противник, знающий алгоритм, может подобрать вход, гарантированно приводящий к вырождению.

Наивное лечение — поддерживать идеальную сбалансированность после каждой операции. Но полная перебалансировка стоит <math>O(n)</math>; АВЛ-дерево поддерживает разность высот <math>\le 1</math> ценой частых поворотов при удалении. Красно-чёрное дерево выбирает компромисс: оно допускает, что один путь может быть вдвое длиннее другого (чёрная высота та же, но между чёрными узлами «вставлены» красные), и благодаря этому при вставке нужно '''не более двух''' поворотов, а при удалении — '''не более трёх'''. Ключевая идея: вместо слежения за высотой поддеревьев следить за числом чёрных узлов на пути, а красные узлы использовать как «бесплатные» вставки, не меняющие чёрную высоту.

== Устройство ==

Красно-чёрное дерево — надстройка над обычным BST. Каждый узел хранит ключ, ссылки на левого и правого ребёнка и на родителя (ссылка на родителя нужна для подъёма при балансировке) и один бит цвета. Строение показано на рис. 1. Все внешние ссылки ведут на общий чёрный часовой <code>T.nil</code>.

Свойства 4 и 5 — главные. Запрет двух красных подряд означает, что на любом пути красные узлы не идут цепочкой; следовательно, '''не менее половины узлов любого пути — чёрные'''. Свойство 5 означает, что дерево «ровное по чёрным узлам», а красные лишь добавляют не более одного уровня между двумя чёрными. Отсюда и появляется оценка высоты <math>h \le 2\,bh</math> (см. рис. 5).

[[Файл:rbt-01-structure.svg|thumb|700px|Рис. 1. Красно-чёрное дерево с двумя красными узлами (15 и 50). Любой путь от корня до листа <code>NIL</code> содержит ровно два чёрных узла, не считая корня, поэтому <math>bh = 2</math>. Красные узлы не соседствуют друг с другом: у 15 и 50 родитель 30 — чёрный.]]

Эквивалентная точка зрения: красно-чёрное дерево — это [[2-3-4-дерево|2-3-4-дерево]], записанное в виде BST (частный случай порядка 3 — [[2-3-дерево|2-3-дерево]]). Красный узел и его чёрный родитель изображают один узел 2-3-4-дерева, хранящий два или три ключа. Это соответствие объясняет, почему операции столь локальны [4].

== Операции и алгоритмы ==

=== Операция: поворот (rotate) ===

'''Идея.''' Поворот — локальная перестройка связей двух узлов, сохраняющая порядок ключей. Он либо поднимает узел (приводя дерево к балансу), либо опускает, за время <math>O(1)</math> и без изменения множества ключей.

'''Пошаговое описание (левый поворот вокруг <math>x</math>, рис. 2).'''

# Обозначить <math>y \leftarrow \text{right}[x]</math> (правый ребёнок <math>x</math>).
# Перевесить левое поддерево <math>y</math> (узел <math>b</math>) в правого ребёнка <math>x</math>.
# Поднять <math>y</math> на место <math>x</math>: переназначить ссылку родителя <math>x</math> на <math>y</math>.
# Сделать <math>x</math> левым ребёнком <math>y</math>.

'''Инвариант.''' До и после поворота для любого узла выполняется порядок <math>\text{left} < \text{node} < \text{right}</math>; множество ключей не меняется.

'''Псевдокод.'''

<syntaxhighlight lang="text">
Алгоритм Left-Rotate(T, x)
Вход:  T — дерево; x — узел, у которого right[x] ≠ T.nil
Выход: поддерево с корнем x перестроено; порядок ключей сохранён
Инвариант: для любого узла left < node < right (BST-свойство)

1  y ← right[x]
2  right[x] ← left[y]
3  if left[y] ≠ T.nil
4      parent[left[y]] ← x
5  parent[y] ← parent[x]
6  if parent[x] = T.nil
7      root[T] ← y
8  else if x = left[parent[x]]
9      left[parent[x]] ← y
10 else
11     right[parent[x]] ← y
12 left[y] ← x
13 parent[x] ← y

Сложность: O(1) времени, O(1) дополнительной памяти.
Корректность: единственное изменяемое отношение — «кто чей ребёнок».
После строк 2–4 узел b подвешен вправо к x, после 12–13 y становится
родителем x; порядок a < x < b < y < c сохраняется.
</syntaxhighlight>

Правый поворот — зеркальная операция: <code>y ← left[x]</code>, <code>left[x] ← right[y]</code> и так далее.

[[Файл:rbt-02-rotations.svg|thumb|700px|Рис. 2. Левый поворот вокруг <math>x</math>: узел <math>y</math> поднимается, <math>x</math> опускается, среднее поддерево <math>b</math> перевешивается к <math>x</math>. Порядок <math>a < x < b < y < c</math> сохраняется.]]

=== Операция: вставка (insert) ===

'''Идея.''' Сначала вставить узел так же, как в обычное BST, и окрасить его в красный: красный узел не меняет чёрную высоту, поэтому нарушено может быть только свойство 4 (два красных подряд). Затем «починить» нарушение подъёмом вверх.

'''Пошаговое описание.'''

# Отыскать место вставки спуском от корня; новый узел <math>z</math> получает ключ и ссылки на <code>T.nil</code>.
# Окрасить <math>z</math> в красный, добавить как лист (родитель <math>y</math>), увеличить счётчик.
# Пока родитель <math>z</math> красный, выполнять балансировку (см. три случая).
# В конце окрасить корень в чёрный.

'''Инвариант.''' Перед каждой итерацией подъёма единственное возможное нарушение RB-свойств — это красный родитель у красного узла <math>z</math>; все чёрные высоты и остальные свойства сохранены.

'''Псевдокод.'''

<syntaxhighlight lang="text">
Алгоритм RB-Insert(T, z)
Вход:  T — дерево; z — новый узел с key[z], left[z] = right[z] = T.nil
Выход: T содержит z; RB-свойства восстановлены
Инвариант: нарушено не более одного RB-свойства — «красный родитель у z»

1  y ← T.nil
2  x ← root[T]
3  while x ≠ T.nil
4      y ← x
5      if key[z] < key[x]
6          x ← left[x]
7      else
8          x ← right[x]
9  parent[z] ← y
10 if y = T.nil
11     root[T] ← z
12 else if key[z] < key[y]
13     left[y] ← z
14 else
15     right[y] ← z
16 color[z] ← RED
17 RB-Insert-Fixup(T, z)

Алгоритм RB-Insert-Fixup(T, z)
18 while color[parent[z]] = RED
19     if parent[z] = left[parent[parent[z]]]
20         u ← right[parent[parent[z]]]          # дядя z
21         if color[u] = RED                      # случай 1
22             color[parent[z]] ← BLACK
23             color[u] ← BLACK
24             color[parent[parent[z]]] ← RED
25             z ← parent[parent[z]]
26         else
27             if z = right[parent[z]]            # случай 2
28                 z ← parent[z]
29                 Left-Rotate(T, z)
30             color[parent[z]] ← BLACK           # случай 3
31             color[parent[parent[z]]] ← RED
32             Right-Rotate(T, parent[parent[z]])
33     else                                       # зеркально: p — правый ребёнок g
34         u ← left[parent[parent[z]]]
35         if color[u] = RED
36             color[parent[z]] ← BLACK
37             color[u] ← BLACK
38             color[parent[parent[z]]] ← RED
39             z ← parent[parent[z]]
40         else
41             if z = left[parent[z]]
42                 z ← parent[z]
43                 Right-Rotate(T, z)
44             color[parent[z]] ← BLACK
45             color[parent[parent[z]]] ← RED
46             Left-Rotate(T, parent[parent[z]])
47 color[root[T]] ← BLACK

Сложность: O(log n) времени, O(1) памяти. Поворотов не более двух.
Корректность: случаи 1–3 исчерпывают ситуации; случай 1 поднимает нарушение
на два уровня вверх, случаи 2–3 устраняют его окончательно.
</syntaxhighlight>

'''Разбор трёх случаев''' (для <math>p</math> — левый ребёнок деда <math>g</math>, рис. 3):

# '''Дядя <math>u</math> красный.''' Перекрашиваем <math>p</math> и <math>u</math> в чёрный, <math>g</math> — в красный, а <math>z</math> переносим в <math>g</math>: нарушение «переехало» на два уровня выше. Чёрная высота поддерева не изменилась.
# '''Дядя чёрный, <math>z</math> — правый ребёнок <math>p</math>.''' Левый поворот вокруг <math>p</math> превращает конфигурацию в случай 3, меняя роли <math>z</math> и <math>p</math>. Корректность ещё не восстановлена.
# '''Дядя чёрный, <math>z</math> — левый ребёнок <math>p</math>.''' Красим <math>p</math> в чёрный, <math>g</math> в красный и делаем правый поворот вокруг <math>g</math>. Нарушение устранено, дальше подниматься не нужно.

Случай зеркалится, когда <math>p</math> — правый ребёнок <math>g</math>.

[[Файл:rbt-03-insert-cases.svg|thumb|700px|Рис. 3. Три случая балансировки после вставки. Случай 1 (дядя красный) — только перекраска; случай 2 превращается в случай 3 одним поворотом; случай 3 завершает балансировку поворотом вокруг деда.]]

'''Крайние случаи.''' Вставка в пустое дерево (строки 10–11): <math>z</math> становится корнем и в строке 47 перекрашивается в чёрный. Вставка под чёрного родителя: цикл не выполняется вовсе. Вставка дубликата: либо игнорируется, либо поддерживается счётчик — здесь дубликаты отклоняются.

=== Операция: удаление (delete) ===

'''Идея.''' Сначала удалить узел по правилам BST (при двух детях — заменить ключом преемника), затем восстановить чёрную высоту. Нарушение возникает '''только если удалённый (или перемещённый) узел был чёрным''': тогда на его месте образуется «двойная чернота» — поддерево, которому не хватает одного чёрного узла.

'''Пошаговое описание.'''

# Найти узел <math>z</math> с данным ключом.
# Если у <math>z</math> меньше двух детей, заменить его ребёнком <math>x</math> (<code>transplant</code>); запомнить цвет удаляемого <math>y \leftarrow z</math>.
# Если у <math>z</math> два ребёнка, найти минимум <math>y</math> в правом поддереве; запомнить <math>y</math> и его цвет; перевесить <math>y</math> на место <math>z</math> (структурно), при этом <math>x \leftarrow \text{right}[y]</math>.
# Если удалённый цвет был чёрным — вызвать <code>RB-Delete-Fixup(T, x)</code>.
# Освободить узел, уменьшить счётчик.

'''Инвариант.''' Перед каждой итерацией <code>RB-Delete-Fixup</code> узел <math>x</math> «несёт» дополнительный чёрный цвет: поддерево с корнем <math>x</math> имеет чёрную высоту на единицу меньше требуемой, а все прочие RB-свойства выполнены.

'''Псевдокод.'''

<syntaxhighlight lang="text">
Алгоритм RB-Delete(T, z)
Вход:  T — дерево; z — удаляемый узел
Выход: z удалён; RB-свойства восстановлены
Инвариант: нарушена чёрная высота в точке x (двойная чернота), если y был чёрным

1  y ← z
2  y-original-color ← color[y]
3  if left[z] = T.nil
4      x ← right[z]
5      RB-Transplant(T, z, right[z])
6  else if right[z] = T.nil
7      x ← left[z]
8      RB-Transplant(T, z, left[z])
9  else
10     y ← Tree-Minimum(right[z])
11     y-original-color ← color[y]
12     x ← right[y]
13     if parent[y] = z
14         parent[x] ← y
15     else
16         RB-Transplant(T, y, right[y])
17         right[y] ← right[z]
18         parent[right[y]] ← y
19     RB-Transplant(T, z, y)
20     left[y] ← left[z]
21     parent[left[y]] ← y
22     color[y] ← color[z]
23 if y-original-color = BLACK
24     RB-Delete-Fixup(T, x)

Алгоритм RB-Transplant(T, u, v)
25 if parent[u] = T.nil
26     root[T] ← v
27 else if u = left[parent[u]]
28     left[parent[u]] ← v
29 else
30     right[parent[u]] ← v
31 parent[v] ← parent[u]

Сложность: O(log n) времени, O(1) памяти. Поворотов не более трёх.
</syntaxhighlight>

<code>RB-Delete-Fixup</code> разбирает четыре случая, различаемых по цвету брата <math>w</math> узла <math>x</math> и цветам его детей (рис. 4):

<syntaxhighlight lang="text">
Алгоритм RB-Delete-Fixup(T, x)
Инвариант: узел x несёт лишний чёрный: поддерево с корнем x имеет чёрную высоту
           на единицу меньше требуемой; если x красный, лишний чёрный
           поглощается сразу окраской в чёрный

1  while x ≠ root[T] and color[x] = BLACK
2      if x = left[parent[x]]
3          w ← right[parent[x]]                     # брат
4          if color[w] = RED                        # случай 1
5              color[w] ← BLACK
6              color[parent[x]] ← RED
7              Left-Rotate(T, parent[x])
8              w ← right[parent[x]]
9          if color[left[w]] = BLACK and color[right[w]] = BLACK
10             color[w] ← RED                       # случай 2
11             x ← parent[x]
12         else
13             if color[right[w]] = BLACK
14                 color[left[w]] ← BLACK           # случай 3
15                 color[w] ← RED
16                 Right-Rotate(T, w)
17                 w ← right[parent[x]]
18             color[w] ← color[parent[x]]          # случай 4
19             color[parent[x]] ← BLACK
20             color[right[w]] ← BLACK
21             Left-Rotate(T, parent[x])
22             x ← root[T]
23     else                                          # зеркально: x — правый ребёнок
24         w ← left[parent[x]]
25         if color[w] = RED
26             color[w] ← BLACK
27             color[parent[x]] ← RED
28             Right-Rotate(T, parent[x])
29             w ← left[parent[x]]
30         if color[right[w]] = BLACK and color[left[w]] = BLACK
31             color[w] ← RED
32             x ← parent[x]
33         else
34             if color[left[w]] = BLACK
35                 color[right[w]] ← BLACK
36                 color[w] ← RED
37                 Left-Rotate(T, w)
38                 w ← left[parent[x]]
39             color[w] ← color[parent[x]]
40             color[parent[x]] ← BLACK
41             color[left[w]] ← BLACK
42             Right-Rotate(T, parent[x])
43             x ← root[T]
44 color[x] ← BLACK

Сложность: O(log n); поворотов не более трёх (по одному в случаях 1, 3, 4).
Корректность: случай 2 поднимает двойную черноту вверх; случаи 3–4 устраняют её
на месте; случай 1 лишь приводит к случаям 2–4.
</syntaxhighlight>

[[Файл:rbt-04-delete-cases.svg|thumb|700px|Рис. 4. Четыре случая <code>Delete-Fixup</code> для <math>x</math> — левого ребёнка. Пунктир и «●●» обозначают двойную черноту. Случай 1 (брат красный) — поворот; случай 2 (оба ребёнка брата чёрные) — перекраска и подъём; случай 3 (левый ребёнок брата красный) — подготовительный поворот; случай 4 (правый ребёнок красный) — завершающий поворот.]]

'''Разбор на примере.''' Возьмём дерево после трассировки вставок — корень 38 чёрный, слева 19 красный с детьми 12 (чёрный; его левый ребёнок 8 красный) и 31 (чёрный), справа 41 чёрный — и удалим узел с ключом 31, чёрный лист.

# <math>y = 31</math>, <math>x = \text{T.nil}</math>, исходный цвет <math>y</math> — чёрный; <code>RB-Transplant(31, T.nil)</code> подвешивает <code>NIL</code> на место 31.
# <code>Delete-Fixup(x = nil)</code>: <math>x</math> — правый ребёнок 19, брат <math>w = 12</math> чёрный. У <math>w</math> левый ребёнок 8 красный, правый <code>nil</code> чёрный, поэтому зеркальный случай 3 (подготовительный поворот) не нужен — сразу случай 4.
# Случай 4: <math>w</math> получает цвет родителя (красный), 19 → чёрный, 8 → чёрный, правый поворот вокруг 19.
# Итог: корень 38 чёрный; слева 12 красный с детьми 8 (чёрный) и 19 (чёрный); справа 41 чёрный. Проверка: все пути от корня до <code>nil</code> дают чёрную высоту 2.

Здесь сработал именно случай 4 (зеркальный), потому что «дальний» ребёнок брата — красный: будь он чёрным, понадобился бы сначала случай 3 с поворотом, и только затем случай 4.

'''Крайние случаи.''' Удаление единственного узла: дерево становится пустым, <code>root[T] = T.nil</code>, <code>RB-Delete-Fixup</code> не нужен (условие <math>x \ne root</math>). Удаление чёрного листа — самый частый источник двойной черноты. У удаляемого узла два ребёнка: <math>y</math> — преемник, и важно запомнить именно его исходный цвет, а цвет самого <math>z</math> скопировать в <math>y</math>.

=== Операция: поиск (search) ===

'''Идея.''' Поиск игнорирует цвета: дерево остаётся корректным BST, поэтому спуск от корня по сравнениям находит ключ (или <code>NIL</code>).

'''Пошаговое описание.'''

# Начать с корня: <math>x \leftarrow root[T]</math>.
# Пока <math>x \ne \text{T.nil}</math> и <math>k \ne \text{key}[x]</math>, спускаться: если <math>k < \text{key}[x]</math> — влево, иначе вправо.
# Вернуть <math>x</math>: либо узел с ключом <math>k</math>, либо <code>T.nil</code>, если ключа в дереве нет.

<syntaxhighlight lang="text">
Алгоритм RB-Search(T, k)
Вход:  T — дерево; k — искомый ключ
Выход: узел с ключом k либо T.nil
Инвариант: если k присутствует, то он лежит в поддереве текущего узла x

1  x ← root[T]
2  while x ≠ T.nil and k ≠ key[x]
3      if k < key[x]
4          x ← left[x]
5      else
6          x ← right[x]
7  return x

Сложность: O(log n) времени (высота дерева), O(1) памяти.
Корректность: следует из BST-свойства, которое повороты и перекраски не нарушают.
</syntaxhighlight>

'''Разбор на примере.''' Ищем 31 в дереве после трассировки (корень 38, слева 19 с детьми 12 и 31, справа 41): <math>31 < 38</math> — шаг влево к 19; <math>31 > 19</math> — шаг вправо к 31; ключи совпали. Три сравнения при высоте дерева <math>h = 3</math> — не больше <math>h + 1</math>.

'''Крайние случаи.''' Пустое дерево: <math>root[T] = \text{T.nil}</math>, цикл не выполняется, возвращается <code>T.nil</code>. Ключа нет: спуск заканчивается на <code>T.nil</code> (например, поиск 20 в том же дереве даёт путь 38 → 19 → 31 → <code>nil</code>). Дубликаты в дерево не попадают — они отклоняются при вставке, поэтому поиск возвращает не более одного узла.

Дополнительно дерево поддерживает <code>minimum</code>/<code>maximum</code> (спуск влево/вправо до <code>NIL</code>), <code>predecessor</code>/<code>successor</code> и упорядоченный обход за <math>O(n)</math>; границы диапазона (<code>lower_bound</code>, <code>upper_bound</code>) — за <math>O(\log n)</math>.

=== Реализация структуры на C++ ===

Полная реализация на современном C++ (C++17). Используется один общий часовой <code>nil</code> (чёрный), ссылки на родителя, шаблонный ключ. Функция <code>validate()</code> проверяет все пять RB-свойств и корректность ссылок на родителей — её удобно вызывать в тестах после каждой операции.

<syntaxhighlight lang="cpp">
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>

enum class Color { RED, BLACK };

template <typename T>
class RBTree {
    struct Node {
        T key;
        Color color;
        Node *left, *right, *parent;
        explicit Node(const T& k, Color c = Color::RED)
            : key(k), color(c), left(nullptr), right(nullptr), parent(nullptr) {}
    };

    Node* nil_;
    Node* root_;
    std::size_t count_;

    void destroy(Node* x) {
        if (x == nil_) return;
        destroy(x->left);
        destroy(x->right);
        delete x;
    }

    void rotateLeft(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        if (y->left != nil_) y->left->parent = x;
        y->parent = x->parent;
        if (x->parent == nil_)          root_ = y;
        else if (x == x->parent->left)  x->parent->left = y;
        else                            x->parent->right = y;
        y->left = x;
        x->parent = y;
    }

    void rotateRight(Node* x) {
        Node* y = x->left;
        x->left = y->right;
        if (y->right != nil_) y->right->parent = x;
        y->parent = x->parent;
        if (x->parent == nil_)          root_ = y;
        else if (x == x->parent->right) x->parent->right = y;
        else                            x->parent->left = y;
        y->right = x;
        x->parent = y;
    }

    void insertFixup(Node* z) {
        while (z->parent->color == Color::RED) {
            if (z->parent == z->parent->parent->left) {
                Node* u = z->parent->parent->right;
                if (u->color == Color::RED) {            // случай 1
                    z->parent->color = Color::BLACK;
                    u->color = Color::BLACK;
                    z->parent->parent->color = Color::RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {         // случай 2
                        z = z->parent;
                        rotateLeft(z);
                    }
                    z->parent->color = Color::BLACK;      // случай 3
                    z->parent->parent->color = Color::RED;
                    rotateRight(z->parent->parent);
                }
            } else {
                Node* u = z->parent->parent->left;
                if (u->color == Color::RED) {
                    z->parent->color = Color::BLACK;
                    u->color = Color::BLACK;
                    z->parent->parent->color = Color::RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rotateRight(z);
                    }
                    z->parent->color = Color::BLACK;
                    z->parent->parent->color = Color::RED;
                    rotateLeft(z->parent->parent);
                }
            }
        }
        root_->color = Color::BLACK;
    }

    void transplant(Node* u, Node* v) {
        if (u->parent == nil_)         root_ = v;
        else if (u == u->parent->left) u->parent->left = v;
        else                           u->parent->right = v;
        v->parent = u->parent;
    }

    Node* minimum(Node* x) const {
        while (x->left != nil_) x = x->left;
        return x;
    }

    void deleteFixup(Node* x) {
        while (x != root_ && x->color == Color::BLACK) {
            if (x == x->parent->left) {
                Node* w = x->parent->right;
                if (w->color == Color::RED) {                       // случай 1
                    w->color = Color::BLACK;
                    x->parent->color = Color::RED;
                    rotateLeft(x->parent);
                    w = x->parent->right;
                }
                if (w->left->color == Color::BLACK && w->right->color == Color::BLACK) {
                    w->color = Color::RED;                          // случай 2
                    x = x->parent;
                } else {
                    if (w->right->color == Color::BLACK) {          // случай 3
                        w->left->color = Color::BLACK;
                        w->color = Color::RED;
                        rotateRight(w);
                        w = x->parent->right;
                    }
                    w->color = x->parent->color;                    // случай 4
                    x->parent->color = Color::BLACK;
                    w->right->color = Color::BLACK;
                    rotateLeft(x->parent);
                    x = root_;
                }
            } else {
                Node* w = x->parent->left;
                if (w->color == Color::RED) {
                    w->color = Color::BLACK;
                    x->parent->color = Color::RED;
                    rotateRight(x->parent);
                    w = x->parent->left;
                }
                if (w->right->color == Color::BLACK && w->left->color == Color::BLACK) {
                    w->color = Color::RED;
                    x = x->parent;
                } else {
                    if (w->left->color == Color::BLACK) {
                        w->right->color = Color::BLACK;
                        w->color = Color::RED;
                        rotateLeft(w);
                        w = x->parent->left;
                    }
                    w->color = x->parent->color;
                    x->parent->color = Color::BLACK;
                    w->left->color = Color::BLACK;
                    rotateRight(x->parent);
                    x = root_;
                }
            }
        }
        x->color = Color::BLACK;
    }

    bool check(Node* x, int blackHeight) const {
        if (x == nil_) return blackHeight == 0;
        if (x->color == Color::RED &&
            (x->left->color == Color::RED || x->right->color == Color::RED))
            return false;                                    // свойство 4
        if (x->left != nil_ && x->left->parent != x) return false;
        if (x->right != nil_ && x->right->parent != x) return false;
        int dec = (x->color == Color::BLACK) ? 1 : 0;
        return check(x->left, blackHeight - dec) &&          // свойство 5
               check(x->right, blackHeight - dec);
    }

public:
    RBTree() : count_(0) {
        nil_ = new Node(T{}, Color::BLACK);
        nil_->left = nil_->right = nil_->parent = nil_;
        root_ = nil_;
    }
    ~RBTree() { destroy(root_); delete nil_; }
    RBTree(const RBTree&) = delete;
    RBTree& operator=(const RBTree&) = delete;

    void insert(const T& key) {
        Node* z = new Node(key);
        Node* y = nil_;
        Node* x = root_;
        while (x != nil_) {
            y = x;
            if (key < x->key)      x = x->left;
            else if (x->key < key) x = x->right;
            else { delete z; return; }             // дубликат отклоняется
        }
        z->parent = y;
        if (y == nil_)             root_ = z;
        else if (key < y->key)     y->left = z;
        else                       y->right = z;
        z->left = z->right = nil_;
        ++count_;
        insertFixup(z);
    }

    bool contains(const T& key) const {
        Node* x = root_;
        while (x != nil_) {
            if (key < x->key)      x = x->left;
            else if (x->key < key) x = x->right;
            else                   return true;
        }
        return false;
    }

    void erase(const T& key) {
        Node* z = root_;
        while (z != nil_) {
            if (key < z->key)      z = z->left;
            else if (z->key < key) z = z->right;
            else break;
        }
        if (z == nil_) return;
        Node* y = z;
        Color yColor = y->color;
        Node* x;
        if (z->left == nil_) {
            x = z->right;
            transplant(z, z->right);
        } else if (z->right == nil_) {
            x = z->left;
            transplant(z, z->left);
        } else {
            y = minimum(z->right);
            yColor = y->color;
            x = y->right;
            if (y->parent == z) {
                x->parent = y;
            } else {
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }
        if (yColor == Color::BLACK) deleteFixup(x);
        delete z;
        --count_;
    }

    std::size_t size() const { return count_; }
    bool empty() const { return count_ == 0; }

    void inorder(Node* x, std::vector<T>& out) const {
        if (x == nil_) return;
        inorder(x->left, out);
        out.push_back(x->key);
        inorder(x->right, out);
    }
    std::vector<T> sorted() const {
        std::vector<T> out;
        inorder(root_, out);
        return out;
    }

    bool validate() const {
        if (root_ == nil_) return true;
        if (root_->color != Color::BLACK) return false;   // свойство 2
        if (nil_->color != Color::BLACK) return false;    // свойство 3
        int bh = 0;
        for (Node* x = root_; x != nil_; x = x->left)
            if (x->color == Color::BLACK) ++bh;
        return check(root_, bh);
    }
};

int main() {
    RBTree<int> t;
    std::vector<int> vals = {41, 38, 31, 12, 19, 8, 50, 25, 7, 3,
                             90, 64, 33, 17, 29, 1, 4, 5};
    for (int v : vals) t.insert(v);
    assert(t.validate() && "нарушение RB-свойств после вставки");
    for (int v : vals) assert(t.contains(v));
    for (int v : {38, 41, 1, 8, 33, 90}) t.erase(v);
    assert(t.validate() && "нарушение RB-свойств после удаления");
    assert(!t.contains(38) && !t.contains(90));

    std::vector<int> out = t.sorted();
    assert(std::is_sorted(out.begin(), out.end()));
    for (std::size_t i = 0; i < out.size(); ++i)
        std::cout << out[i] << (i + 1 == out.size() ? '\n' : ' ');
    return 0;
}
</syntaxhighlight>

'''Замечания по реализации.'''

* Часовой <code>nil_</code> — обычный узел с чёрным цветом; его поля <code>parent</code> могут временно меняться в <code>transplant</code>, но это безопасно, поскольку используются только внутри <code>deleteFixup</code>.
* Рекурсию в деструкторе можно заменить итеративным обходом, но высота <math>O(\log n)</math> делает рекурсию безопасной.
* Копирование отключено: корректная копия требует клонирования всех узлов и перенаправления <code>nil_</code>. При необходимости реализуйте правило трёх/пяти.
* Дубликаты отклоняются. Для мультимножества заведите в узле счётчик повторов и уменьшайте его при <code>erase</code>, удаляя узел лишь при обнулении счётчика.

== Сводная таблица сложности ==

{| class="wikitable"
|-
! Операция !! Худший случай !! Средний случай !! Амортизированная !! Память !! Поворотов
|-
| Поиск || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(1)</math> || 0
|-
| Вставка || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(1)</math> || ≤ 2
|-
| Удаление || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(1)</math> || ≤ 3
|-
| Минимум / максимум || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(1)</math> || 0
|-
| Обход по возрастанию || <math>O(n)</math> || <math>O(n)</math> || <math>O(n)</math> || <math>O(\log n)</math> со стеком; <math>O(1)</math> при обходе по ссылкам на родителя || 0
|-
| Память структуры || <math>O(n)</math> сверх данных || <math>O(n)</math> || <math>O(n)</math> || 1 бит цвета сверх обычного узла BST (ключ, указатели на родителя и двух детей) || 0
|}

'''Примечание.''' Все оценки '''худшего''' случая детерминированы: они не зависят от порядка вставок и не требуют рандомизации. Это принципиальное отличие от хеш-таблиц, где средний случай <math>O(1)</math>, а худший — <math>O(n)</math> (и возможны атаки на хеш-функцию). Оценки для вставки и удаления даны по числу '''перекрасок''': перекрасок в fixup может быть <math>O(\log n)</math>, поворотов — константно.

== Трассировка примера ==

Вставим в пустое дерево последовательность <math>41, 38, 31, 12, 19, 8</math> (классический пример из CLRS, гл. 13 [1]).

{| class="wikitable"
|-
! Шаг !! Вставили !! Состояние (в порядке возрастания) !! Действие <code>Insert-Fixup</code>
|-
| 0 || — || пусто || —
|-
| 1 || 41 || '''41''' || корень, сразу чёрный
|-
| 2 || 38 || 38(к), '''41''' || родитель чёрный — балансировка не нужна
|-
| 3 || 31 || 31(к), '''38''', 41(к) || случай 3: 38 → чёрный, 41 → красный, правый поворот вокруг 41
|-
| 4 || 12 || 12(к), '''31''', '''38''', '''41''' || случай 1: 31 и 41 → чёрные, 38 → красный; корень снова чёрный
|-
| 5 || 19 || 12(к), '''19''', 31(к), '''38''', '''41''' || случай 2 → случай 3: поворот вокруг 12, затем 19 → чёрный, 31 → красный, поворот вокруг 31
|-
| 6 || 8 || 8(к), '''12''', 19(к), '''31''', '''38''', '''41''' || случай 1: 12 и 31 → чёрные, 19 → красный; родитель 38 чёрный — стоп
|}

Жирным отмечены чёрные узлы, «(к)» — красные; столбец показывает состояние после шага.

Дерево после шести вставок: корень 38 чёрный, слева 19 (красный) с детьми 12 (чёрный, левый ребёнок 8 красный) и 31 (чёрный), справа 41 (чёрный). Проверка <code>validate()</code> на каждом шаге подтверждает все пять RB-свойств.

== Корректность и оценка сложности ==

'''Лемма 1 (нижняя оценка числа узлов).''' Для любого узла <math>x</math> поддерево с корнем в <math>x</math> содержит не менее <math>2^{bh(x)} - 1</math> внутренних узлов.

''Доказательство.'' Индукция по высоте <math>x</math>. База: если <math>x</math> — лист <code>NIL</code>, то <math>bh(x)=0</math> и <math>2^0-1=0</math> — верно. Шаг: пусть <math>x</math> внутренний. У каждого ребёнка <math>x</math> чёрная высота равна <math>bh(x)</math>, если ребёнок красный (он не добавляет чёрного узла), и <math>bh(x)-1</math>, если ребёнок чёрный. По индуктивному предположению каждое поддерево содержит не менее <math>2^{bh(x)-1}-1</math> узлов. Тогда

<math display="block">n(x) \ge \bigl(2^{bh(x)-1}-1\bigr) + \bigl(2^{bh(x)-1}-1\bigr) + 1 = 2^{bh(x)} - 1.</math>

<math>\blacksquare</math>

'''Лемма 2 (высота и чёрная высота).''' Дерево с <math>n</math> внутренними узлами имеет высоту <math>h \le 2\log_2(n+1)</math>.

''Доказательство.'' По свойству 4 никакие два красных узла не соседствуют, поэтому на любом пути от корня до листа не менее половины узлов чёрные. Следовательно, корень имеет чёрную высоту <math>bh \ge h/2</math>. По лемме 1:

<math display="block">n \ge 2^{bh} - 1 \ge 2^{h/2} - 1 \;\Rightarrow\; n + 1 \ge 2^{h/2} \;\Rightarrow\; h \le 2\log_2(n+1).</math>

<math>\blacksquare</math>

'''Вывод.''' Поиск, минимум/максимум, преемник/предшественник выполняют не более <math>h+1 = O(\log n)</math> шагов. Вставка и удаление в худшем случае проходят путь до корня, выполняя <math>O(1)</math> работы на уровне (перекраски и повороты); отсюда <math>O(\log n)</math> времени. Число поворотов константно (2 при вставке, 3 при удалении), а число перекрасок — <math>O(\log n)</math>. Ни один шаг не требует дополнительной памяти, кроме <math>O(1)</math>: спуск и подъём итеративны, стек не используется.

'''Инвариант-аргумент для вставки.''' Перед каждой итерацией <code>Insert-Fixup</code> поддерево с корнем <math>z</math> имеет ту же чёрную высоту, что и до вставки, а нарушено лишь свойство 4 (красный родитель). Случай 1 сохраняет чёрную высоту и поднимает нарушение на два уровня; случаи 2–3 восстанавливают свойство 4, не трогая чёрные высоты. Значит, по завершении цикла и после окраски корня в чёрный все пять свойств выполнены.

'''Инвариант-аргумент для удаления.''' Узел <math>x</math> несёт дополнительный чёрный цвет: чёрная высота его поддерева на единицу меньше, чем была бы по свойству 5. Случай 2 переносит избыточный чёрный вверх, случаи 3–4 поглощают его поворотом и перекраской (случай 4 возможен только при брате с красным правым ребёнком, что гарантирует корректность), случай 1 сводит задачу к случаям 2–4. Цикл заканчивается, когда избыточный чёрный доходит до красного узла (окрашивается в чёрный) или до корня.

[[Файл:rbt-05-height-bound.svg|thumb|700px|Рис. 5. Минимальное дерево с чёрной высотой <math>bh = 3</math> содержит <math>2^3-1 = 7</math> чёрных узлов. Красные узлы могут быть вставлены только между чёрными, поэтому <math>h \le 2\,bh</math>.]]

== Сравнение с альтернативами ==

{| class="wikitable"
|-
! Структура !! Поиск (худший) !! Вставка (худший) !! Удаление (худший) !! Память на узел !! Баланс !! Когда выбирать
|-
| Несбалансированное BST || <math>O(n)</math> || <math>O(n)</math> || <math>O(n)</math> || 3 указателя || нет || учебные задачи, статические данные
|-
| '''Красно-чёрное дерево''' || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(\log n)</math>, ≤ 3 поворотов || 3 указателя + 1 бит || высота <math>\le 2\log_2(n{+}1)</math> || универсальный выбор: <code>std::map</code>, <code>TreeMap</code>
|-
| АВЛ-дерево || <math>O(\log n)</math> || <math>O(\log n)</math> || <math>O(\log n)</math>, до <math>O(\log n)</math> поворотов || 3 указателя + баланс || разность высот <math>\le 1</math> || частые поиски, редкие записи
|-
| B-дерево / B⁺-дерево || <math>O(\log_t n)</math> || <math>O(\log_t n)</math> || <math>O(\log_t n)</math> || массив ключей в блоке || страницы по <math>t</math> ключей || диск, СУБД, файловые системы
|-
| Хеш-таблица || <math>O(n)</math> худший, <math>O(1)</math> средний || <math>O(1)</math> средний || <math>O(1)</math> средний || ~2 указателя || нет || когда порядок не нужен; но нет упорядоченного обхода
|-
| Splay-дерево || аморт. <math>O(\log n)</math> || аморт. <math>O(\log n)</math> || аморт. <math>O(\log n)</math> || 3 указателя || нет жёсткого || если часто запрашиваются «горячие» ключи
|}

[[Файл:rbt-06-complexity.svg|thumb|700px|Рис. 6. Худшая высота при <math>n = 10^6</math>: КЧ-дерево <math>\le 40</math>, АВЛ <math>\le 29</math>, B-дерево с <math>t=32</math> — около 4, а вырожденное BST может достичь <math>10^6</math>.]]

'''Вердикт.''' Красно-чёрное дерево — компромисс: слегка выше АВЛ-дерева, но требует меньше поворотов при записи, поэтому является стандартом для контейнеров общего назначения, где чередуются вставки, удаления и поиски. Если данные на диске — B-дерево выигрывает за счёт локальности. Если порядок не нужен и важна скорость в среднем — хеш-таблица.

== Где применяется ==

# '''Стандартная библиотека C++.''' <code>std::map</code>, <code>std::set</code>, <code>std::multimap</code>, <code>std::multiset</code> обязаны обеспечивать <math>O(\log n)</math> для каждой операции (требование стандарта), и основные реализации (libstdc++ от GCC, libc++ от LLVM) используют красно-чёрные деревья [5]. Выбор объясняется гарантией худшего случая и поддержкой упорядоченного обхода — хеш-таблицы этого не дают.
# '''Java Collections Framework.''' <code>java.util.TreeMap</code> и <code>TreeSet</code> также построены на красно-чёрном дереве и дают <math>O(\log n)</math> на операцию.
# '''Ядро Linux.''' КЧ-деревья используются для таймеров высокого разрешения и в <code>epoll</code>. Интервалы виртуальной памяти (<code>vm_area_struct</code>) исторически хранились в КЧ-дереве, но в новых ядрах их вытеснило maple tree. Планировщик CFS использовал КЧ-дерево с ключом <code>vruntime</code>; в новых ядрах его сменил EEVDF, который по-прежнему опирается на красно-чёрное дерево.
# '''.NET.''' <code>SortedDictionary&lt;TKey,TValue&gt;</code> и <code>SortedSet&lt;T&gt;</code> реализованы как красно-чёрные деревья, обеспечивая упорядоченные операции за <math>O(\log n)</math>.
# '''2-3-4-деревья и B-деревья.''' Теоретически каждому красно-чёрному дереву соответствует 2-3-4-дерево (красный узел + чёрный родитель = один много ключевой узел). Это связывает структуру с дисковыми B-деревьями и помогает понимать балансировку [1][4].
# '''Вычислительная геометрия и обработка интервалов.''' Интервальные деревья (interval trees) строятся на КЧ-деревьях (CLRS, гл. 14 [1]) и используются в задачах сметания плоскости (sweep line), поиска пересечений отрезков и в базах данных с диапазонными индексами в памяти.

== Историческая справка ==

* '''1962.''' Адельсон-Вельский и Ландис предложили АВЛ-деревья — первое сбалансированное BST с разностью высот <math>\le 1</math> [6].
* '''1972.''' Рудольф Байер ввёл «симметричные двоичные B-деревья» (symmetric binary B-trees) — структуру, эквивалентную будущим красно-чёрным деревьям [3].
* '''1978.''' Лео Гибас и Роберт Седжвик в статье «A Dichromatic Framework for Balanced Trees» дали современную формулировку с красно-чёрной раскраской и названием «красно-чёрное дерево»; их рамка объединила разные классы сбалансированных деревьев [2].
* '''2008.''' Седжвик предложил вариант «лево-ориентированных красно-чёрных деревьев» (left-leaning red-black trees), упрощающий реализацию за счёт запрета красных правых рёбер [4].
* Название происходит от двухцветной раскраски, введённой Гибасом и Седжвиком; в исходной формулировке Байера цвета соответствовали типам рёбер «горизонтальным/вертикальным» [3].

== Типичные ошибки и подводные камни ==

* '''Забыть перекрасить корень в чёрный''' в конце <code>Insert-Fixup</code> — нарушается свойство 2.
* '''Не вызывать <code>Delete-Fixup</code> при удалении чёрного узла.''' Если удалённый/перемещённый узел был красным, чёрная высота не меняется и балансировка не нужна; если чёрным — нужна обязательно.
* '''Путать цвет <code>y</code> и цвет <code>z</code>''' при удалении узла с двумя детьми: запоминать надо исходный цвет преемника <code>y</code>, а <code>z</code> может быть любого цвета — его цвет копируется в <code>y</code>.
* '''Изменять часовой <code>nil</code>.''' <code>nil</code> всегда чёрный, но его поле <code>parent</code> временно меняется в <code>transplant</code>, поэтому читать <code>parent[nil]</code> вне <code>Delete-Fixup</code> нельзя: там может лежать ссылка на последнего родителя, а не на сам <code>nil</code>. Цвет <code>nil</code> при этом никогда не меняется.
* '''Нарушать порядок случаев.''' В <code>Delete-Fixup</code> случай 3 обязателен перед случаем 4; в <code>Insert-Fixup</code> случай 2 обязан идти перед случаем 3. Перестановка ломает инвариант.
* '''Рекурсивный деструктор''' — при корректном дереве глубина <math>O(\log n)</math> безопасна, но если инвариант уже нарушен и дерево выродилось, рекурсия может переполнить стек; безопаснее итеративный обход.
* '''Инвалидация итераторов и ссылок.''' У <code>std::map</code>/<code>std::set</code> вставка не инвалидирует итераторы, а удаление — только итераторы и ссылки на удалённый элемент. В учебной реализации из этой статьи узел-преемник физически перемещается на место удалённого и получает его ключ, поэтому указатель на преемника после <code>erase</code> указывает на узел с другим ключом: если храните итераторы, либо не перемещайте узлы, либо обновляйте их.
* '''Ожидание строгого баланса.''' КЧ-дерево не даёт идеальной сбалансированности: высота может достигать <math>2\log_2(n+1)</math>, и это нормально. Не пытайтесь «дожать» его до АВЛ-условия — потеряете константные границы числа поворотов.
* '''Дубликаты.''' Стандартные <code>map</code>/<code>set</code> уникальны; для мультимножеств нужен счётчик, иначе вставка молча теряет элементы.

== Задачи для практики ==

# '''Проверка корректности раскраски.''' Дано дерево с цветами. За <math>O(n)</math> проверьте все пять RB-свойств. Ограничения: <math>n \le 10^6</math>. Подсказка: обход снизу вверх, возвращайте чёрную высоту поддерева и наличие нарушения. Ответ: одна рекурсивная функция, <math>O(n)</math> времени и <math>O(\log n)</math> стека.
# '''Число перекрасок.''' Докажите, что вставка одного ключа вызывает не более <math>O(\log n)</math> перекрасок и не более 2 поворотов. Подсказка: случай 1 поднимает <math>z</math> на два уровня за <math>O(1)</math> перекрасок; случаи 2–3 — последние.
# '''Интервал-дерево.''' Реализуйте на КЧ-дереве поиск всех интервалов, пересекающих запрос. Ограничения: <math>n \le 10^5</math>. Подсказка: в узле храните максимум правых концов поддерева. Ответ: <math>O(\log n + k)</math>, где <math>k</math> — число ответов.
# '''Построение за <math>O(n)</math>.''' По отсортированному массиву постройте КЧ-дерево за <math>O(n)</math>. Подсказка: делите массив пополам, верхнему уровню давайте чёрные узлы, нижнему — красные.
# '''Порядковая статистика.''' Добавьте в узлы размер поддерева и реализуйте <code>select(k)</code> и <code>rank(key)</code> за <math>O(\log n)</math>. Подсказка: пересчитывайте размер при поворотах.
# '''Диапазонный запрос.''' Выведите все ключи в <math>[a, b]</math> за <math>O(\log n + k)</math>. Подсказка: рекурсивный обход, отсекающий поддеревья вне диапазона.
# '''Сравнение с АВЛ.''' Сгенерируйте 100 000 случайных вставок и посчитайте число поворотов в КЧ- и АВЛ-дереве. Подсказка: сравните число поворотов и перекрасок; объясните разницу.
# '''Мультимножество.''' Расширьте реализацию до <code>multiset</code> со счётчиком повторов; проверьте, что удаление одного из дубликатов не удаляет весь узел преждевременно.

== Связанные темы ==

* [[двоичное-дерево-поиска|Двоичное дерево поиска]] — базовая структура, над которой надстроена балансировка.
* [[авл-дерево|АВЛ-дерево]] — более строгий баланс, больше поворотов.
* [[b-дерево|B-дерево]] — страничная балансировка для дисков.
* [[2-3-4-дерево|2-3-4-дерево]] — изоморф Красно-чёрному дереву.
* [[2-3-дерево|2-3-дерево]] — частный случай (порядок 3); лево-ориентированная кодировка.
* [[splay-дерево|Splay-дерево]] — амортизированная альтернатива без хранения цвета.
* [[декартово-дерево|Декартово дерево]] — рандомизированное упорядоченное дерево.
* [[хеш-таблица|Хеш-таблица]] — альтернатива, когда порядок не нужен.
* [[асимптотическая-сложность|Асимптотическая сложность]] — нотация <math>O</math>, <math>\Omega</math>, <math>\Theta</math>.

== Источники ==

# Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. ''Introduction to Algorithms'' (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 13 «Red-Black Trees», гл. 14 «Augmenting Data Structures», гл. 17 «Amortized Analysis».
# Guibas L. J., Sedgewick R. A Dichromatic Framework for Balanced Trees // Proceedings of the 19th Annual Symposium on Foundations of Computer Science (FOCS). — 1978. — P. 8–21.
# Bayer R. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms // Acta Informatica. — 1972. — Vol. 1, No. 4. — P. 290–306.
# Sedgewick R., Wayne K. ''Algorithms''. 4th ed. — Addison-Wesley, 2011. — Гл. 3.3 «Balanced Search Trees».
# Wikipedia: Red–black tree. URL: https://en.wikipedia.org/wiki/Red%E2%80%93black_tree ''(проверено)''; Wikipedia: AVL tree. URL: https://en.wikipedia.org/wiki/AVL_tree.
# Adelson-Velsky G. M., Landis E. M. An Algorithm for the Organization of Information // Doklady Akademii Nauk SSSR. — 1962. — Vol. 146. — P. 263–266.

[[Category:Алгоритмы и структуры данных]]
[[Category:Деревья поиска]]