Красно-черное дерево

Материал из Викиконспекты ПМ-ПУ

TL;DR

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

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

Определения

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

  1. Каждый узел либо красный, либо чёрный.
  2. Корень дерева чёрный.
  3. Каждый лист (NIL, внешний узел-часовой) чёрный.
  4. Оба ребёнка красного узла чёрные (эквивалентно: нет двух красных узлов, соединённых ребром).
  5. Для любого узла все простые пути от него вниз до листьев содержат одинаковое число чёрных узлов.

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

Высота дерева (height) [math]\displaystyle{ h }[/math] — число рёбер на самом длинном пути от корня до листа.

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

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

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

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

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

Устройство

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

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

Рис. 1. Красно-чёрное дерево с двумя красными узлами (15 и 50). Любой путь от корня до листа NIL содержит ровно два чёрных узла, не считая корня, поэтому [math]\displaystyle{ bh = 2 }[/math]. Красные узлы не соседствуют друг с другом: у 15 и 50 родитель 30 — чёрный.

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

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

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

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

Пошаговое описание (левый поворот вокруг [math]\displaystyle{ x }[/math], рис. 2).

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

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

Псевдокод. 

Алгоритм 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 сохраняется.

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

Рис. 2. Левый поворот вокруг [math]\displaystyle{ x }[/math]: узел [math]\displaystyle{ y }[/math] поднимается, [math]\displaystyle{ x }[/math] опускается, среднее поддерево [math]\displaystyle{ b }[/math] перевешивается к [math]\displaystyle{ x }[/math]. Порядок [math]\displaystyle{ a \lt x \lt b \lt y \lt c }[/math] сохраняется.

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

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

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

  1. Отыскать место вставки спуском от корня; новый узел [math]\displaystyle{ z }[/math] получает ключ и ссылки на T.nil.
  2. Окрасить [math]\displaystyle{ z }[/math] в красный, добавить как лист (родитель [math]\displaystyle{ y }[/math]), увеличить счётчик.
  3. Пока родитель [math]\displaystyle{ z }[/math] красный, выполнять балансировку (см. три случая).
  4. В конце окрасить корень в чёрный.

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

Псевдокод. 

Алгоритм 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 устраняют его окончательно.

Разбор трёх случаев (для [math]\displaystyle{ p }[/math] — левый ребёнок деда [math]\displaystyle{ g }[/math], рис. 3):

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

Случай зеркалится, когда [math]\displaystyle{ p }[/math] — правый ребёнок [math]\displaystyle{ g }[/math].

Рис. 3. Три случая балансировки после вставки. Случай 1 (дядя красный) — только перекраска; случай 2 превращается в случай 3 одним поворотом; случай 3 завершает балансировку поворотом вокруг деда.

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

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

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

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

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

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

Псевдокод. 

Алгоритм 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) памяти. Поворотов не более трёх.

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

Алгоритм 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.
Рис. 4. Четыре случая Delete-Fixup для [math]\displaystyle{ x }[/math] — левого ребёнка. Пунктир и «●●» обозначают двойную черноту. Случай 1 (брат красный) — поворот; случай 2 (оба ребёнка брата чёрные) — перекраска и подъём; случай 3 (левый ребёнок брата красный) — подготовительный поворот; случай 4 (правый ребёнок красный) — завершающий поворот.

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

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

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

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

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

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

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

  1. Начать с корня: [math]\displaystyle{ x \leftarrow root[T] }[/math].
  2. Пока [math]\displaystyle{ x \ne \text{T.nil} }[/math] и [math]\displaystyle{ k \ne \text{key}[x] }[/math], спускаться: если [math]\displaystyle{ k \lt \text{key}[x] }[/math] — влево, иначе вправо.
  3. Вернуть [math]\displaystyle{ x }[/math]: либо узел с ключом [math]\displaystyle{ k }[/math], либо T.nil, если ключа в дереве нет.
Алгоритм 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-свойства, которое повороты и перекраски не нарушают.

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

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

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

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

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

#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;
}

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

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

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

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

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

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

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

Шаг Вставили Состояние (в порядке возрастания) Действие Insert-Fixup
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 (чёрный). Проверка validate() на каждом шаге подтверждает все пять RB-свойств.

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

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

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

[math]\displaystyle{ n(x) \ge \bigl(2^{bh(x)-1}-1\bigr) + \bigl(2^{bh(x)-1}-1\bigr) + 1 = 2^{bh(x)} - 1. }[/math]

[math]\displaystyle{ \blacksquare }[/math]

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

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

[math]\displaystyle{ 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]\displaystyle{ \blacksquare }[/math]

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

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

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

Рис. 5. Минимальное дерево с чёрной высотой [math]\displaystyle{ bh = 3 }[/math] содержит [math]\displaystyle{ 2^3-1 = 7 }[/math] чёрных узлов. Красные узлы могут быть вставлены только между чёрными, поэтому [math]\displaystyle{ h \le 2\,bh }[/math].

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

Структура Поиск (худший) Вставка (худший) Удаление (худший) Память на узел Баланс Когда выбирать
Несбалансированное BST [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(n) }[/math] [math]\displaystyle{ O(n) }[/math] 3 указателя нет учебные задачи, статические данные
Красно-чёрное дерево [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(\log n) }[/math], ≤ 3 поворотов 3 указателя + 1 бит высота [math]\displaystyle{ \le 2\log_2(n{+}1) }[/math] универсальный выбор: std::map, TreeMap
АВЛ-дерево [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(\log n) }[/math] [math]\displaystyle{ O(\log n) }[/math], до [math]\displaystyle{ O(\log n) }[/math] поворотов 3 указателя + баланс разность высот [math]\displaystyle{ \le 1 }[/math] частые поиски, редкие записи
B-дерево / B⁺-дерево [math]\displaystyle{ O(\log_t n) }[/math] [math]\displaystyle{ O(\log_t n) }[/math] [math]\displaystyle{ O(\log_t n) }[/math] массив ключей в блоке страницы по [math]\displaystyle{ t }[/math] ключей диск, СУБД, файловые системы
Хеш-таблица [math]\displaystyle{ O(n) }[/math] худший, [math]\displaystyle{ O(1) }[/math] средний [math]\displaystyle{ O(1) }[/math] средний [math]\displaystyle{ O(1) }[/math] средний ~2 указателя нет когда порядок не нужен; но нет упорядоченного обхода
Splay-дерево аморт. [math]\displaystyle{ O(\log n) }[/math] аморт. [math]\displaystyle{ O(\log n) }[/math] аморт. [math]\displaystyle{ O(\log n) }[/math] 3 указателя нет жёсткого если часто запрашиваются «горячие» ключи
Рис. 6. Худшая высота при [math]\displaystyle{ n = 10^6 }[/math]: КЧ-дерево [math]\displaystyle{ \le 40 }[/math], АВЛ [math]\displaystyle{ \le 29 }[/math], B-дерево с [math]\displaystyle{ t=32 }[/math] — около 4, а вырожденное BST может достичь [math]\displaystyle{ 10^6 }[/math].

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

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

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

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

  • 1962. Адельсон-Вельский и Ландис предложили АВЛ-деревья — первое сбалансированное BST с разностью высот [math]\displaystyle{ \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].

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

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

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

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

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

Источники

  1. 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».
  2. 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.
  3. Bayer R. Symmetric Binary B-Trees: Data Structure and Maintenance Algorithms // Acta Informatica. — 1972. — Vol. 1, No. 4. — P. 290–306.
  4. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — Гл. 3.3 «Balanced Search Trees».
  5. 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.
  6. Adelson-Velsky G. M., Landis E. M. An Algorithm for the Organization of Information // Doklady Akademii Nauk SSSR. — 1962. — Vol. 146. — P. 263–266.
Источник — https://apmath.info/w/index.php?title=Красно-черное_дерево&oldid=851