9_лекция_2026

1. Основы программного конструирования

ЛЕКЦИЯ №9
14 АПРЕЛЯ 2026

2. Дерево поиска

BST (Binary Search Tree).
Каждому узлу n сопоставлен ключ k(n).
k(x) < k(n) для x из левого поддерева n.
k(y) > k(n) для y из правого поддерева n.
Тривиальный алгоритм поиска.

3. Интерфейс дерева поиска

Поиск элемента по ключу
Вставка элемента по ключу
Удаление элемента по ключу
Перечисление всех ключей
Поиск и вставка за O(h(N))!

4. Высота дерева поиска

Бинарное дерево высоты h содержит максимум 2h–1 узлов.
Значит высота h(N) ≥ log(N).
При добавлении случайных элементов h(N) ~ 2,99 log(N).
Средняя глубина узла ~ 1,39 log(N).
Но в худшем случае…

5. Не все деревья одинаково полезны

6. Решения проблемы «кривых» деревьев

Восстановление оптимальности:
«Выворачивание» (splay trees),
АВЛ-деревья,
Красно-черные деревья.

7. Splay trees

Обычное дерево поиска, но после каждого поиска найденный элемент помещается в
вершину.
При удалении предок удаленного элемента помещается в вершину.
Помещение в вершину происходит пошагово («всплытие»).
«Средняя» сложность операций – O(log(N)).

8. АВЛ-деревья

1962 г. Адельсон-Вельский и Ландис (СССР)
Сбалансированное дерево: высоты двух родственных поддеревьев
отличаются не более, чем на единицу
Перебалансировка после операций вставки и удаления, нарушающих
свойство сбалансированности. Идем снизу вверх (к корню), восстанавливая
баланс.
В узел добавляется показатель сбалансированности, равный разности высот
поддеревьев (0, +1, −1).

9. Балансировка: Малый левый поворот

Поворот
вокруг B
Было
Вставили
Выполняется, если B имеет баланс +2,
а A имеет баланс ≥ 0.

10. Балансировка: Большой Левый поворот

Поворот
вокруг A, C
Было
Вставили
Выполняется, если С имеет баланс +2,
а A имеет баланс –1.

11. Балансировка: Правые повороты

Малый правый поворот аналогично малому левому
Большой правый поворот аналогично большому левому

12. Пример АВЛ-дерева

0
1
–2
–1
1
1
2
–1
0
Вставляем 1
0
2
малый
2
1
0
Вставляем 2
0
0
3
Вставляем 3
3

13. Пример АВЛ-дерева

–2
–1
2
2
2
–2
0
–1
0
1
–1
1
3
0
3
малый
–1
0
4
0
3
4
0
5
Вставляем 5
1
0
4
Вставляем 4
0
5

14. Пример АВЛ-дерева

0
2
0
+1
1
0
Вставляем 0
–1
4
0
0
0
2
3
+1
5
–1
1
Вставляем 7
4
–1
0
0
0
3
5
0
7

15. Пример АВЛ-дерева

–1
–2
2
2
+1
+1
–2
1
1
4
0
3
0
5
7
0
6
0
0
–2
+1
Вставляем 6
4
большой
0
0
–1
0
3
6
0
0
5
7

16. 2-3-4 Деревья

6
Дерево поиска, узлы которого:
либо пусты;
5
8
либо 2-узел: 1 значение, 2 поддерева;
47
либо 3-узел: 2 значения, 3 поддерева;
2
либо 4-узел: 3 значения, 4 поддерева.
6
Всегда идеально сбалансировано: высоты всех
поддеревьев равны.
9
357
2
4
6
8

17. 2-3-4 Деревья: Поиск и Вставка

Поиск как в обычном дереве поиска.
Вставка в 2-узел: превращаем его в 3-узел.
Вставка в 3-узел: превращаем его в 4-узел.
Вставка в 4-узел: временно создаем 5-узел, вытаскиваем одно из значений и
добавляем его в родителя.

18. Вставка: 5-узел как корень

c
abcd
ab
d
e
f
g
d
h
d
e
f
g
h

19. Вставка: 5-узел с родителем

Вытягиваем одно из значений на уровень выше и продолжаем рекурсивно идти наверх, если
получился новый 5-узел.
q
cq
abcd
d
e
f
…
g
h
ab
d
e
d
f
g
…
h

20. 2-3-4 Деревья: Анализ

Высота дерева: log4(N) ≤ h(N) ≤ log2(N).
Всегда идеально сбалансировано.
Очень трудоемкая реализация, но идея-то хорошая!

21. Красно-Черные деревья Red-Black trees

1. Все узлы либо красные, либо черные. Корень черный.
2. Потомки красного узла черные.
3. Все листья (NIL) черные.
4. Пути от любого узла до потомков содержат одинаковое количество черных узлов.
5. (Следствие) Пути от корня до двух любых узлов отличаются не более чем в 2 раза.

22. На сегодня все!