Деревья (определение и виды) 🌳
Открой любую библиотеку машинного обучения и посмотри на одну из самых популярных моделей — дерево решений. DecisionTreeClassifier из scikit-learn при обучении строит именно то, что называется в его имени: дерево. Каждый внутренний узел этого дерева хранит условие вроде «возраст пациента больше 45?» или «доход клиента выше 60 000?», а каждый лист — итоговое предсказание: класс болезни, вероятность оттока, ожидаемую цену квартиры. Чтобы получить предсказание для нового объекта, модель просто спускается по дереву от корня к листу, на каждом узле сворачивая налево или направо в зависимости от ответа на условие. Это не метафора и не упрощённая иллюстрация — это буквально та же структура данных, узлы, рёбра, листья и обходы которой мы разберём в этом уроке.
До сих пор в этом курсе ты работал с линейными структурами: массивы и списки хранят элементы один за другим, стеки и очереди диктуют порядок доступа к этой линейной последовательности, хеш-таблицы прячут линейную структуру за вычисляемым индексом. Дерево — первая по-настоящему иерархическая структура данных в курсе: у элемента может быть несколько «следующих» элементов сразу, и эта ветвящаяся связность моделирует вещи, которые линейная память моделирует плохо или совсем не моделирует. Файловая система на твоём компьютере — дерево: папка Документы содержит несколько подпапок, каждая из которых может содержать ещё подпапки. Синтаксический разбор предложения в задачах обработки естественного языка — дерево: предложение раскладывается на группы слов, группы — на более мелкие группы, вплоть до отдельных токенов. HTML-страница, которую твой браузер рендерит прямо сейчас, устроена как дерево DOM-элементов. Индексы в промышленных базах данных (B-деревья и их варианты) устроены как деревья, чтобы находить нужную запись среди миллиардов строк за считаные шаги.
Именно поэтому дерево — не просто ещё одна структура данных в списке из двадцати пяти уроков этого блока, а один из самых фундаментальных инструментов информатики в целом. Разобравшись с деревом на уровне терминологии и способов обхода, ты одновременно готовишь себя к трём вещам сразу: к пониманию того, как реально устроена и обучается модель дерева решений (будущие уроки курса), к чтению кода, который работает с иерархическими данными (JSON, XML, AST-деревья компиляторов), и к следующим темам этого блока — бинарным деревьям поиска, сбалансированным деревьям и графам, которые все опираются на аппарат, введённый именно здесь.
🎯 Ты узнаешь:
- Что такое дерево как иерархическая структура данных, и какими терминами описываются его части: корень, узел, лист, ребро, родитель, потомок, поддерево
- Чем отличаются глубина узла и высота дерева, и почему их легко перепутать
- Чем бинарное дерево отличается от n-арного, и почему на практике чаще всего используют именно бинарные деревья
- Как устроен обход дерева в глубину (DFS) и чем принципиально отличаются его прямой, симметричный и обратный варианты
- Как устроен обход дерева в ширину (BFS), и в каких задачах он незаменим там, где DFS не справляется
- Как дерево представляется в памяти компьютера: через узлы с указателями и через плоский массив — и почему для полных деревьев второй способ экономит память
История: откуда это взялось?
Слово «дерево» в математике появилось задолго до компьютеров. В 1857 году английский математик Артур Кэли, изучая химические формулы насыщенных углеводородов, ввёл понятие дерева как связного графа без циклов — именно так молекулы вроде алканов ветвятся от центрального атома углерода, не образуя замкнутых колец. Независимо от Кэли похожую структуру рассматривал ещё в 1847 году немецкий физик Густав Кирхгоф при анализе электрических цепей: чтобы найти независимый набор контуров в сложной схеме, ему потребовалось выделить «остовное дерево» графа схемы — минимальный набор проводов, связывающий все узлы без единого замкнутого контура. Оба пришли к одной и той же математической конструкции с разных сторон — из химии и из электротехники, — и оба обнаружили, что связный граф без циклов обладает удивительно чистыми и полезными свойствами: между любыми двумя узлами существует ровно один путь.
Когда в середине XX века появились первые языки программирования, работающие со сложными структурами данных, математическое дерево естественно перекочевало в информатику. В 1958 году в языке Lisp, созданном Джоном Маккарти, списки и деревья стали основным способом представления не только данных, но и самого кода программы — знаменитые вложенные скобки Lisp — это, по сути, запись дерева выражений в текстовом виде. Тогда же начала формироваться терминология, которой мы пользуемся до сих пор: «корень» (root), «лист» (leaf), «узел» (node) — заимствованная из ботаники метафора живого дерева, только перевёрнутого: у компьютерного дерева корень традиционно рисуют сверху, а листья — снизу.
Практическая мощь деревьев по-настоящему раскрылась в 1970-х годах, когда Рудольф Байер и Эд Маккрейт изобрели B-дерево (1972) — специализированный вид сбалансированного дерева, спроектированный именно для хранения данных на медленных дисковых накопителях, и с тех пор лежащий в основе индексов практически любой промышленной базы данных, от PostgreSQL до файловых систем NTFS и ext4. А в 1980-х деревья пришли и в машинное обучение: в 1986 году Росс Куинлан опубликовал алгоритм ID3, строящий дерево решений для классификации на основе информационного выигрыша, а в 1984 году группа статистиков во главе с Лео Брейманом описала родственный подход CART (Classification and Regression Trees), который до сих пор — почти в неизменном виде — реализован в sklearn.tree.DecisionTreeClassifier и лежит в основе ансамблевых моделей вроде случайного леса и градиентного бустинга. Так одна и та же математическая идея XIX века — связный граф без циклов — за полтора столетия прошла путь от химических формул до самой интерпретируемой модели машинного обучения.
Терминология и структура дерева
Интуиция: генеалогическое древо и файловая система
Представь семейное древо: на вершине — общий предок, от него отходят линии к детям, от каждого ребёнка — линии к его собственным детям, и так далее вниз по поколениям. У любого человека на этой схеме (кроме самого верхнего предка) есть ровно один родитель на схеме, но может быть несколько детей. У человека без собственных детей линии вниз не идут — он «конечная точка» ветви. Ровно та же картина — в файловой системе твоего компьютера: корневая папка (диск C: или /) содержит вложенные папки, те — свои вложенные папки и файлы, а обычный файл (не папка) — это конечная точка, дальше идти некуда.
Дерево как структура данных формализует именно эту интуицию: единственная точка входа наверху, ветвящиеся связи вниз, и никаких «коротких путей» в сторону или назад — из одного узла к другому есть ровно один способ добраться, двигаясь только по рёбрам дерева.
Формальное определение
Определение: Деревом называется структура данных, состоящая из конечного множества узлов (nodes), связанных рёбрами (edges), при этом:
- существует ровно один выделенный узел без родителя — корень (root) дерева;
- каждый узел, кроме корня, имеет ровно одного родителя (parent) — узел, из которого к нему идёт ребро;
- узел может иметь произвольное число потомков (children) — узлов, для которых он является родителем (в том числе ноль потомков);
- между корнем и любым другим узлом существует ровно один путь по рёбрам дерева — то есть дерево не содержит циклов.
Узел без потомков называется листом (leaf). Узел, имеющий хотя бы одного потомка, называется внутренним узлом (internal node). Число потомков узла называется его степенью (degree).
Из связки «узел вместе со всеми его потомками, потомками потомков и так далее» рождается ещё одно ключевое понятие: поддерево (subtree). Любой узел дерева, если посмотреть только на него самого и всё, что находится ниже него, сам образует корректное дерево меньшего размера — это и есть его поддерево. Такая самоподобная структура (дерево состоит из вложенных деревьев меньшего размера) — не просто красивое наблюдение, а причина, по которой почти все алгоритмы на деревьях естественно пишутся рекурсивно: обработать дерево — значит обработать его корень и рекурсивно обработать каждое из поддеревьев, растущих из его потомков.
Два родственных, но разных понятия, которые постоянно путают: глубина узла (depth) и высота дерева (height).
Определение: Глубина узла — это число рёбер на пути от корня до этого узла. Глубина самого корня равна $0$. Высота узла — это число рёбер на самом длинном пути от этого узла вниз до любого листа в его поддереве; высота листа равна $0$. Высотой дерева называется высота его корня — то есть глубина самого глубокого листа во всём дереве.
Разница на пальцах: глубина отвечает на вопрос «как далеко я спустился от вершины до этого конкретного узла», а высота — на вопрос «сколько ещё можно спускаться вниз от этого узла». У корня глубина всегда $0$, а высота может быть какой угодно большой — в зависимости от того, насколько дерево разрослось вниз.
Примеры с разбором
Пример 1 (лёгкий). Смоделируем узел дерева на Python и построим маленькое дерево, соответствующее структуре папок Документы → (Работа, Личное) → Работа → (Отчёты, Презентации).
class TreeNode:
def __init__(self, name):
self.name = name
self.children = []
def add_child(self, child):
self.children.append(child)
# Строим дерево файловой системы
root = TreeNode("Документы")
work = TreeNode("Работа")
personal = TreeNode("Личное")
root.add_child(work)
root.add_child(personal)
reports = TreeNode("Отчёты")
presentations = TreeNode("Презентации")
work.add_child(reports)
work.add_child(presentations)
Здесь root — корень дерева (глубина $0$), work и personal — его прямые потомки (глубина $1$), reports и presentations — потомки узла work (глубина $2$) и одновременно листья, поскольку у них нет собственных children. Узел personal — тоже лист (список children у него пуст), хотя и находится на той же глубине, что и work, у которого есть потомки. Поддерево, растущее из узла work, — это корректное дерево само по себе: у него свой корень (work) и два листа (reports, presentations).
Пример 2 (средний). Оргструктура компании: генеральный директор (CEO) руководит двумя вице-президентами (VP Engineering и VP Sales), у VP Engineering — три тимлида, у каждого тимлида — по четыре разработчика, у VP Sales — два менеджера по продажам без подчинённых. Найдём глубину узла «тимлид» и высоту всего дерева.
Путь от корня (CEO) до тимлида: CEO → VP Engineering → тимлид — это два ребра, значит глубина узла «тимлид» равна $2$. Самый длинный путь вниз от корня: CEO → VP Engineering → тимлид → разработчик — три ребра, и дальше вниз пути нет (разработчик — лист), значит высота всего дерева равна $3$. Обрати внимание: ветка через VP Sales короче (CEO → VP Sales → менеджер, всего два ребра), но высота дерева определяется самой длинной веткой, а не средней или самой короткой — это стандартная и важная деталь определения.
Пример 3 (сложный). Дерево решений для упрощённой медицинской диагностики: корень — условие «температура выше 38°?», если да — переход к узлу «кашель есть?», если нет от корня — сразу лист «здоров». От узла «кашель есть?»: если да — лист «вероятно ОРВИ», если нет — узел «сыпь есть?», от которого: да — лист «проверить аллергию», нет — лист «наблюдать». Определим все листья, глубину каждого листа и высоту дерева.
Обозначим корень как узел A (глубина $0$). Его дети: B = «кашель есть?» (глубина $1$) и лист «здоров» (глубина $1$). Дети узла B: лист «вероятно ОРВИ» (глубина $2$) и узел C = «сыпь есть?» (глубина $2$). Дети узла C: лист «проверить аллергию» (глубина $3$) и лист «наблюдать» (глубина $3$). Итого четыре листа с глубинами $1, 2, 3, 3$. Высота дерева равна глубине самого глубокого листа, то есть $3$. Заметь, что в этом дереве, как и почти в любом настоящем дереве решений, глубины листьев неодинаковы — некоторые прогнозы модель делает после одной проверки, другие требуют цепочки из нескольких условий, и именно длина этой цепочки для конкретного объекта определяет, насколько быстро модель приняла решение о нём.
Почему это важно. Вся терминология этого раздела — не формальность ради формальности, а рабочий словарь, которым описывается и обучение, и инференс дерева решений. Когда ты задаёшь гиперпараметр max_depth в DecisionTreeClassifier, ты буквально ограничиваешь высоту дерева, которое алгоритм имеет право построить, — а значит, ограничиваешь и максимальную длину цепочки условий, которую модель может применить к одному объекту. Когда говорят о «переобученном» дереве решений, чаще всего имеют в виду дерево с чрезмерно большой высотой: оно нарастило столько узлов и листьев, что запомнило шум обучающей выборки вместо общей закономерности. Понимание разницы между глубиной конкретного узла и высотой всего дерева — первый шаг к осмысленной настройке этого гиперпараметра, а не подбору его значения вслепую перебором.
Виды деревьев: бинарные и n-арные
Интуиция: сколько развилок допускает узел
Определение дерева из предыдущего раздела ничего не говорит о том, сколько потомков может быть у одного узла — теоретически их может быть сколько угодно. На практике оказывается крайне полезно зафиксировать это число заранее, потому что это резко упрощает и код, и математический анализ структуры. Самый важный частный случай — когда у узла не больше двух потомков: тогда для каждого потомка можно однозначно сказать, «левый» он или «правый», и вся структура становится удобно описываемой парой ссылок в каждом узле вместо произвольного списка.
Формальное определение
Определение: Бинарным деревом (binary tree) называется дерево, в котором у каждого узла не более двух потомков, традиционно называемых левым потомком (left child) и правым потомком (right child). N-арным деревом (n-ary tree), или деревом общего вида, называется дерево, в котором у узла может быть произвольное число потомков, не более некоторого фиксированного $n$ (при $n$-неограниченном — просто «общее дерево», general tree).
Частные виды бинарного дерева: полное бинарное дерево (complete binary tree) — все уровни, кроме, возможно, последнего, заполнены полностью, а узлы последнего уровня расположены как можно левее; идеальное бинарное дерево (perfect binary tree) — все внутренние узлы имеют ровно двух потомков, а все листья находятся на одной и той же глубине; вырожденное дерево (degenerate tree) — у каждого узла не более одного потомка, из-за чего дерево фактически превращается в связный список.
Разница в терминологии здесь важна: «полное» и «идеальное» бинарные деревья — не синонимы, хотя их часто путают. Идеальное дерево — самый строгий случай: оно симметрично заполнено на всех уровнях. Полное дерево допускает недозаполненный последний уровень, но требует, чтобы пустые места были только справа — это именно то свойство, которое делает возможным компактное представление дерева в обычном массиве, о чём пойдёт речь в последнем разделе урока.
Примеры с разбором
Пример 1 (лёгкий). Бинарное дерево сравнений: узел хранит число, левый потомок — число меньше родителя, правый — больше. Реализуем узел и вставим последовательность чисел $[8, 3, 10, 1, 6]$.
class BinaryNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def insert(node, value):
if node is None:
return BinaryNode(value)
if value < node.value:
node.left = insert(node.left, value)
else:
node.right = insert(node.right, value)
return node
root = None
for v in [8, 3, 10, 1, 6]:
root = insert(root, v)
# root.value == 8
# root.left.value == 3, root.right.value == 10
# root.left.left.value == 1, root.left.right.value == 6
Здесь у каждого узла ровно две именованные ссылки — left и right — вместо произвольного списка children. Это и есть отличительный признак кода для бинарного дерева: явные поля вместо коллекции. Подробный разбор именно такого дерева (бинарного дерева поиска, с гарантией порядка «левое меньше, правое больше») — тема следующего урока 257; здесь важно только увидеть механику бинарного узла.
Пример 2 (средний). N-арное дерево файловой системы из предыдущего раздела — каноничный пример дерева общего вида: у папки Документы было два потомка, у Работа — тоже два, но в реальной файловой системе у папки может быть и ноль, и пять, и сто вложенных элементов — никакого ограничения в два потомка нет. Для такого дерева естественная реализация узла — с полем children, хранящим список произвольной длины, как в примере 1 предыдущего раздела, а не пара left/right. Попытка «впихнуть» дерево файловой системы в бинарное представление потребовала бы либо искусственного ограничения (не более двух файлов в папке — абсурд), либо трюка «первый потомок — следующий потомок» (left-child right-sibling representation), где left ссылается на первого ребёнка узла, а right — на следующего по порядку сиблинга. Такой трюк действительно существует и позволяет представить произвольное n-арное дерево через бинарные узлы, но он усложняет код и используется редко — обычно проще напрямую хранить список потомков.
Пример 3 (сложный). Дерево решений из ML-практики почти всегда строят как бинарное, даже когда признак, по которому идёт разбиение, категориальный и принимает больше двух значений. Например, признак «город» с тремя значениями Москва, Питер, `Казань» в CART не превращается в узел с тремя потомками — вместо этого алгоритм на каждом шаге ищет бинарное разбиение вида «город = Москва?» (да/нет) или группирует категории в два подмножества «{Москва, Питер} против {Казань}» и снова проверяет принадлежность одному из двух подмножеств. Почему так: бинарное дерево математически проще анализировать (у него ровно $2^h$ листьев на глубине $h$ в идеальном случае, для него хорошо изучены алгоритмы балансировки — уроки 257–258), а любое n-арное разбиение всегда можно эмулировать последовательностью бинарных разбиений, но не наоборот. Поэтому почти все промышленные реализации деревьев решений (scikit-learn, XGBoost, LightGBM) строят именно бинарные деревья, даже когда исходная предметная область выглядит «n-арно».
Почему это важно. Выбор между бинарным и n-арным деревом — это не вопрос вкуса, а вопрос компромисса между простотой структуры и естественностью модели предметной области. Файловые системы, синтаксис языков разметки (XML/HTML), организационные структуры — всё это по природе n-арные иерархии, и пытаться силой сделать их бинарными без необходимости усложнило бы код. А там, где важны предсказуемая математика структуры и эффективные алгоритмы поиска и балансировки — бинарные деревья поиска, кучи, деревья решений — практически всегда выбирают именно бинарный вариант, даже ценой дополнительного шага «разложить n-арный выбор на последовательность бинарных».
Обход в глубину (DFS): прямой, симметричный и обратный порядок
Интуиция: погружение в лабиринт
Представь, что дерево — это лабиринт с развилками, и тебе нужно посетить каждую комнату (узел) ровно один раз. Обход в глубину (Depth-First Search, DFS) — это стратегия «иди как можно дальше вглубь одной веткой, и только упёршись в тупик — возвращайся и пробуй следующую». Ты никогда не «распыляешься» сразу на несколько соседних комнат — сначала полностью исследуешь одну ветку до конца, и только потом переходишь к соседней. Ключевой вопрос, который различает три варианта DFS, — не в какую сторону ты идёшь (это всегда «вглубь»), а в какой момент по отношению к своим потомкам ты «обрабатываешь» (например, печатаешь) сам узел: до того, как спустился к детям, между спуском к левому и к правому ребёнку, или уже после того, как обошёл обоих детей.
Формальное определение
Определение: Пусть узел дерева $N$ имеет потомков (для бинарного случая — $\mathrm{left}$ и $\mathrm{right}$). Три классических варианта обхода в глубину для бинарного дерева:
- Прямой обход (preorder, «корень — левое — правое»): сначала обрабатывается сам узел $N$, затем рекурсивно обходится его левое поддерево, затем рекурсивно — правое.
- Симметричный обход (inorder, «левое — корень — правое»): сначала рекурсивно обходится левое поддерево, затем обрабатывается сам узел $N$, затем рекурсивно — правое поддерево.
- Обратный обход (postorder, «левое — правое — корень»): сначала рекурсивно обходятся оба поддерева (левое, затем правое), и только после этого обрабатывается сам узел $N$.
Для n-арного дерева определения прямого и обратного обхода обобщаются напрямую (узел обрабатывается до или после рекурсивного обхода всех его потомков по порядку), а симметричный обход в чистом виде определён только для бинарных деревьев, поскольку требует единственной, однозначной точки «между» потомками.
Все три варианта реализуются практически одинаковым кодом — меняется только момент, в который строка process(node) вставлена относительно двух рекурсивных вызовов:
def preorder(node, out):
if node is None:
return
out.append(node.value) # обработка ДО спуска
preorder(node.left, out)
preorder(node.right, out)
def inorder(node, out):
if node is None:
return
inorder(node.left, out)
out.append(node.value) # обработка МЕЖДУ поддеревьями
inorder(node.right, out)
def postorder(node, out):
if node is None:
return
postorder(node.left, out)
postorder(node.right, out)
out.append(node.value) # обработка ПОСЛЕ спуска
Примеры с разбором
Пример 1 (лёгкий). Бинарное дерево из предыдущего раздела, построенное вставкой чисел $[8, 3, 10, 1, 6]$: корень $8$, слева $3$ (у которого слева $1$, справа $6$), справа $10$ (без потомков). Найдём результат всех трёх обходов.
Прямой обход (корень — левое — правое): $8 \to 3 \to 1 \to 6 \to 10$. Логика: печатаем $8$, спускаемся в левое поддерево (с корнем $3$) — печатаем $3$, спускаемся в его левое поддерево — печатаем $1$ (лист, возвращаемся), возвращаемся к $3$, идём в его правое поддерево — печатаем $6$ (лист), возвращаемся к $8$, идём в правое поддерево — печатаем $10$ (лист). Итог: $[8, 3, 1, 6, 10]$.
Симметричный обход (левое — корень — правое) для этого же дерева даёт отсортированную последовательность: $[1, 3, 6, 8, 10]$ — это не совпадение, а прямое следствие того, что дерево строилось как дерево поиска («левое меньше, правое больше»); симметричный обход такого дерева всегда возвращает элементы по возрастанию.
Обратный обход (левое — правое — корень) даёт $[1, 6, 3, 10, 8]$ — каждый узел появляется в выводе только после того, как оба его поддерева полностью обработаны, поэтому корень $8$ оказывается в самом конце последовательности.
Пример 2 (средний, вычисление арифметического выражения). Дерево выражения $(3 + 4) \times 5$ строится так: корень — узел ×, его левое поддерево — узел + с потомками-листьями $3$ и $4$, его правое поддерево — лист $5$. Найдём результаты обходов и объясним, какой из них восстанавливает исходную запись выражения.
Симметричный обход даёт 3 + 4 × 5 (в порядке «левое — корень — правое»: сначала левое поддерево + само даёт 3 + 4, затем корень ×, затем правое поддерево 5) — именно так дерево выражения превращается обратно в привычную инфиксную запись (с той оговоркой, что без скобок теряется исходный приоритет операций — на практике при печати добавляют скобки вокруг каждого поддерева-операции). Обратный обход даёт 3 4 + 5 × — это в точности постфиксная запись (обратная польская нотация), которую калькуляторы и стековые вычислительные машины умеют вычислять без единой скобки, читая слева направо и используя стек (урок 253): встретил число — положил в стек, встретил операцию — вынул два верхних числа, применил операцию, результат вернул в стек. Прямой обход даёт × + 3 4 5 — префиксную запись, на которой построены, например, S-выражения языка Lisp.
Пример 3 (сложный, извлечение правил из дерева решений). Возьмём дерево решений о выдаче кредита: корень — «доход > 50 000?», левый потомок (нет) — лист «отказ», правый потомок (да) — узел «кредитная история хорошая?», у которого левый потомок (нет) — лист «отказ», правый потомок (да) — лист «одобрение». Требуется вывести все правила вида «условие И условие → решение» для каждого листа, используя обход дерева.
Здесь естественная стратегия — модифицированный прямой обход с накоплением пути: спускаясь к каждому узлу, дописываем в список условие, которое привело именно в эту сторону (для левого потомка — «не выполнено», для правого — «выполнено»), а достигнув листа — печатаем накопленный путь целиком как правило и явно «откатываем» последнее добавленное условие при возврате из рекурсии (это тот самый паттерн backtracking, естественно возникающий из структуры DFS):
def extract_rules(node, path, rules):
if node.is_leaf:
rules.append(" И ".join(path) + f" → {node.decision}")
return
path.append(f"{node.condition} = да")
extract_rules(node.right, path, rules)
path.pop()
path.append(f"{node.condition} = нет")
extract_rules(node.left, path, rules)
path.pop()
Результат для нашего дерева: доход > 50000 = да И кредитная история хорошая = да → одобрение, доход > 50000 = да И кредитная история хорошая = нет → отказ, доход > 50000 = нет → отказ. Это ровно тот механизм, которым интерпретируемость дерева решений превращается из абстрактного свойства в конкретный, читаемый человеком список правил «если... и... то...» — одна из главных причин, по которой дерево решений остаётся популярным там, где важна объяснимость модели, в отличие от менее прозрачных алгоритмов.
Почему это важно. Три порядка DFS — не три произвольные вариации ради разнообразия, а три инструмента под три разные задачи. Прямой обход используют, когда нужно обработать узел раньше его содержимого — скопировать дерево, сериализовать его в текст с сохранением структуры, извлечь правила «сверху вниз», как в примере 3. Симметричный обход для бинарного дерева поиска — единственный способ получить элементы в отсортированном порядке за один линейный проход, без отдельной сортировки (подробнее — урок 257). Обратный обход используют, когда узел нельзя обработать, пока не обработаны оба его поддерева, — классический случай: безопасное удаление дерева (нельзя освободить память родителя, пока не освобождена память детей) или вычисление агрегированных величин снизу вверх (например, размер поддерева, зависящий от размеров поддеревьев потомков).
Обход в ширину (BFS) и представление дерева в памяти
Интуиция: расходящиеся круги по воде
Если DFS — это погружение в одну ветку лабиринта до упора, то обход в ширину (Breadth-First Search, BFS) — это круги на воде от брошенного камня: сначала полностью «накрывается» ближайшее кольцо вокруг точки падения, потом следующее, потом ещё следующее. Применительно к дереву: сначала обрабатывается корень, затем все узлы на глубине $1$, затем все узлы на глубине $2$, и так далее — уровень за уровнем, никогда не забегая на следующий уровень, пока текущий не пройден полностью. Такой обход ещё называют «обходом по уровням» (level-order traversal).
Формальное определение
Определение: Обход в ширину посещает узлы дерева уровень за уровнем, от корня к листьям, слева направо на каждом уровне. Реализуется с помощью очереди (урок 253, FIFO): корень кладётся в очередь; далее, пока очередь не пуста, из неё извлекается узел, обрабатывается, а все его потомки добавляются в конец очереди.
from collections import deque
def bfs(root):
if root is None:
return []
result = []
queue = deque([root])
while queue:
node = queue.popleft()
result.append(node.value)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
Именно очередь, а не стек, делает обход «широким»: очередь возвращает элементы в том же порядке, в каком они были добавлены (FIFO), поэтому все узлы одного уровня извлекаются и обрабатываются раньше, чем в очередь попадёт хотя бы один узел следующего уровня. Если вместо очереди по ошибке использовать стек, обход неожиданно превратится в один из вариантов DFS — разница между BFS и DFS при итеративной (нерекурсивной) реализации сводится ровно к выбору структуры данных для хранения «узлов на будущее».
Второй вопрос этого раздела — как дерево вообще хранится в памяти компьютера. Есть два принципиально разных подхода.
Определение: Связное представление (linked representation) хранит дерево как набор объектов-узлов, каждый из которых содержит данные и явные ссылки (указатели) на своих потомков — ровно так, как были устроены все узлы
TreeNodeиBinaryNodeв примерах этого урока. Массивное представление (array representation) хранит только полные или идеальные бинарные деревья, записывая узлы в плоский массив по уровням слева направо: для узла с индексом $i$ (нумерация с нуля) его левый потомок находится по индексу $2i+1$, правый потомок — по индексу $2i+2$, а родитель — по индексу $\lfloor (i-1)/2 \rfloor$.
Примеры с разбором
Пример 1 (лёгкий). Для дерева из раздела про DFS (корень $8$; слева $3$ с детьми $1$ и $6$; справа $10$) выполним обход в ширину и сравним с прямым обходом (preorder).
BFS: сначала корень $8$ (единственный узел глубины $0$), затем оба узла глубины $1$ слева направо — $3$, $10$, затем оба узла глубины $2$ — $1$, $6$ (дети узла $3$; у узла $10$ детей нет). Итог: $[8, 3, 10, 1, 6]$. Сравним с прямым обходом из примера 1 предыдущего раздела: $[8, 3, 1, 6, 10]$. Числа те же самые, но порядок другой: прямой обход сразу «нырнул» в левое поддерево узла $3$ и добрался до $1$ и $6$ раньше, чем вообще посетил узел $10$ на глубине $1$ — ровно та разница между «вглубь одной веткой» и «по уровням», о которой шла речь в интуиции.
Пример 2 (средний, массивное представление кучи). Идеальное бинарное дерево с семью узлами и значениями по уровням $[50, 30, 70, 20, 40, 60, 80]$ (корень $50$, следующий уровень $30$ и $70$, следующий — $20, 40, 60, 80$). Запишем его в массив и найдём индексы левого и правого потомков узла со значением $30$.
Массив по определению: tree = [50, 30, 70, 20, 40, 60, 80], где индекс $i=0$ — корень $50$. Значение $30$ стоит по индексу $i=1$. Левый потомок: $2 \cdot 1 + 1 = 3$, то есть tree[3] = 20. Правый потомок: $2 \cdot 1 + 2 = 4$, то есть tree[4] = 40. Проверим обратную формулу для родителя узла $60$ (индекс $i=5$): $\lfloor (5-1)/2 \rfloor = \lfloor 4/2 \rfloor = 2$, то есть tree[2] = 70 — действительно, $70$ является родителем и $60$, и $80$ в этом дереве. Никаких явных ссылок left/right/parent не хранится вообще — вся структура дерева полностью выражена только позицией элемента в обычном списке Python.
Пример 3 (сложный, память и границы применимости). Оценим, сколько памяти займёт хранение идеального бинарного дерева высоты $h=20$ (около миллиона узлов) двумя способами, и объясним, почему массивное представление неприменимо к дереву решений из практики ML.
Число узлов в идеальном бинарном дереве высоты $h$: $2^{h+1}-1$, при $h=20$ это $2^{21}-1 = 2\,097\,151$ узел. В связном представлении каждый узел — отдельный Python-объект с накладными расходами на заголовок объекта и минимум два указателя (left, right), что на 64-битной системе даёт ориентировочно от нескольких десятков до сотни байт на узел (точная цифра зависит от языка и реализации) — то есть порядка сотен мегабайт для двух миллионов узлов. В массивном представлении — это один сплошной массив на $2\,097\,151$ элементов, без единого указателя между узлами, с накладными расходами лишь на сам массив: экономия в разы, а главное — превосходная локальность в кэше процессора, потому что соседние по логике узлы физически соседствуют в памяти. Но у этой экономии есть жёсткая цена: массивное представление работает только для деревьев, близких к идеальным или полным — формулы $2i+1$, $2i+2$ молчаливо предполагают, что «дырок» в дереве почти нет. Дерево решений, обученное на реальных данных, почти всегда несбалансированное: одни ветки растут глубоко, другие обрываются листом уже на первом уровне — записать такое дерево в плотный массив по этим формулам означало бы оставлять гигантские пустые промежутки там, где ветки короче остальных, сводя на нет всю экономию памяти. Поэтому реальные реализации дерева решений (как и любые несбалансированные деревья) почти всегда используют связное представление, а массивное представление берегут для структур, у которых полнота дерева гарантирована по построению, — классический пример которых мы разберём в отдельном будущем уроке: двоичная куча (binary heap).
Почему это важно. BFS и способ хранения дерева — не два случайных вопроса под одним заголовком, а тесно связанные вещи: BFS естественно раскладывает дерево именно по уровням, а массивное представление — это ровно то же самое разложение по уровням, «застывшее» в виде индексов массива. Выбор между BFS и DFS на практике определяется задачей: искать кратчайший путь или ближайший подходящий узел (например, ближайшего свободного слота в структуре) нужно через BFS, потому что он гарантированно находит решение на минимальной глубине первым; обходить всё дерево целиком, извлекать правила, считать агрегаты снизу вверх — задачи для DFS. А выбор представления в памяти определяется формой дерева: плотные, предсказуемо заполненные структуры выигрывают от компактного массива, рыхлые и несбалансированные — от гибкости связного представления с явными указателями.
Практика: 30 заданий
Базовые (задания 1–10)
Задание 1. Дано дерево: корень A, у него дети B и C, у B — ребёнок D (лист), у C детей нет (лист). Назови корень, всех внутренних узлов и всех листьев.
Задание 2. Для дерева из задания 1 найди глубину узла D и высоту всего дерева.
Задание 3. Бинарное дерево: корень $5$, левый потомок $3$, правый потомок $8$, у $3$ — правый потомок $4$ (без других детей). Является ли это дерево идеальным бинарным деревом? Обоснуй.
Задание 4. N-арное дерево категорий интернет-магазина: «Электроника» имеет потомков «Телефоны», «Ноутбуки», «Наушники»; «Одежда» имеет потомков «Мужская», «Женская». Оба — потомки корня «Каталог». Сколько потомков у корня и чему равна степень узла «Электроника»?
Задание 5. Дано бинарное дерево: корень $1$, левый потомок $2$, правый потомок $3$; у $2$ — левый потомок $4$; у $4$ — левый потомок $5$ (без других детей на этой ветке). Выпиши результат прямого обхода (preorder).
Задание 6. Для дерева из задания 5 выпиши результат симметричного обхода (inorder).
Задание 7. Для дерева из задания 5 выпиши результат обратного обхода (postorder).
Задание 8. Дано полное бинарное дерево из пяти узлов со значениями по уровням $[10, 20, 30, 40, 50]$. Запиши его как массив с индексацией от нуля и найди значения левого и правого потомков узла с индексом $1$.
Задание 9. Для дерева из задания 8 найди индекс родителя узла с индексом $4$.
Задание 10. Дано дерево из задания 5. Выполни обход в ширину (BFS) и сравни его с прямым обходом (preorder) из задания 5 — совпадают ли результаты?
Средние (задания 11–20)
Задание 11. Бинарное дерево построено вставкой чисел $[15, 7, 20, 3, 10, 18, 25]$ по правилу дерева поиска (меньше — влево, не меньше — вправо, как в примере 1 раздела про виды деревьев). Нарисуй (опиши словами) структуру дерева и найди его высоту.
Задание 12. Для дерева из задания 11 выпиши результат симметричного обхода. Что особенного в этой последовательности?
Задание 13. N-арное дерево: корень имеет $3$ потомков, у каждого из этих трёх — по $2$ потомка, у которых потомков нет. Сколько всего узлов в дереве и сколько из них — листья?
Задание 14. Идеальное бинарное дерево имеет высоту $h=4$. Найди общее число узлов и число листьев в нём, используя формулы $2^{h+1}-1$ и $2^h$.
Задание 15. Дерево решений глубины $3$ (все листья строго на глубине $3$, дерево идеальное бинарное). Сколько различных путей от корня до листа существует, и что означает каждый такой путь в терминах модели?
Задание 16. Дерево арифметического выражения $(7 - 2) \times (4 + 1)$: корень ×, слева поддерево - с листьями $7, 2$, справа поддерево + с листьями $4, 1$. Выпиши обратный обход (postorder) и объясни, как по нему вычислить значение выражения с помощью стека.
Задание 17. Массивное представление хранит полное бинарное дерево tree = [4, 9, 2, 15, 6, 8] (индексы $0..5$). Нарисуй словами структуру дерева по уровням и укажи, у какого узла нет пары (только один потомок).
Задание 18. В дереве из задания 17 найди индекс родителя для узла со значением $6$ и для узла со значением $8$, используя формулу $\lfloor (i-1)/2 \rfloor$.
Задание 19. Дерево решений с четырьмя листьями на глубинах $2, 2, 3, 4$ соответственно. Чему равна высота этого дерева, и почему нельзя вычислить её как среднее арифметическое глубин листьев?
Задание 20. Дан код обхода:
def mystery(node, out):
if node is None:
return
mystery(node.right, out)
out.append(node.value)
mystery(node.left, out)
Как называется этот обход и чем он отличается от стандартного симметричного (inorder)? Что он вернёт для дерева поиска, отсортированного по возрастанию слева направо?
Сложные (задания 21–30)
Задание 21. Докажи, что в любом бинарном дереве высоты $h$ число узлов не может превышать $2^{h+1}-1$.
Задание 22. Напиши рекурсивную функцию, вычисляющую высоту произвольного бинарного дерева, и вычисли высоту руками для дерева: корень $A$, левый потомок $B$ (у которого левый потомок $C$, у $C$ нет детей), правый потомок $A$ — узел $D$ (лист).
Задание 23. Докажи, что при обходе inorder бинарного дерева поиска (с инвариантом «всё в левом поддереве меньше корня, всё в правом — больше») элементы всегда выводятся в строго возрастающем порядке.
Задание 24. Дерево решений с $L$ листьями, каждый на глубине не больше $D$. Оцени максимальное число внутренних узлов дерева через $L$ и $D$, если дерево бинарное.
Задание 25. Реализуй функцию count_nodes(node), возвращающую общее число узлов бинарного дерева, используя обратный обход (postorder) в качестве идеи рекурсии, и объясни, почему для этой задачи обратный порядок обхода естественен.
Задание 26. Дерево решений глубины $D$ используется для инференса одного объекта. Сколько условий (сравнений) в худшем случае будет проверено при классификации одного объекта, и как это связано с понятием высоты дерева?
Задание 27. Сравни асимптотическую сложность поиска узла по значению в связном представлении бинарного дерева поиска высоты $h$ (обычный обход по ссылкам) и в массивном представлении того же дерева (если бы оно было полным). Совпадает ли сложность, и почему массивное представление здесь не даёт выигрыша по скорости поиска?
Задание 28. N-арное дерево представлено связным способом, где у каждого узла список children произвольной длины. Напиши функцию depth_sum(node), возвращающую сумму глубин всех узлов дерева (глубина корня $=0$), используя обход в ширину.
Задание 29. Объясни, почему рекурсивная реализация DFS может вызвать переполнение стека вызовов (RecursionError в Python) на очень несбалансированном дереве, и как этого избежать, используя явный стек вместо рекурсии.
Задание 30. Дерево решений имеет $1000$ листьев и является строго бинарным (у каждого внутреннего узла ровно два потомка). Известно, что дерево крайне несбалансированное: половина листьев на глубине $5$, другая половина — на глубине $500$. Возможна ли такая конфигурация, и что она говорит о качестве модели с точки зрения переобучения?
Частые ошибки
❌ Ошибка: «Глубина узла и высота узла — это одно и то же» ✅ Правильно: Глубина узла считается сверху вниз — от корня до узла; высота узла считается снизу вверх — от узла до самого дальнего листа в его поддереве 💡 Почему: У одного и того же узла глубина и высота почти всегда разные числа: у корня глубина всегда $0$, но высота равна высоте всего дерева; у листа высота всегда $0$, но глубина может быть какой угодно. Смешение этих понятий — источник ошибок в задачах на подсчёт числа узлов или оценку сложности алгоритмов на дереве.
❌ Ошибка: «Высота дерева — это среднее арифметическое глубин всех его листьев» ✅ Правильно: Высота дерева — это глубина самого глубокого листа, то есть максимум, а не среднее 💡 Почему: Задание 19 практики показало это явно: высота дерева с листьями на глубинах $2, 2, 3, 4$ равна $4$, а не среднему $2{,}75$. Высота отвечает на вопрос о худшем случае (максимальная глубина погружения), а не о типичном.
❌ Ошибка: «Дерево можно всегда компактно хранить в массиве, как кучу» ✅ Правильно: Массивное представление эффективно только для полных или идеальных деревьев; для произвольного несбалансированного дерева (в том числе почти любого реального дерева решений) оно приводит к огромным пустым промежуткам в массиве 💡 Почему: Формулы $2i+1$, $2i+2$ жёстко фиксируют позицию каждого потомка исходя из предположения о почти полном заполнении дерева. Несбалансированное дерево, где часть веток короче других, нарушает это предположение — часть ячеек массива останется незаполненной, теряя всю выгоду от компактного хранения.
❌ Ошибка: «Симметричный обход (inorder) применим к любому дереву так же однозначно, как прямой и обратный» ✅ Правильно: Симметричный обход в классическом виде определён только для бинарных деревьев, потому что требует единственной точки «между» потомками узла 💡 Почему: Для n-арного узла с тремя и более потомками нет естественного способа сказать, «между каким и каким потомком» обрабатывать сам узел — прямой и обратный обходы обобщаются на n-арный случай напрямую (обработать до всех потомков или после всех потомков), а inorder — нет без дополнительных соглашений.
❌ Ошибка: «Обход в ширину (BFS) и обход в глубину (DFS) всегда посещают узлы в одинаковом порядке, просто с разными названиями» ✅ Правильно: Порядок посещения узлов у BFS и DFS, как правило, различается уже начиная со второго уровня дерева — задание 10 практики показывает это на конкретном примере 💡 Почему: BFS использует очередь (FIFO) и гарантированно обрабатывает все узлы одного уровня раньше любого узла следующего уровня; DFS использует стек (явный или неявный, через рекурсию, LIFO) и может «провалиться» в глубину одной ветки, минуя другие ветки того же уровня. Разные структуры данных внутри алгоритма — разный порядок обхода снаружи.
❌ Ошибка: «Рекурсивный обход дерева безопасен для любого дерева, потому что дерево — небольшая структура» ✅ Правильно: Глубина рекурсии равна высоте дерева, и на сильно несбалансированном (почти вырожденном) дереве рекурсивный DFS может исчерпать лимит глубины рекурсии интерпретатора независимо от общего числа узлов 💡 Почему: Задание 29 практики разбирает это прямо: дерево из $100\,000$ узлов, вытянутое в почти линейную цепочку, потребует $100\,000$ вложенных вызовов функции — переполнение стека вызовов наступит задолго до обработки всех узлов, если не перейти на итеративную реализацию с явным стеком.
Главное запомнить
✅ Дерево — иерархическая структура данных с единственным корнем, где у каждого узла (кроме корня) ровно один родитель, а число потомков произвольно; между корнем и любым узлом существует ровно один путь, циклов нет
✅ Ключевые термины: узел, корень (без родителя), лист (без потомков), внутренний узел (с потомками), ребро (связь родитель-потомок), поддерево (узел вместе со всеми его потомками)
✅ Глубина узла считается от корня вниз (глубина корня $=0$), высота дерева — это глубина самого глубокого листа; путать их — частая и системная ошибка
✅ Бинарное дерево — не более двух потомков у узла (левый и правый); n-арное дерево — произвольное число потомков; на практике деревья решений почти всегда строят бинарными даже для категориальных признаков с несколькими значениями
✅ Прямой обход (preorder): узел → левое → правое — используется для копирования, сериализации, извлечения правил «сверху вниз»
✅ Симметричный обход (inorder): левое → узел → правое — для бинарного дерева поиска даёт элементы в отсортированном порядке; определён только для бинарных деревьев
✅ Обратный обход (postorder): левое → правое → узел — используется, когда обработка узла зависит от уже обработанных потомков: безопасное удаление, подсчёт агрегатов снизу вверх
✅ Обход в ширину (BFS) идёт по уровням через очередь (FIFO); принципиально отличается от DFS порядком посещения узлов уже со второго уровня
✅ Связное представление (объекты-узлы с указателями) подходит для любых деревьев, особенно несбалансированных; массивное представление (формулы $2i+1$, $2i+2$, $\lfloor(i-1)/2\rfloor$) компактно только для полных или идеальных деревьев
✅ В дереве решений высота дерева напрямую определяет и максимальную длину цепочки условий для одного объекта (время инференса), и склонность модели к переобучению — гиперпараметр max_depth управляет именно этой характеристикой
Связь с другими темами курса
🔙 Откуда пришли: Из уроков 253–255 — стеки и очереди (обе структуры буквально используются внутри DFS и BFS как хранилище «узлов на будущее»), связные списки (узел дерева с одним потомком — концептуально тот же узел связного списка, а дерево в целом обобщает список, допуская ветвление вместо единственной цепочки), хеш-таблицы (иногда используются вместе с деревом для быстрой проверки «посещён ли уже этот узел» при обходе циклических структур, родственных дереву, — графов).
🔜 Куда идём:
- Бинарные деревья поиска (урок 257) — тот самый инвариант «левое меньше, правое больше», который уже появлялся в примерах этого урока, здесь станет центральной темой: вставка, удаление, поиск за $O(h)$
- Сбалансированные деревья (урок 258) — что происходит, когда высота дерева поиска перестаёт быть маленькой (вырожденный случай из этого урока), и как AVL-деревья и красно-чёрные деревья гарантируют логарифмическую высоту независимо от порядка вставки
- Графы (уроки 259–260) — дерево является частным случаем графа (связный граф без циклов), и вся терминология обхода (DFS, BFS), освоенная здесь на деревьях, переносится на графы почти без изменений, только с добавлением проверки на уже посещённые узлы
🎯 В машинном обучении: Дерево решений — не аналогия, а прямое применение структуры данных «дерево» из этого урока: узлы хранят условия разбиения по признакам, листья хранят предсказания, а инференс — это спуск от корня до листа ровно так, как это делает функция обхода. В будущих уроках курса, посвящённых деревьям решений, ансамблевым методам (случайный лес, градиентный бустинг) и их гиперпараметрам, ты будешь напрямую использовать термины «высота», «глубина», «лист», «обход», введённые здесь — без этого фундамента разговор о max_depth, min_samples_leaf или об извлечении правил из обученного дерева был бы разговором о магии, а не о конкретном, понятном механизме.
Интересные факты
📌 В большинстве языков программирования и учебников дерево принято рисовать «корнем вверх, листьями вниз» — вопреки ботанической метафоре, откуда пришло само слово. Это, вероятно, унаследовано от математической традиции рисования графов и диаграмм родословных, где принято начинать с самого «старшего» элемента сверху страницы.
📌 B-дерево (упомянутое в историческом разделе), несмотря на название, не является бинарным — буква «B» в его названии, по одной из версий, происходит от фамилии одного из авторов, Байера (Bayer), либо от слова «balanced» (сбалансированное); узлы B-дерева могут иметь десятки и сотни потомков, что специально сделано для минимизации числа обращений к медленному диску при поиске.
📌 XML- и HTML-документы, которые обрабатывает браузер, во внутреннем представлении браузера превращаются именно в дерево — DOM (Document Object Model). Когда JavaScript-код обращается к document.body.children, он буквально обходит узлы этого дерева, а методы вроде querySelectorAll внутри выполняют разновидность обхода в глубину по всему DOM-дереву страницы.
📌 В компиляторах и интерпретаторах языков программирования (включая сам Python) исходный код сначала превращается в абстрактное синтаксическое дерево (AST) — именно на этом дереве компилятор выполняет проверки типов, оптимизации и в конце концов генерирует машинный код; функция ast.parse() в стандартной библиотеке Python позволяет увидеть это дерево для любого кода на Python своими глазами.
Лайфхаки и полезные трюки
💡 Если забыл, какой обход что делает, запомни мнемонику по позиции буквы «Д» (для «действие», то есть обработка узла) в трёхбуквенном названии относительно «Л» (левое) и «П» (правое): Д-Л-П — прямой (preorder, действие первое), Л-Д-П — симметричный (inorder, действие в середине), Л-П-Д — обратный (postorder, действие последнее).
💡 Перед тем как писать код обхода дерева, задай себе один вопрос: «нужно ли мне обработать узел раньше, позже или между обработкой его потомков?» — ответ на этот единственный вопрос сразу выбирает между preorder, postorder и inorder без необходимости запоминать три отдельных алгоритма как нечто изолированное.
💡 Когда пишешь рекурсивную функцию на дереве и не уверена, какой должен быть базовый случай — почти всегда это проверка if node is None: return ... с «нейтральным» значением (нулём для суммы, -1 для высоты, пустым списком для сбора значений) — то есть значением, которое не повлияет на результат объединения с результатами по непустым поддеревьям.
💡 Если дерево может быть очень глубоким (сотни тысяч уровней) или ты не уверена в его сбалансированности, сразу закладывай итеративную реализацию обхода с явным стеком или очередью вместо рекурсии — это разом снимает риск RecursionError, разобранный в задании 29, и часто оказывается даже немного быстрее за счёт отсутствия накладных расходов на вызовы функций.
💡 При отладке кода, работающего с деревом, полезно сначала написать вспомогательную функцию печати дерева с отступами по глубине (например, print(" " * depth + str(node.value)) при обходе с передачей текущей глубины) — визуальное представление формы дерева на экране почти всегда мгновенно показывает, где логика пошла не так, особенно при работе со вставкой или удалением узлов.
💡 Начиная работать с деревом решений в scikit-learn, используй sklearn.tree.export_text() или plot_tree(), чтобы увидеть обученное дерево как текст или картинку, — за этими функциями стоит ровно та же логика обхода дерева (по сути, вариант prefix-обхода с накоплением условий пути), которую ты только что реализовала руками в задании 21 практики этого урока.
Дерево — редкий пример структуры данных, знакомство с которой окупается почти сразу и почти везде: стоит один раз разобраться, что такое корень, лист, глубина и три способа обхода, и внезапно начинаешь узнавать эту же конструкцию в файловом менеджере, в разборе кода, в структуре HTML-страницы и, конечно, в самой интерпретируемой модели машинного обучения — дереве решений. Следующий урок возьмёт этот фундамент и превратит его в конкретный, работающий инструмент поиска: бинарное дерево поиска, где каждая операция — вставка, удаление, поиск — опирается ровно на те определения глубины, высоты и обхода, которые сегодня перестали быть абстракцией и стали рабочим словарём.
Понял тему? Закрепи в боте! 🚀
Попрактикуйся на задачах и получи персональные рекомендации от AI
💪 Начать тренировку