Деревья: бинарные деревья, обходы (DFS/BFS)🔗
От иерархии к рекурсии🔗
Ранее мы работали с линейными структурами: массивами и связными списками, где у каждого элемента был строго один «сосед» спереди и сзади. Однако многие данные в реальности организованы иерархично — вспомните файловую систему или структуру DOM в браузере. Дерево — это связная нелинейная структура данных, представляющая собой совокупность узлов, в которой отсутствуют циклы.
С точки зрения архитектуры дерево — это рекурсивная структура. Его можно определить так: дерево состоит из корневого узла R и набора непересекающихся поддеревьев T1,T2,…,Tn, каждое из которых само является деревом. Концепция встроенных друг в друга элементов позволяет сводить глобальные задачи к операциям над отдельными частями иерархии.
Анатомия дерева🔗
Чтобы свободно ориентироваться в иерархических связях, обратимся к базовой терминологии:
- Корень (Root): Самый верхний узел, не имеющий родителя.
- Узел (Node): Единица хранения данных, связанная с потомками.
- Лист (Leaf): Терминальный узел, у которого нет дочерних элементов.
- Высота (h): Максимальное количество ребер от узла до самого дальнего листа. Высота пустого дерева обычно равна −1, дерева из одного корня — 0.
- Глубина (Depth): Расстояние в ребрах от корня до конкретного узла.
Диаграмма загружается…
Бинарные деревья и их типы🔗
Бинарное дерево — это частный случай, где степень исхода (количество потомков) для любого узла не превышает 2. Обычно такие ветви называют left и right.
В зависимости от заполненности и структуры выделяют три вида деревьев, критически важных для анализа сложности:
- Полное (Full): У каждого узла либо 0, либо 2 потомка. Узлов с одним ребенком в такой структуре нет.
- Завершенное (Complete): Все уровни заполнены целиком, за исключением, возможно, последнего, который заполняется строго слева направо. Это свойство необходимо для реализации куч.
- Идеальное (Perfect): Все внутренние узлы имеют по два потомка, а все листья находятся строго на одном уровне. Общее количество узлов в таком случае при высоте h вычисляется по формуле n=2h+1−1.
От структурного баланса напрямую зависит временная сложность поиска: в сбалансированном дереве она составляет O(logn), что делает его эффективным инструментом для быстрой обработки данных.
Теоретический минимум: Математика связей🔗
Эффективная работа с деревьями опирается на их топологические свойства. В отличие от линейных структур, дерево накладывает жесткие математические ограничения на количество связей и пропорции всей системы.
Свойства графа: Связность и отсутствие циклов🔗
Формально дерево — это частный случай графа. Его определяют два критических условия:
- Связность: между любыми двумя узлами существует путь.
- Ацикличность: в структуре нет маршрутов, которые возвращаются в исходную точку.
Подробную классификацию графов и способы их обхода изучим в девятой лекции.
Теорема о ребрах🔗
В любом дереве с количеством узлов n число ребер (связей) всегда равно n−1.
Это правило подтверждается логикой построения: одиночный корень имеет 0 ребер. Каждый следующий элемент, добавляемый в систему, соединяется ровно с одним из уже существующих узлов. Так сохраняется связность и исключается появление циклов. Появление k-го узла вносит в структуру ровно одну новую связь.
Диаграмма загружается…
На схеме для n=5 количество ребер ∣E∣=4.
Высота и плотность: Граничные состояния🔗
Высота h (дистанция от корня до самого удаленного листа) напрямую влияет на скорость поиска и изменения данных.
-
Вырожденное дерево:
Структура превращается в аналог связного списка.
- Соотношение: h=n−1.
- Эффективность доступа: O(n), что сопоставимо с перебором массива.
-
Полное бинарное дерево:
Узлы распределены максимально равномерно. На каждом уровне i (начиная с 0) располагается до 2i элементов.
- Общее число узлов n при высоте h вычисляется как n=2h+1−1.
- Высота зависит от количества элементов логарифмически: h≈log2n.
- Эффективность доступа: O(logn).
Логарифмическая сложность операций — главное преимущество деревьев. Чтобы сохранять такую производительность, применяют алгоритмы балансировки (например, AVL или красно-черные деревья), о которых пойдет речь в седьмой лекции.
Механика обходов: DFS и BFS🔗
Дерево не является линейной структурой, поэтому проитерироваться по нему привычным циклом от начала к концу невозможно. Проблема заключается в порядке посещения узлов: как гарантированно обработать каждый элемент ровно один раз? В Computer Science существуют две основные стратегии: движение вглубь до упора или исследование дерева слой за слоем.
Поиск в глубину (Depth-First Search, DFS)🔗
DFS опирается на самоподобие древовидных структур. Алгоритм выбирает одну ветвь и спускается по ней до самого листа (базовый случай рекурсии), после чего возвращается назад для перехода к следующей ветке.
Механически этот процесс неразрывно связан со стеком вызовов. При переходе к дочернему элементу состояние текущего узла «замораживается» в стеке, пока программа обрабатывает вложенное поддерево.
Для бинарных деревьев выделяют три классических порядка обхода. Они различаются тем, в какой момент обрабатывается значение корня относительно его потомков:
- Pre-order (Прямой): Корень → Лево → Право. Полезен для клонирования структуры или её сериализации в строку.
- In-order (Центрированный): Лево → Корень → Право. В бинарных деревьях поиска (BST) такой обход извлекает элементы строго по возрастанию.
- Post-order (Обратный): Лево → Право → Корень. Оптимален для удаления узлов или вычисления объема памяти, так как сначала вычисляются данные детей, а затем результат суммируется в родителе.
Диаграмма загружается…
Пример последовательности для дерева выше:
- Pre-order: 1, 2, 4, 5, 3
- In-order: 4, 2, 5, 1, 3
- Post-order: 4, 5, 2, 3, 1
def dfs_inorder(node):
if node is None:
return
dfs_inorder(node.left) # Рекурсивный переход влево
print(node.value) # Обработка данных (LIFO механизм стека вызовов)
dfs_inorder(node.right) # Рекурсивный переход вправо
Поиск в ширину (Breadth-First Search, BFS)🔗
В отличие от «вертикального» DFS, поиск в ширину работает горизонтально. Алгоритм посещает все узлы текущего уровня («поколения»), прежде чем перейти к следующему. Этот метод часто называют Level-order traversal.
В этой стратегии на смену рекурсии приходит итеративный цикл и очередь (Queue). Она реализует принцип FIFO: мы помещаем корень в очередь, а затем поочередно извлекаем узлы, добавляя всех их прямых потомков в конец списка. Это обеспечивает строгую последовательность обработки уровней.
Диаграмма загружается…
Логика BFS гарантирует, что программа не затронет узлы на глубине d+1, пока не завершит работу со всеми элементами на глубине d. Такое свойство делает обход в ширину незаменимым при поиске кратчайшего пути в невзвешенных графах.
from collections import deque
def bfs_level_order(root):
if not root:
return
# Используем deque для эффективного O(1) извлечения первого элемента
queue = deque([root])
while queue:
node = queue.popleft() # Достаем элемент, добавленный раньше всех
print(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
Сравнение механизмов🔗
Выбор конкретного алгоритма часто зависит от топологии дерева и доступных ресурсов памяти.
- Память в DFS: Нагрузка на систему пропорциональна максимальной глубине (высоте H). В сбалансированных деревьях это logN, в вырожденных — N.
- Память в BFS: Расход ресурсов зависит от максимальной «ширины» структуры. В полных бинарных деревьях на последнем уровне находится N/2 узлов, что в худшем случае требует значительно больше оперативной памяти, чем стек при поиске в глубину.
Оба подхода имеют временную сложность O(N), так как для полной обработки структуры необходимо посетить каждый узел. Подробный разбор пограничных случаев и специфику реализации мы изучим в следующем блоке.
Анализ сложности и реализация🔗
Переход от концептуальных моделей к программному коду требует оценки ресурсов. Если рассматривать алгоритм как потребителя мощностей, важно понимать, какую «цену» платит система за иерархическую гибкость деревьев.
Асимптотический анализ операций🔗
В худшем случае, когда дерево вырождается в длинную цепочку, временная сложность поиска или вставки становится линейной. Для сбалансированных структур эти показатели значительно лучше.
| Операция / Обход |
Временная сложность (Time) |
Пространственная сложность (Space) |
| Поиск (в произвольном бинарном дереве) |
O(n) |
O(h) |
| Вставка / Удаление (листа) |
O(1) — при ссылке на родителя |
O(1) |
| Обход в глубину (DFS) |
O(n) |
O(h) |
| Обход в ширину (BFS) |
O(n) |
O(w) |
Здесь n — количество узлов, h — высота дерева, w — максимальная ширина (число элементов на самом населенном уровне). В худшем сценарии h=n, а в идеально сбалансированном — h=⌈log2(n+1)⌉.
Программная реализация и барьеры🔗
Написание кода на Python опирается на узловую структуру. Основное отличие от линейных структур заключается в наличии нескольких указателей на потомков вместо одного.
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert_left(root, value):
"""Вставка с сохранением существующих веток"""
new_node = TreeNode(value)
if root.left is None:
root.left = new_node
else:
# Чтобы не потерять данные, переподвешиваем текущую ветку к новому узлу
new_node.left = root.left
root.left = new_node
Распространенные ошибки:
- Разрыв связей при удалении: Если убрать узел, не являющийся листом, можно случайно «отрезать» всё его поддерево. Программа должна явно переназначать указатели родителя на дочерние элементы удаляемого объекта.
- Зацикливание: Если узел начнет ссылаться на своего предка, обход в глубину станет бесконечным и переполнит стек вызовов. Дерево обязано быть ацикличным — это фундаментальное ограничение графовых иерархий.
- Управление памятью: В языках без автоматической сборки мусора удаление корня без рекурсивной очистки потомков ведет к утечкам. В Python стоит быть внимательнее с циклическими ссылками, если в
TreeNode добавляется поле parent.
Прикладное использование: Синтаксические деревья🔗
Фундаментальная область применения таких структур — парсинг выражений. Компиляторы преобразуют текст кода в абстрактное синтаксическое дерево (AST), где приоритет операций диктуется глубиной расположения узла.
Диаграмма загружается…
На схеме: Представление выражения 2∗3+4. Порядок вычислений определяется обходом Post-order (лево-право-корень).
Иерархии также незаменимы в организационных схемах и JSON-документах. О том, как сохранять минимальную высоту дерева для максимально быстрого поиска, пойдет речь в блоке о сбалансированных структурах (AVL и Красно-черных деревьях).
Когда использовать и что дальше🔗
Деревья становятся незаменимы, когда информация перерастает формат массивов или списков и требует четкой иерархии либо ускоренного упорядоченного доступа.
Критерии выбора🔗
Эта структура превосходит линейные аналоги, если для задачи критичен баланс между скоростью извлечения и частотой обновления данных:
- Иерархическая природа. Данные обладают естественной вложенностью: каталоги файлов, документы XML/JSON, организационные схемы.
- Эффективный диапазонный поиск. Хеш-таблицы обеспечивают константное время O(1) для поиска конкретного ключа, но не подходят для задачи «найти все значения от A до B». Упорядоченное дерево справляется с этим быстро.
- Динамичность. Деревья позволяют гибко добавлять и удалять узлы, сохраняя логарифмическую сложность операций. В этом их преимущество перед статическими массивами.
Проблема «вырождения»🔗
Высокая скорость поиска O(logn) (подробности — в лекции 12) характерна только для бинарных деревьев поиска (BST) с жестким порядком узлов. Без контроля формы структура способна превратиться в «бамбук», который функционально не отличается от связного списка.
Диаграмма загружается…
В таком состоянии сложность операций становится линейной — O(n), а иерархические бонусы исчезают. Чтобы сохранить производительность, применяют механизмы автоматической балансировки.
Перспективы изучения🔗
Деревья служат базой для многих сложных инженерных решений. В следующих частях курса мы изучим:
- Самобалансирующиеся деревья (AVL и Red-Black): способы автоматического поддержания минимальной высоты (лекция 7).
- Кучи (Heaps): специфические структуры для реализации очередей приоритетов (лекция 8).
- Графы: переход от строгой иерархии к произвольным связям между объектами (лекция 9).
