лекция_10

1.

Лекция 10
Красно-черные деревья
2026

2. Определение

Красно-черное дерево (Red-Black Tree, RBT) - это особый вид
самобалансирующегося бинарного дерева поиска, изобретенный
в 1978 году Леонидасом Гибасом и Робертом Седжвиком.
Основная идея этой структуры данных заключается в
дополнительном атрибуте каждого узла - "цвете", который может
быть либо красным, либо черным.
Красно-черные
деревья
являются
одной
из
наиболее
эффективных и широко используемых структур данных и
представляют собой самобалансирующиеся бинарные деревья
поиска, которые обеспечивают логарифмическую сложность для
основных операций.
2

3. Свойства

Красно-черное дерево удовлетворяет следующим свойствам:
1. Свойство цвета. Каждый узел является либо красным, либо
черным.
2. Свойство корня. Корень дерева всегда черный.
3. Красное свойство узла. Если узел красный, то оба его потомка
черные (у красного узла не может быть красных детей).
4. Черное свойство высоты. Для каждого узла все пути от этого
узла до листьев содержат одинаковое количество черных
узлов.
5. Все NIL- узлы черные.
Благодаря этим свойствам самый длинный путь от корня до любого листа не
более чем в два раза длиннее самого короткого пути, что обеспечивает баланс
и эффективную работу дерева.
Высота красно-черного дерева с n узлами не превышает 2 · log₂(n + 1)
3

4. Примеры дерева

Какие из деревьев составлены корректно?
100
60
21
100
2.
145
100
110
76
60
160
1.
21
21
145
76
110
145
110
76
32
150
3.
150
4

5. Основные операции

Основные операции с красно-черным деревом:
1. Вставка
2. Поиск
3. Удаление
Поиск происходит как в обычном BST.
Вставка и удаление по аналогии с AVL-деревом. Сначала
вставляем или удаляем элемент как в обычном BST, а потом, при
необходимости, происходит перебалансировка дерева.
5

6. Вставка в красно-черное дерево

При вставке в дерево AVL мы использовали вращение как
инструмент для балансировки после вставки. В красно-чёрном
дереве мы используем два инструмента для балансировки.
1. Перекрашивание
2. Вращение
Перекрашивание — это изменение цвета узла, то есть если он
красный, то мы меняем его на чёрный и наоборот. Следует
отметить, что цвет корневого узла всегда чёрный. Кроме того, мы
всегда сначала пробуем перекрасить, и только если это не
помогает, переходим к поворотам. Мы рассмотрим подробный
алгоритм вставки. Алгоритмы в основном делятся на два случая в
зависимости от цвета дяди. Если дядя красный, мы
перекрашиваем. Если дядя чёрный, мы меняем местами и/или
перекрашиваем.
6

7. Вставка в красно-черное дерево

Общий пример, который будем рассматривать в дальнейшем:
Дедушка X (Grandfather)
G
Дядя X
(Uncle)
Родитель X (Parent)
U
P
S
X
Одноуровневый элемент с X
(брат X) (Sibling)
7

8. Вставка в красно-черное дерево

Сначала вставляем узел так же, как в двоичное дерево, и
присваиваем ему красный цвет.
Теперь, если узел является корневым, измените его цвет на
чёрный, а если нет, то проверьте цвет родительского узла. Если
его цвет чёрный, то не меняйте цвет, а если нет, то есть он
красный, то проверьте цвет дяди узла. Если у дяди узла красный
цвет, измените цвет родителя и дяди узла на чёрный, а цвет
дедушки на красный и повторите тот же процесс для него (т. е. для
дедушки). Если дедушка является корнем, не меняйте его цвет на
красный.
8

9. Вставка в красно-черное дерево

Дядя красный
1. Измените цвет
родительского элемента
P и дяди U на черный.
2. Измените цвет дедушки
G на красный
G
P
G
U
X
P
U
X
Исходная структура дерева
Результирующая структура дерева
1. Рекурсивно повторяем шаги
перекрашивания, рассматривая дедушку G в
качестве X
9

10. Вставка в красно-черное дерево

Но если у дяди-узла чёрный цвет, то возможны 4 варианта:
• Правый поворот
Дядя черный
1. Правый поворот для
дедушки G
2. Меняем цвета Дедушки
G и родителя P
G
P
U
X
Исходная структура дерева
P
X
G
U
Результирующая структура дерева
10

11. Вставка в красно-черное дерево

Но если у дяди-узла чёрный цвет, то возможны 4 варианта:
• Левый поворот
Дядя черный
1. Левый поворот для
дедушки G
2. Меняем цвета Дедушки
G и родителя P
G
U
P
P
G
X
Исходная структура дерева
X
U
Результирующая структура дерева
11

12. Вставка в красно-черное дерево

Но если у дяди-узла чёрный цвет, то возможны 4 варианта:
• Лево-правый поворот
1. Левый поворот для родителя P
2. Правый поворот для узла дедушки G
G
P
G
U
X
X
X
U
P
P
G
U
Промежуточная структура дерева
Исходная структура дерева
Результирующая структура дерева
12

13. Вставка в красно-черное дерево

Но если у дяди-узла чёрный цвет, то возможны 4 варианта:
• Право-левый поворот
1. Правый поворот для родителя P
2. Левый поворот для узла дедушки G
G
G
U
P
X
U
X
X
G
P
U
P
Промежуточная структура дерева
Исходная структура дерева
Результирующая структура дерева
13

14. Вставка в красно-черное дерево

Итоговый алгоритм.
Пусть x - только что вставленный узел (стандартными правилами двоичного дерева
поиска). Цвет красный.
1. Если x — это корень, измените цвет x на чёрный.
2. Сделайте следующее, если цвет родителя x не ЧЕРНЫЙ и x не является корнем.
a) Если цвет дяди x является красным:
(i) Измените цвет родителей и дяди на ЧЕРНЫЙ.
(ii) Цвет дедушки - КРАСНЫЙ.
(iii) Указатель x = дедушка, повторите шаги 2 и 3 для нового x.
14

15. Вставка в красно-черное дерево

Итоговый алгоритм.
Пусть x - только что вставленный узел (стандартными правилами двоичного дерева
поиска). Цвет красный.
1. Если x — это корень, измените цвет x на чёрный.
2. Сделайте следующее, если цвет родителя x не ЧЕРНЫЙ и x не является корнем.
б) Если цвет дяди x — ЧЕРНЫЙ, то для x, родителя x (p) и дедушки x (g) может
быть четыре варианта:
(i) Правый поворот (p является левым потомком g, а x является левым
потомком p)
(ii) Лево-правый поворот (p является левым потомком g, а x — правым
потомком p)
(iii) Левый поворот (зеркальное отражение i)
(iv) Право-левый поворот (зеркальное отражение ii)
Перекраска после поворотов:
Для правого [3.б (i)] и левого [3.b (iii)] поворотов поменяйте местами цвета предка и
потомка после поворотов
Для лево-правого [3.b (ii)] и право-левого [3.b (iv)] поворотов поменяйте местами цвета
предка и вставленного узла после поворотов
15

16. Вставка в красно-черное дерево

Пример. Построение красно-черного дерева из массива [3, 21, 32, 15]
16

17. Вставка в красно-черное дерево

Пример. Построение красно-черного дерева из массива [3, 21, 32, 15]
Шаг 1. Вставляем элемент 3. Т.к. это будет корнем, меняем цвет на черный.
3
17

18. Вставка в красно-черное дерево

Пример. Построение красно-черного дерева из массива [3, 21, 32, 15]
Шаг 2. Вставляем элемент 21. Вставляемый элемент красим в красный цвет.
3
21
18

19. Вставка в красно-черное дерево

Пример. Построение красно-черного дерева из массива [3, 21, 32, 15]
Шаг 3. Вставляем элемент 32. Вставляемый элемент красим в красный цвет.
1. Видим 2 красных узла
подряд. => Нарушение
условия 3.
2. Выполнены все условия
для левого поворота.
3
21
32
21
3
32
19

20. Вставка в красно-черное дерево

Пример. Построение красно-черного дерева из массива [3, 21, 32, 15]
Шаг 3. Вставляем элемент 15. Вставляемый элемент красим в красный цвет.
1. Видим 2 красных узла
подряд. => Нарушение
условия 3.
2. Выполнены все условия
для перекрашивания
21
21
32
3
15
32
3
15
20

21. Вставка в красно-черное дерево

Пример. Построение красно-черного дерева из массива [3, 21, 32, 15].
Красно-черное дерево построено.
21
32
3
15
21

22. Удаление из красно-черного дерева

Удаление в красно-чёрном дереве немного сложнее, чем вставка.
При удалении узла (как и в BST) у него может не быть потомков,
быть один потомок или два потомка. Сначала выполняется
стандартное удаление, потом дерево балансируется.
22

23. Удаление из красно-черного дерева

Как и при вставке, для сохранения свойств красно-чёрного дерева
используются перекраска и повороты.
Если при вставке мы проверяем цвет «дяди», чтобы принять решение. При
удалении необходимо проверить цвет «брата» для принятия решения.
Основное свойство, которое нарушается после вставки, — это два
последовательных красных узла. При удалении нам не страшно потерять
красный узел. Основной проблемой является изменение высоты чёрного
дерева в поддеревьях, так как удаление чёрного узла может привести к
уменьшению высоты чёрного дерева на одном пути от корня до листа.
Удаление — довольно сложный процесс. Чтобы понять, как происходит
удаление, используется понятие «двойной чёрный». Когда чёрный узел
удаляется и заменяется чёрным дочерним узлом, дочерний узел помечается
как двойной чёрный. Теперь основная задача состоит в том, чтобы
преобразовать этот двойной чёрный узел в одиночный чёрный.
23

24. Удаление из красно-черного дерева

Алгоритм удаления:
1. Выполните стандартное удаление в двоичном дереве поиска. При
выполнении стандартной операции удаления в двоичном дереве поиска мы
всегда удаляем либо лист, либо узел, у которого есть только один потомок (для
внутреннего узла мы копируем значение следующего узла, а затем удаляем
следующий узел, который всегда является либо листом, либо узлом с одним
потомком). Таким образом, нам нужно обрабатывать только те случаи, когда
узел является листом или имеет одного потомка. Пусть v — удаляемый узел, а u
— потомок, который будет занимать место v (обратите внимание, что u NULL,
если v является листом, а цвет NULL считается чёрным).
24

25. Удаление из красно-черного дерева

Алгоритм удаления:
2. Простой случай: если либо u, либо v красные, мы помечаем заменённого
потомка как чёрного (без изменения высоты чёрного). Обратите внимание, что
и u, и v не могут быть красными, так как v является родителем u, а в красночёрном дереве не допускаются два последовательных красных цвета.
30
30
Удаляем 20
v
u
20
40
10
40
10
25

26. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.1) Покрасьте u в двойной чёрный цвет. Теперь наша задача сводится к тому,
чтобы преобразовать двойной чёрный цвет в одинарный чёрный. Обратите
внимание, что если v является листом, то u равно NULL, а цвет NULL считается
чёрным. Таким образом, удаление чёрного листа также приводит к появлению
двойного чёрного цвета.
30
30
Удаляем 20
v
u
NULL
40
20
NULL
u
50
NULL
40
50
26

27. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды
чёрным и не является корнем. Пусть брат узла будет s.
….(a): Если брат s является чёрным и хотя бы один из его потомков является
красным, выполните поворот(ы). Пусть красный потомок s будет r. Этот случай
можно разделить на четыре подслучая в зависимости от расположения s и r.
…………..(i) Правый поворот (s является левым потомком своего родителя, а r
является левым потомком s или оба потомка s являются красными). Это
зеркальное отражение левого поворота, который мы рассмотрим дальше.
…………..(ii) Лево-правый поворот (s является левым потомком своего родителя, а r
является правым потомком). Это зеркальное отражение правого левого случая,
который мы рассмотрим дальше.
27

28. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды
чёрным и не является корнем. Пусть брат узла будет s.
…………..(iii) Левый поворот (s является правым потомком своего родителя, а r
является правым потомком s, или оба потомка s являются красными):
• Брат (s) берёт цвет родителя (p).
• Родитель (p) становится чёрным.
• Правый ребенок брата (r) становится чёрным.
• Левый поворот вокруг родителя (p).
r
28

29. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды
чёрным и не является корнем. Пусть брат узла будет s.
…………..(iii) Левый поворот (s является правым потомком своего родителя, а r
является правым потомком s, или оба потомка s являются красными)
p
30
40
30
Удаляем 20
40
20
35
u
50
30
s
40
NULL
35
50
50
35
r
29

30. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды
чёрным и не является корнем. Пусть брат узла будет s.
…………..(iv) Право-левый поворот (s является правым потомком своего родителя, а
r — левым потомком s)
• Выполняем правый поворот для брата s (перекрашиваем брата и его левого
сына)
• Выполняем левый поворот для родителя P.
p
30
35
30
30
Удаляем
20
40
20
u
35
40
NULL
35
s
NULL
30
35
40
40
30

31. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды чёрным и
не является корнем. Пусть брат узла будет s.
…..(b): Если цвет элемента-брата (s) чёрный, и оба его потомка чёрные, выполните
перекраску и повторите для родительского элемента, если он чёрный (красим брата в
красный цвет и рекурсивно переходим к родителю – проблема "двойной черноты"
перемещается с листового элемента).
В случае, если родитель был красным, то нам не нужно рекурсивно повторять для него
процедуру, мы можем просто сделать его чёрным (красный + двойной чёрный =
одинарный чёрный)
p
p
20
v
20
20
Удаляем
10
10
30
s
u
NULL
30
s
NULL
NULL
NULL
NULL
NULL
NULL
Рекурсивно
для 20
NULL
30
31

32. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды чёрным и
не является корнем. Пусть брат узла будет s.
…..(c): Если брат или сестра красные, выполните поворот, чтобы переместить старого
брата или сестру вверх, перекрасьте старого брата или сестру и родителя. Новый брат
или сестра всегда чёрные (см. диаграмму ниже). Это в основном преобразует дерево в
случай с чёрными братьями и сёстрами (поворотом) и приводит к случаям (a) или (b).
Этот случай можно разделить на два подслучая.
…………..(i) Правый поворот (s является левым дочерним элементом своего родителя). Это
зеркальное отражение левого поворота, показанного на следующем слайде.
32

33. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.2) Выполняйте следующие действия, пока текущий узел u является дважды чёрным и
не является корнем. Пусть брат узла будет s.
…..(c): Если брат или сестра красные, выполните поворот, чтобы переместить старого
…………..(ii) Левый поворот (s является правым дочерним элементом своего родителя). Мы
поворачиваем родителя p влево. Красим брата в чёрный, а отца — в красный цвет
p
p
20
20
v
30
Удаляем 10
30
10
25
s
35
u
30
Левый поворот
30
NULL
25
s
35
3.2.b
20
NULL
35
25
20
NULL
35
25
33

34. Удаление из красно-черного дерева

Алгоритм удаления:
3. Если оба u и v черные:
3.3) Если u является корнем, сделайте его единственным чёрным узлом.
34

35. Сравнение с AVL-деревьями

Деревья AVL более сбалансированы по сравнению с красночёрными деревьями и имеют гораздо более простую и понятную
реализацию. Но имеют 1 основной недостаток. Какой?
Они могут вызывать больше поворотов при вставке и удалении.
Поэтому, если в вашем приложении часто происходят вставки и
удаления, следует использовать красно-чёрные деревья.
Если же операции вставки и удаления происходят редко, а поиск
является более востребованной операцией, то дерево AVL будет
выгоднее.
35

36. Сравнение с AVL-деревьями

Параметр
AVL
КЧД
Поиск
O(1.44 log n)
O(2 log n)
Вставка
До 2 поворотов
До 2 поворотов
Удаление
O(log n) поворотов
≤3 поворотов
Балансировка
Локальная+глобаль
ная
Локальная*
*из-за того, что балансировка выполняется локально, в узлах красно-черных
деревьев принято хранить ссылки на родительский элемнент
36

37. Практическое применение

Красно-черные деревья имеют множество практических применений
благодаря
их
эффективной
балансировке
и
гарантированной
логарифмической сложности операций:
• Кластеризация k-средних: Красно-черные деревья используются в
алгоритмах кластеризации k-средних для эффективного поиска ближайших
соседей.
• Обработка текстов и майнинг текстов: Красно-черные деревья используются
в алгоритмах обработки естественного языка и поиска текста.
• Встроенные системы и операционные системы: Linux использует красночерные деревья для планирования процессов, управления виртуальной
памятью и в реализации файловых систем.
• Сборка мусора: Некоторые алгоритмы сборки мусора используют красночерные деревья для отслеживания объектов в памяти
37

38. Задание

Построить красно-черное дерево на основе массива [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].
Удалить из него элементы 5, 1.
38