- Обходить двоичное дерево в прямом, симметричном, обратном порядке и по уровням
- Выполнять поиск, вставку и удаление в двоичном дереве поиска и объяснять стоимость O(h)
- Отслеживать вставку и извлечение минимума в куче на её представлении массивом
Папки на компьютере, генеалогическое древо, HTML-элементы веб-страницы, синтаксическое дерево, которое компилятор строит по программе, — всё это деревья. А в приёмном отделении больницы пациентов принимают не по порядку прихода, а по тяжести состояния: это очередь с приоритетом, построенная на дереве. В этом уроке мы изучим математику деревьев и два важнейших их вида — двоичное дерево поиска и кучу.
Двоичные деревья и их обходы
Дерево, в котором у каждого узла не более двух потомков (левого и правого). Верхний узел — корень, узел без потомков — лист. Глубина узла — число рёбер от корня до него, высота дерева h — наибольшая глубина.
- nчисло узлов
- hвысота дерева (в рёбрах)
На глубине d помещается не более 2ᵈ узлов: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. Значит, высота двоичного дерева из n узлов не может быть меньше примерно log₂ n, но может достигать n − 1.
50
/ \
30 70
/ \ / \
20 40 60 80
/
35| Обход | Правило | Результат для примера | Где применяется |
|---|---|---|---|
| Прямой (preorder) | корень, левое, правое | 50 30 20 40 35 70 60 80 | копирование дерева |
| Симметричный (inorder) | левое, корень, правое | 20 30 35 40 50 60 70 80 | ключи в отсортированном порядке |
| Обратный (postorder) | левое, правое, корень | 20 35 40 30 60 80 70 50 | удаление, подсчёт размера папок |
| По уровням | с очередью, сверху вниз | 50 30 70 20 40 60 80 35 | кратчайшие пути, печать по уровням |
Двоичные деревья поиска (BST)
В двоичном дереве поиска для каждого узла все ключи левого поддерева меньше его, а правого — больше. Поиск начинается с корня: если ключ меньше — идём влево, если больше — вправо; это древесный вариант двоичного поиска. Вставка тем же путём находит свободное место. Обе операции занимают O(h).
Удали 30 из дерева-примера. Каким будет симметричный обход после удаления?
Показать решениеСкрыть решение
У 30 два потомка (20 и 40). Правое поддерево: 40 → 35. Наименьший ключ — 35 (идём влево до упора).
Записываем 35 на место 30 и удаляем 35 со старого места (это лист).
Новое дерево: 50 → (35 → 20, 40), (70 → 60, 80).
Симметричный обход: 20 35 40 50 60 70 80 — по-прежнему по возрастанию, свойство BST сохранено.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(t):
return inorder(t.left) + [t.key] + inorder(t.right) if t else []
def preorder(t):
return [t.key] + preorder(t.left) + preorder(t.right) if t else []
def height(t):
return -1 if t is None else 1 + max(height(t.left), height(t.right))
root = chain = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
for k in range(1, 9):
chain = insert(chain, k)
print('inorder: ', inorder(root))
print('preorder:', preorder(root))
print('height:', height(root), '| sorted input height:', height(chain))▸ Ожидаемый результат
inorder: [20, 30, 35, 40, 50, 60, 70, 80] preorder: [50, 30, 20, 40, 35, 70, 60, 80] height: 3 | sorted input height: 7
Выход — сбалансированные деревья: после каждой вставки и удаления они с помощью поворотов (rotation) удерживают высоту O(log n). В АВЛ-дереве высоты левого и правого поддеревьев любого узла отличаются не больше чем на 1 (h < 1,44 log₂ n); в красно-чёрном дереве h ≤ 2 log₂(n + 1). TreeMap в Java и std::map в C++ — красно-чёрные деревья, а индексы баз данных — B-деревья, хранящие в каждом узле сотни ключей.
Кучи и очереди с приоритетом
Полное двоичное дерево (все уровни заполнены, последний — слева направо), в котором каждый узел не больше своих потомков. Значит, минимум всегда в корне. Дерево хранится без указателей, просто в массиве.
- iиндекс узла в массиве (с 0)
Дерево записывается в массив по уровням; так как оно полное, пропусков нет, а высота равна ⌊log₂ n⌋.
Min-куча: [3, 5, 8, 10, 7]. а) Вставь 2. б) Затем извлеки минимум. Записывай массив после каждого шага.
Показать решениеСкрыть решение
parent(5) = 2, там 8 > 2 → меняем → [3, 5, 2, 10, 7, 8].
parent(2) = 0, там 3 > 2 → меняем → [2, 5, 3, 10, 7, 8]. Дошли до корня.
б) Погружение (sift-down): забираем корень 2, последний элемент 8 ставим в корень → [8, 5, 3, 10, 7].
Потомки: 5 (i = 1) и 3 (i = 2); меньший — 3 → меняем → [3, 5, 8, 10, 7].
У i = 2 потомков нет (индексы 5 и 6 за пределами массива) → [3, 5, 8, 10, 7], извлечено 2.
Каждая операция делает не больше h = ⌊log₂ n⌋ обменов → O(log n).
import heapq
heap = [3, 5, 8, 10, 7]
heapq.heappush(heap, 2)
print(heap)
print(heapq.heappop(heap), heap)
patients = []
for urgency, name in [(3, 'Aysel'), (1, 'Murad'), (2, 'Leyla'), (1, 'Elvin')]:
heapq.heappush(patients, (urgency, name))
while patients:
print(heapq.heappop(patients))
def heap_sort(a):
h = a[:]
heapq.heapify(h)
return [heapq.heappop(h) for _ in range(len(h))]
print(heap_sort([9, 4, 7, 1, 8, 2]))▸ Ожидаемый результат
[2, 5, 3, 10, 7, 8] 2 [3, 5, 8, 10, 7] (1, 'Elvin') (1, 'Murad') (2, 'Leyla') (3, 'Aysel') [1, 2, 4, 7, 8, 9]
heapq в Python — это min-куча на обычном list: результат совпадает с ручной трассировкой. Пациенты хранятся парами (срочность, имя): меньшее число срочнее, при равенстве сравниваются имена. heapify + n раз heappop = пирамидальная сортировка.- hвысота узла над листьями
- n / 2ʰ⁺¹n / 2ʰ⁺¹число узлов высоты h (примерно)
heapify превращает массив в кучу снизу вверх: половина узлов — листья (0 работы), четверть погружается на 1 шаг и т. д. Поскольку ∑ h/2ʰ = 2, всего получается O(n), а не O(n log n). Пирамидальная сортировка затем делает n извлечений — O(n log n).
| Операция | Сбалансированное BST | Несбалансированное BST (худший) | Двоичная куча |
|---|---|---|---|
| поиск любого ключа | O(log n) | O(n) | O(n) |
| вставка | O(log n) | O(n) | O(log n) |
| посмотреть минимум | O(log n) | O(n) | O(1) |
| извлечь минимум | O(log n) | O(n) | O(log n) |
| построить из n элементов | O(n log n) | O(n²) | O(n) |
Главное
- Высота двоичного дерева из n узлов не меньше ≈ log₂ n и не больше n − 1.
- Прямой, симметричный и обратный обходы определяются местом корня; симметричный обход BST выдаёт ключи по возрастанию.
- Операции BST — O(h); сбалансированные деревья (АВЛ, красно-чёрные, B-деревья) удерживают h = O(log n).
- Куча — полное дерево в массиве: потомки в 2i + 1 и 2i + 2; вставка и извлечение минимума — O(log n), построение — O(n).
- Очередь с приоритетом строится на куче; пирамидальная сортировка — O(n log n), на месте, но неустойчивая.
Проверь себя
Вопросов: 10. Каждый правильный ответ приносит XP.