Структура данных дерево: термины, виды, обходы и код на Python

Дерево как структура данных простыми словами: корень, узлы и листья, высота и глубина, виды деревьев, представление в коде и обходы в глубину и в ширину. Примеры на Python.

14 мин чтенияструктуры данных · деревья · python

Коротко

  • Дерево — структура данных из узлов, связанных отношением «родитель — потомок». Есть один корень, у каждого остального узла ровно один родитель, циклов нет.
  • В дереве из nn узлов всегда n−1n - 1 ребро, а между любыми двумя узлами существует ровно один путь.
  • Главные термины: корень (узел без родителя), лист (узел без потомков), глубина (расстояние от корня до узла), высота (расстояние от узла до самого дальнего листа под ним).
  • Почти все операции в деревьях стоят O(h)O(h), где hh — высота. Поэтому половина «видов деревьев» — это способы удержать высоту около log⁡n\log n.
  • Обойти дерево можно двумя способами: в глубину (DFS, рекурсия или стек) и в ширину (BFS, очередь). Оба работают за O(n)O(n).
Вид дереваЗачем нужноКлючевые операции
Бинарное деревоБазовая форма: не больше двух потомковобход O(n)O(n)
Бинарное дерево поискаХранить ключи упорядоченноO(h)O(h)
АВЛ, красно-чёрноеТо же, но высота гарантированно O(log⁡n)O(\log n)O(log⁡n)O(\log n)
B-деревоИндексы на диске: много ключей в одном узлеO(log⁡n)O(\log n)
Двоичная кучаБыстро доставать минимум или максимумO(log⁡n)O(\log n)
Префиксное дерево (trie)Поиск слов по префиксуO(длина)O(\text{длина})
Дерево отрезков, ФенвикаСуммы и минимумы на отрезках массиваO(log⁡n)O(\log n)

Что такое дерево

Массив и связный список — линейные структуры: у каждого элемента один следующий. Дерево описывает иерархию: у элемента может быть несколько «следующих», и у каждого из них — свои.

Примеры вокруг вас: папки на диске, HTML-документ (DOM), оргструктура компании, оглавление книги, вложенный JSON. Везде одна и та же картина: есть верхний элемент, из него растут вложенные, из тех — следующие.

Формальное определение короткое. Дерево — это набор узлов и рёбер, в котором:

  1. есть один выделенный узел — корень;
  2. у каждого узла, кроме корня, ровно один родитель;
  3. от корня можно дойти до любого узла.

Из этих трёх условий следует всё остальное: в дереве нет циклов, рёбер всегда на одно меньше, чем узлов, а путь между двумя узлами единственный.

В программировании дерево рисуют корнем вверх — в отличие от настоящих деревьев. Дальше будем работать с таким примером:

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 обычно короче.

Оба обхода работают за O(n)O(n) по времени. По памяти DFS требует O(h)O(h) — глубину стека, BFS — O(w)O(w), где ww — ширина самого большого уровня.

Подробнее, с итеративными версиями всех трёх порядков — в статье про обходы бинарного дерева, а про сами алгоритмы на графах — в DFS и BFS.

Виды деревьев

Деревья различаются двумя вещами: формой (сколько потомков разрешено, как узлы расположены) и правилом, которому подчиняются значения. Форма определяет высоту, правило — то, какие вопросы можно задавать быстро.

Бинарное дерево

У каждого узла не больше двух потомков — левый и правый. Сама по себе форма не даёт никакого порядка, но на ней построено большинство остальных видов. У бинарных деревьев своя терминология: полное, совершенное, сбалансированное, вырожденное. Разбор — в статье про бинарное дерево.

Бинарное дерево поиска (BST)

Бинарное дерево с правилом: всё, что слева от узла, меньше его ключа, всё, что справа, — больше. Благодаря этому при поиске на каждом шаге отбрасывается целое поддерево, как в бинарном поиске по массиву. Поиск, вставка и удаление стоят O(h)O(h). Подробно — в статье про бинарное дерево поиска.

Сбалансированные деревья: АВЛ и красно-чёрное

Проблема обычного 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 — по сути в связный список, где поиск стоит O(n)O(n). В случайном порядке получилась высота около 20 при теоретическом минимуме 9.

Сбалансированные деревья решают это принудительно: после каждой вставки и удаления они перестраивают себя поворотами так, чтобы высота оставалась O(log⁡n)O(\log n).

  • АВЛ-дерево держит строгий баланс: высоты левого и правого поддеревьев любого узла отличаются не больше чем на 1. Быстрее на поиске, чуть дороже на вставке.
  • Красно-чёрное дерево балансирует мягче, зато реже перестраивается. На нём сделаны TreeMap в Java и, в распространённых реализациях стандартной библиотеки, std::map в C++.

B-дерево

Узел хранит не один ключ, а десятки или сотни, и потомков у него столько же. Дерево получается очень низким и широким: до нужной записи среди миллионов — три-четыре перехода. Это важно, когда каждый переход — чтение с диска, поэтому на B-деревьях и их вариантах построены индексы в базах данных.

Двоичная куча

Бинарное дерево с более слабым правилом, чем у BST: родитель не больше своих потомков (или не меньше — для max-кучи). Найти произвольный элемент куча не помогает, зато минимум всегда лежит в корне, а вставка и извлечение стоят O(log⁡n)O(\log n). На куче работают очереди с приоритетом, в Python это модуль heapq. Подробности — в статье про двоичную кучу.

Префиксное дерево (trie)

Здесь ключ хранится не в узле, а на пути к нему: каждое ребро — одна буква, путь от корня — префикс слова. Поиск слова стоит O(L)O(L), где LL — его длина, и не зависит от того, сколько слов в словаре. Применяется в автодополнении и проверке орфографии. Разбор — в статье про префиксное дерево.

Дерево отрезков и дерево Фенвика

Деревья, построенные поверх массива. Каждый узел хранит готовый ответ (сумму, минимум, максимум) для своего куска массива, поэтому и запрос на отрезке, и изменение элемента стоят O(log⁡n)O(\log n).

  • Дерево отрезков универсальнее: подходит для суммы, минимума, НОД и многого другого.
  • Дерево Фенвика короче в коде и экономнее по памяти, но рассчитано в основном на суммы.

Обе структуры — скорее олимпиадная тема; на обычном алгоритмическом собеседовании их спрашивают редко.

Дерево и граф

Дерево — частный случай графа: связный граф без циклов. Отсюда и свойство про n−1n - 1 ребро. Если в структуре есть цикл или у узла два родителя, это уже не дерево, и обходить её надо с множеством посещённых вершин.

В задачах на графах дерево часто задано без выделенного корня — просто списком рёбер. Корнем тогда назначают любую вершину, а чтобы не уйти обратно вверх, в обход передают родителя. Подробнее — в статье про графы.

Где применяются деревья

  • Файловые системы. Каталог — внутренний узел, файл — лист. Подсчёт размера папки — обратный обход.
  • DOM и интерфейсы. HTML-страница разбирается в дерево элементов, компоненты React и виджеты в мобильных приложениях тоже образуют дерево.
  • Компиляторы и интерпретаторы. Код превращается в абстрактное синтаксическое дерево (AST). В Python на него можно посмотреть модулем ast.
  • Базы данных. Индексы — B-деревья и их варианты, поэтому поиск по индексированной колонке логарифмический.
  • Стандартные библиотеки. Упорядоченные словари и множества, очереди с приоритетом.
  • Поиск и автодополнение. Префиксные деревья в подсказках и маршрутизаторах URL.
  • Машинное обучение. Деревья решений и ансамбли из них — градиентный бустинг, случайный лес.
  • Форматы данных. JSON, XML и YAML описывают именно деревья.

Типичные ошибки

Путают высоту и глубину. Глубина — от корня вниз до узла, высота — от узла вниз до листа. Заодно проверьте, в чём считают: в рёбрах или в узлах.

Забывают про пустое дерево. В бинарных деревьях root может быть None, и любая рекурсивная функция должна начинаться с этой проверки.

Считают, что операции в BST всегда O(log⁡n)O(\log n). Они стоят O(h)O(h), а hh без балансировки может дорасти до n−1n - 1 — пример выше это показывает.

Упираются в лимит рекурсии. В Python глубина рекурсии по умолчанию ограничена примерно тысячей вызовов. На вырожденном дереве из 5000 узлов рекурсивная height упадёт с RecursionError. Лечится итеративным обходом со стеком или sys.setrecursionlimit.

Склеивают списки в рекурсии. Запись inorder(left) + [value] + inorder(right) удобна для объяснения, но копирует списки на каждом уровне и на вырожденном дереве даёт O(n2)O(n^2). В рабочем коде передавайте один общий список и добавляйте в него через append.

Обходят граф как дерево. Если в данных возможны циклы, обход без множества посещённых вершин зациклится.

Деревья на собеседованиях

На алгоритмических секциях деревья — одна из самых частых тем, и почти всегда речь о бинарных. Набор идей небольшой:

  • рекурсия «ответ для узла из ответов потомков»: высота, проверка баланса, диаметр дерева;
  • обход по уровням и его вариации;
  • свойство BST: проверка корректности, k-й по величине элемент;
  • наименьший общий предок двух узлов;
  • сериализация и восстановление дерева по обходам.

Подборка с разборами — в статье задачи на деревья.

Если деревья для вас — первая нелинейная структура, порядок изучения такой: бинарное дерево и обходы, затем дерево поиска, затем куча. Балансировку АВЛ и красно-чёрных деревьев достаточно понимать на уровне идеи — писать повороты на собеседовании просят редко. Как деревья соотносятся с массивами, списками и хеш-таблицами, смотрите в обзоре структур данных.

Потренироваться в спокойной обстановке

Все задачи

Читать дальше

Все статьи
Алгоритмы и структуры данныхОчередь (queue): структура данных FIFO, операции и реализация на PythonОчередь как структура данных простыми словами: принцип FIFO, операции за O(1), почему list.pop(0) медленный, collections.deque, кольцевая очередь и применение в BFS и планировщиках.Алгоритмы и структуры данныхГраф как структура данных: матрица смежности, список смежности и список рёбер на PythonЧто такое граф в программировании: вершины и рёбра, ориентированный, неориентированный и взвешенный граф. Три представления графа в памяти с кодом на Python и сравнением по памяти и скорости.Алгоритмы и структуры данныхБинарное дерево: что это, виды, листья, полное и сбалансированное деревоБинарное дерево простыми словами: корень, узлы и листья, высота, виды деревьев (строгое, полное, совершенное, сбалансированное, вырожденное) и построение на Python с рабочим кодом.