Структура данных дерево: термины, виды, обходы и код на Python
Дерево как структура данных простыми словами: корень, узлы и листья, высота и глубина, виды деревьев, представление в коде и обходы в глубину и в ширину. Примеры на Python.
Коротко
- Дерево — структура данных из узлов, связанных отношением «родитель — потомок». Есть один корень, у каждого остального узла ровно один родитель, циклов нет.
- В дереве из узлов всегда ребро, а между любыми двумя узлами существует ровно один путь.
- Главные термины: корень (узел без родителя), лист (узел без потомков), глубина (расстояние от корня до узла), высота (расстояние от узла до самого дальнего листа под ним).
- Почти все операции в деревьях стоят , где — высота. Поэтому половина «видов деревьев» — это способы удержать высоту около .
- Обойти дерево можно двумя способами: в глубину (DFS, рекурсия или стек) и в ширину (BFS, очередь). Оба работают за .
| Вид дерева | Зачем нужно | Ключевые операции |
|---|---|---|
| Бинарное дерево | Базовая форма: не больше двух потомков | обход |
| Бинарное дерево поиска | Хранить ключи упорядоченно | |
| АВЛ, красно-чёрное | То же, но высота гарантированно | |
| B-дерево | Индексы на диске: много ключей в одном узле | |
| Двоичная куча | Быстро доставать минимум или максимум | |
| Префиксное дерево (trie) | Поиск слов по префиксу | |
| Дерево отрезков, Фенвика | Суммы и минимумы на отрезках массива |
Что такое дерево
Массив и связный список — линейные структуры: у каждого элемента один следующий. Дерево описывает иерархию: у элемента может быть несколько «следующих», и у каждого из них — свои.
Примеры вокруг вас: папки на диске, HTML-документ (DOM), оргструктура компании, оглавление книги, вложенный JSON. Везде одна и та же картина: есть верхний элемент, из него растут вложенные, из тех — следующие.
Формальное определение короткое. Дерево — это набор узлов и рёбер, в котором:
- есть один выделенный узел — корень;
- у каждого узла, кроме корня, ровно один родитель;
- от корня можно дойти до любого узла.
Из этих трёх условий следует всё остальное: в дереве нет циклов, рёбер всегда на одно меньше, чем узлов, а путь между двумя узлами единственный.
В программировании дерево рисуют корнем вверх — в отличие от настоящих деревьев. Дальше будем работать с таким примером:
A глубина 0 / | \ B C D глубина 1 / \ \ E F G глубина 2 | H глубина 3
Термины: корень, узел, лист, высота, глубина
| Термин | Что значит | В примере |
|---|---|---|
| Узел (вершина) | Элемент дерева, хранит значение и ссылки на потомков | A, B, …, H — всего 8 |
| Ребро | Связь между родителем и потомком | A–B, B–F, … — всего 7 |
| Корень | Единственный узел без родителя | A |
| Родитель | Узел, стоящий на один шаг выше | у F родитель B |
| Потомок (ребёнок) | Узел на один шаг ниже | у B потомки E и F |
| Братья | Узлы с общим родителем | B, C и D |
| Лист | Узел без потомков | E, H, C, G |
| Внутренний узел | Узел, у которого есть хотя бы один потомок | A, B, D, F |
| Предок | Любой узел на пути от данного узла к корню | у H предки F, B, A |
| Поддерево | Узел вместе со всеми, кто под ним | поддерево B: B, E, F, H |
| Глубина узла | Число рёбер от корня до узла | у H глубина 3 |
| Высота узла | Число рёбер от узла до самого дальнего листа под ним | у B высота 2, у листа — 0 |
| Высота дерева | Высота корня | 3 |
| Уровень | Все узлы одной глубины | уровень 2: E, F, G |
| Степень узла | Число потомков | у A степень 3 |
Глубину и высоту путают чаще всего. Запомнить просто: глубина считается сверху, от корня, а высота — снизу, от листьев. У корня глубина 0 и самая большая высота. У листа высота 0, а глубина может быть любой.
Один подвох: в одних учебниках высоту считают в рёбрах (дерево из одного узла имеет высоту 0), в других — в узлах (высота 1). В этой статье считаем в рёбрах. На собеседовании и в условии задачи это стоит уточнить: на LeetCode, например, «maximum depth» считается в узлах.
Важное свойство, на котором держатся почти все алгоритмы: каждое поддерево — тоже дерево. Поэтому функции над деревьями естественно пишутся рекурсивно: реши задачу для потомков, собери ответ для узла. Если рекурсия пока даётся с трудом, загляните в разбор рекурсии.
Как представить дерево в коде
Узлы со ссылками на потомков
Самый прямой способ — класс узла со значением и списком потомков.
class Node: def __init__(self, value): self.value = value self.children = [] def add(self, child): self.children.append(child) return child root = Node('A') b = root.add(Node('B')) c = root.add(Node('C')) d = root.add(Node('D')) e = b.add(Node('E')) f = b.add(Node('F')) g = d.add(Node('G')) h = f.add(Node('H'))
Всё дерево доступно через одну переменную root. Так устроен DOM в браузере и большинство деревьев в прикладном коде.
Посчитаем на этом дереве то, что определили выше, — высоту, размер и листья:
def height(node): if not node.children: return 0 return 1 + max(height(child) for child in node.children) def size(node): return 1 + sum(size(child) for child in node.children) def leaves(node): if not node.children: return [node.value] result = [] for child in node.children: result.extend(leaves(child)) return result print(height(root)) # 3 print(height(b)) # 2 print(size(root)) # 8 print(leaves(root)) # ['E', 'H', 'C', 'G']
Все три функции устроены одинаково: у листа ответ известен сразу, у остальных узлов он собирается из ответов потомков.
Глубина считается в обратную сторону — её передают сверху вниз как аргумент:
def depths(node, depth=0, result=None): if result is None: result = {} result[node.value] = depth for child in node.children: depths(child, depth + 1, result) return result print(depths(root)) # {'A': 0, 'B': 1, 'E': 2, 'F': 2, 'H': 3, 'C': 1, 'D': 1, 'G': 2}
Бинарный узел
Если потомков не больше двух, вместо списка заводят два поля — left и right. Это бинарное дерево, самый частый вид на собеседованиях.
class TreeNode: def __init__(self, value, left=None, right=None): self.value = value self.left = left self.right = right
Словарь потомков и массив родителей
В задачах дерево часто приходит не объектами, а списком рёбер или массивом. Тогда удобнее словарь «узел → список потомков»:
tree = { 'A': ['B', 'C', 'D'], 'B': ['E', 'F'], 'C': [], 'D': ['G'], 'E': [], 'F': ['H'], 'G': [], 'H': [], }
Обратное представление — для каждого узла хранить только родителя. Оно компактное и позволяет быстро подниматься к корню, но не даёт спускаться вниз:
parent = {'A': None} for node, children in tree.items(): for child in children: parent[child] = node def path_to_root(node): path = [] while node is not None: path.append(node) node = parent[node] return path print(path_to_root('H')) # ['H', 'F', 'B', 'A'] print(len(path_to_root('H')) - 1) # 3 — глубина H
На массиве родителей построены система непересекающихся множеств и поиск наименьшего общего предка.
Массив без ссылок
Если дерево бинарное и заполнено по уровням слева направо без пропусков, ссылки не нужны вообще: узлы кладут в массив подряд, и положение потомков вычисляется по индексу.
heap = [1, 3, 2, 7, 4, 5] i = 1 # узел со значением 3 print(heap[2 * i + 1], heap[2 * i + 2]) # 7 4 — потомки print(heap[(i - 1) // 2]) # 1 — родитель
Так хранится двоичная куча и, с небольшими отличиями, дерево отрезков.
Обходы дерева
Обойти дерево — значит посетить каждый узел ровно один раз. Способов два, и различаются они порядком.
В глубину (DFS)
Идём вниз по одной ветке до листа, потом возвращаемся и берём следующую. Вопрос только в том, когда обрабатывать сам узел: до потомков (прямой обход, pre-order) или после (обратный, post-order).
def preorder(node): result = [node.value] for child in node.children: result.extend(preorder(child)) return result def postorder(node): result = [] for child in node.children: result.extend(postorder(child)) result.append(node.value) return result print(preorder(root)) # ['A', 'B', 'E', 'F', 'H', 'C', 'D', 'G'] print(postorder(root)) # ['E', 'H', 'F', 'B', 'C', 'G', 'D', 'A']
Прямой обход нужен, когда родителя надо обработать раньше потомков: скопировать дерево, напечатать структуру папок. Обратный — когда ответ для узла зависит от потомков: посчитать размер папки, удалить дерево, вычислить высоту. Функции height и size выше — это и есть обратный обход.
У бинарного дерева есть третий вариант — симметричный обход (in-order): левое поддерево, узел, правое поддерево. В дереве поиска он выдаёт ключи по возрастанию:
def inorder(node): if node is None: return [] return inorder(node.left) + [node.value] + inorder(node.right)
Рекурсию всегда можно заменить явным стеком. Вот прямой обход для дерева-словаря:
def preorder_iterative(tree, root): result = [] stack = [root] while stack: node = stack.pop() result.append(node) stack.extend(reversed(tree[node])) return result print(preorder_iterative(tree, 'A')) # ['A', 'B', 'E', 'F', 'H', 'C', 'D', 'G']
reversed нужен, чтобы первым со стека снялся левый потомок.
В ширину (BFS)
Идём по уровням: сначала корень, потом все узлы глубины 1, потом глубины 2. Вместо стека — очередь.
from collections import deque def levels(root): result = [] queue = deque([root]) while queue: level = [] for _ in range(len(queue)): node = queue.popleft() level.append(node.value) queue.extend(node.children) result.append(level) return result print(levels(root)) # [['A'], ['B', 'C', 'D'], ['E', 'F', 'G'], ['H']]
Внутренний цикл for _ in range(len(queue)) забирает ровно один уровень: в момент его начала в очереди лежат только узлы текущей глубины.
BFS выбирают, когда важны уровни или нужен ближайший к корню узел с каким-то свойством. В остальных случаях DFS обычно короче.
Оба обхода работают за по времени. По памяти DFS требует — глубину стека, BFS — , где — ширина самого большого уровня.
Подробнее, с итеративными версиями всех трёх порядков — в статье про обходы бинарного дерева, а про сами алгоритмы на графах — в DFS и BFS.
Виды деревьев
Деревья различаются двумя вещами: формой (сколько потомков разрешено, как узлы расположены) и правилом, которому подчиняются значения. Форма определяет высоту, правило — то, какие вопросы можно задавать быстро.
Бинарное дерево
У каждого узла не больше двух потомков — левый и правый. Сама по себе форма не даёт никакого порядка, но на ней построено большинство остальных видов. У бинарных деревьев своя терминология: полное, совершенное, сбалансированное, вырожденное. Разбор — в статье про бинарное дерево.
Бинарное дерево поиска (BST)
Бинарное дерево с правилом: всё, что слева от узла, меньше его ключа, всё, что справа, — больше. Благодаря этому при поиске на каждом шаге отбрасывается целое поддерево, как в бинарном поиске по массиву. Поиск, вставка и удаление стоят . Подробно — в статье про бинарное дерево поиска.
Сбалансированные деревья: АВЛ и красно-чёрное
Проблема обычного BST в том, что его высота зависит от порядка вставки. Проверим на тысяче ключей:
import random def insert(root, value): if root is None: return TreeNode(value) node = root while True: if value < node.value: if node.left is None: node.left = TreeNode(value) break node = node.left else: if node.right is None: node.right = TreeNode(value) break node = node.right return root def bst_height(root): best = 0 stack = [(root, 0)] while stack: node, depth = stack.pop() best = max(best, depth) for child in (node.left, node.right): if child: stack.append((child, depth + 1)) return best values = list(range(1000)) sorted_tree = None for x in values: sorted_tree = insert(sorted_tree, x) random.shuffle(values) shuffled_tree = None for x in values: shuffled_tree = insert(shuffled_tree, x) print(bst_height(sorted_tree)) # 999 print(bst_height(shuffled_tree)) # около 20
Те же ключи, вставленные по возрастанию, вытянули дерево в цепочку высотой 999 — по сути в связный список, где поиск стоит . В случайном порядке получилась высота около 20 при теоретическом минимуме 9.
Сбалансированные деревья решают это принудительно: после каждой вставки и удаления они перестраивают себя поворотами так, чтобы высота оставалась .
- АВЛ-дерево держит строгий баланс: высоты левого и правого поддеревьев любого узла отличаются не больше чем на 1. Быстрее на поиске, чуть дороже на вставке.
- Красно-чёрное дерево балансирует мягче, зато реже перестраивается. На нём сделаны
TreeMapв Java и, в распространённых реализациях стандартной библиотеки,std::mapв C++.
B-дерево
Узел хранит не один ключ, а десятки или сотни, и потомков у него столько же. Дерево получается очень низким и широким: до нужной записи среди миллионов — три-четыре перехода. Это важно, когда каждый переход — чтение с диска, поэтому на B-деревьях и их вариантах построены индексы в базах данных.
Двоичная куча
Бинарное дерево с более слабым правилом, чем у BST: родитель не больше своих потомков (или не меньше — для max-кучи). Найти произвольный элемент куча не помогает, зато минимум всегда лежит в корне, а вставка и извлечение стоят . На куче работают очереди с приоритетом, в Python это модуль heapq. Подробности — в статье про двоичную кучу.
Префиксное дерево (trie)
Здесь ключ хранится не в узле, а на пути к нему: каждое ребро — одна буква, путь от корня — префикс слова. Поиск слова стоит , где — его длина, и не зависит от того, сколько слов в словаре. Применяется в автодополнении и проверке орфографии. Разбор — в статье про префиксное дерево.
Дерево отрезков и дерево Фенвика
Деревья, построенные поверх массива. Каждый узел хранит готовый ответ (сумму, минимум, максимум) для своего куска массива, поэтому и запрос на отрезке, и изменение элемента стоят .
- Дерево отрезков универсальнее: подходит для суммы, минимума, НОД и многого другого.
- Дерево Фенвика короче в коде и экономнее по памяти, но рассчитано в основном на суммы.
Обе структуры — скорее олимпиадная тема; на обычном алгоритмическом собеседовании их спрашивают редко.
Дерево и граф
Дерево — частный случай графа: связный граф без циклов. Отсюда и свойство про ребро. Если в структуре есть цикл или у узла два родителя, это уже не дерево, и обходить её надо с множеством посещённых вершин.
В задачах на графах дерево часто задано без выделенного корня — просто списком рёбер. Корнем тогда назначают любую вершину, а чтобы не уйти обратно вверх, в обход передают родителя. Подробнее — в статье про графы.
Где применяются деревья
- Файловые системы. Каталог — внутренний узел, файл — лист. Подсчёт размера папки — обратный обход.
- DOM и интерфейсы. HTML-страница разбирается в дерево элементов, компоненты React и виджеты в мобильных приложениях тоже образуют дерево.
- Компиляторы и интерпретаторы. Код превращается в абстрактное синтаксическое дерево (AST). В Python на него можно посмотреть модулем
ast. - Базы данных. Индексы — B-деревья и их варианты, поэтому поиск по индексированной колонке логарифмический.
- Стандартные библиотеки. Упорядоченные словари и множества, очереди с приоритетом.
- Поиск и автодополнение. Префиксные деревья в подсказках и маршрутизаторах URL.
- Машинное обучение. Деревья решений и ансамбли из них — градиентный бустинг, случайный лес.
- Форматы данных. JSON, XML и YAML описывают именно деревья.
Типичные ошибки
Путают высоту и глубину. Глубина — от корня вниз до узла, высота — от узла вниз до листа. Заодно проверьте, в чём считают: в рёбрах или в узлах.
Забывают про пустое дерево. В бинарных деревьях root может быть None, и любая рекурсивная функция должна начинаться с этой проверки.
Считают, что операции в BST всегда . Они стоят , а без балансировки может дорасти до — пример выше это показывает.
Упираются в лимит рекурсии. В Python глубина рекурсии по умолчанию ограничена примерно тысячей вызовов. На вырожденном дереве из 5000 узлов рекурсивная height упадёт с RecursionError. Лечится итеративным обходом со стеком или sys.setrecursionlimit.
Склеивают списки в рекурсии. Запись inorder(left) + [value] + inorder(right) удобна для объяснения, но копирует списки на каждом уровне и на вырожденном дереве даёт . В рабочем коде передавайте один общий список и добавляйте в него через append.
Обходят граф как дерево. Если в данных возможны циклы, обход без множества посещённых вершин зациклится.
Деревья на собеседованиях
На алгоритмических секциях деревья — одна из самых частых тем, и почти всегда речь о бинарных. Набор идей небольшой:
- рекурсия «ответ для узла из ответов потомков»: высота, проверка баланса, диаметр дерева;
- обход по уровням и его вариации;
- свойство BST: проверка корректности, k-й по величине элемент;
- наименьший общий предок двух узлов;
- сериализация и восстановление дерева по обходам.
Подборка с разборами — в статье задачи на деревья.
Если деревья для вас — первая нелинейная структура, порядок изучения такой: бинарное дерево и обходы, затем дерево поиска, затем куча. Балансировку АВЛ и красно-чёрных деревьев достаточно понимать на уровне идеи — писать повороты на собеседовании просят редко. Как деревья соотносятся с массивами, списками и хеш-таблицами, смотрите в обзоре структур данных.