§ 43. Деревья

Определения и обозначения

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

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

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

Лист — вершина корневого дерева, не имеющая потомков. Внутренняя вершина, напротив, имеет хотя бы одного потомка. Такое различие показывает, где ветви дерева заканчиваются, а где от вершины продолжается дальнейшая структура.

Как это устроено

В дереве между любыми двумя вершинами существует ровно один путь. Связность обеспечивает наличие хотя бы одного пути, поэтому вершины не оказываются в разных несвязанных частях. Если бы существовали два разных пути между одной парой вершин, их расхождение и последующее соединение образовали бы цикл; отсутствие циклов исключает такую возможность.

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

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

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

Обход дерева — способ перечислить его вершины в определённом порядке. При обходе в глубину сначала переходят в поддерево и продолжают движение вглубь, пока это возможно, а затем возвращаются к предыдущим вершинам. В прямом обходе корень посещают до потомков, в обратном — после них. В симметричном обходе двоичного дерева сначала посещают левое поддерево, затем корень, потом правое; порядок зависит от момента посещения корня.

Виды деревьев и их основные характеристики

Сопоставляйте вид дерева с условиями, которые задают его устройство: наличие корня, число потомков и способ считать вершины. Столбец «Что важно проверить» помогает не спутать определения, а примеры показывают, где такие структуры полезны.

Разбор задач

Задача 1. Дан граф с 6 вершинами и 5 рёбрами. Известно, что граф связный; нужно определить, является ли он деревом. Используем признак для связного графа: при n вершинах дерево содержит n − 1 ребро. Важно учитывать условие связности, потому что одного подсчёта рёбер недостаточно.

1. Находим число вершин: n = 6.
2. Вычисляем необходимое для дерева число рёбер: n − 1 = 6 − 1 = 5.
3. Сравниваем результат с условием: рёбер действительно 5, а граф связный.

Ответ: граф является деревом. Связность дана в условии, а число рёбер соответствует признаку; следовательно, циклов в графе нет.

Задача 2. Для корневого дерева нужно указать корень, потомков каждой вершины, листья и уровни. Поскольку само дерево представлено схемой, последовательность действий применима к любой такой схеме: сначала находят выделенную вершину, а затем прослеживают рёбра от неё. Уровень вершины равен числу рёбер на пути от корня.

1. Найдите выделенный корень и присвойте ему уровень 0.
2. Для каждой вершины на очередном уровне отметьте соседей, расположенных дальше от корня: это её непосредственные потомки.
3. Повторяйте действие, двигаясь по уровням; записывайте для каждой вершины её родителя и потомков.
4. Отметьте вершины, у которых не осталось потомков: это листья.

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

Задача 3. Для заданного двоичного дерева нужно выписать вершины в порядке прямого, симметричного и обратного обхода. Чтобы не перепутать последовательности, применяем одно рекурсивное правило к корню и затем к каждому поддереву. Рекурсия означает повторение того же действия для частей дерева.

1. При прямом обходе запишите корень, затем выполните прямой обход левого и правого поддеревьев.
2. При симметричном обходе сначала выполните обход левого поддерева, затем запишите корень, после чего обойдите правое.
3. При обратном обходе сначала обойдите левое и правое поддеревья, а корень запишите последним.
4. Повторяйте соответствующий порядок в каждом поддереве до листьев; пустую ветвь просто пропускайте.

Ответ: точные последовательности определяются вершинами на схеме. Для проверки сравните, в какой момент в каждой последовательности появляется корень каждого поддерева: до потомков, между ними или после них.

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

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

Ошибка: считать, что граф с n вершинами и n − 1 ребром обязательно является деревом. Число рёбер само по себе не гарантирует связности: граф может распасться на компоненты и при этом иметь нужное количество рёбер. Чтобы не сделать поспешный вывод, сначала проверяйте связность, а затем применяйте признак для связного графа.

Ошибка: определять лист как вершину степени 1. В корневом дереве лист — это вершина без потомков, а корень может быть листом, если у него нет ни одного потомка. Степень считает все инцидентные вершине рёбра и не всегда совпадает с числом потомков. Проверяйте положение вершины относительно корня и наличие потомков.

Ошибка: полагать, что у каждой вершины двоичного дерева обязательно два потомка. Определение ограничивает их максимальное количество, а не требует ровно двух. Эту ошибку провоцирует слово «двоичное», которое ошибочно принимают за указание на обязательную пару ветвей. У каждой вершины может быть ноль, один или два потомка.

Связь с другими темами

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

Что запомнить

• Дерево — связный граф без циклов.
• Между двумя вершинами дерева проходит ровно один путь.
• В дереве из n вершин ровно n − 1 ребро.
• Выбор корня задаёт иерархию вершин.
• Лист не имеет потомков.
• У вершины двоичного дерева не более двух потомков.
• Порядок обхода зависит от того, когда посещают корень относительно поддеревьев.