§ 55. Деревья

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

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

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

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

Потомок вершины — вершина, расположенная ниже неё: это может быть её ребёнок или вершина, до которой нужно пройти через несколько уровней. Ребёнок — непосредственный потомок, а остальные потомки связаны с вершиной через промежуточные вершины. Такое различение позволяет точно описывать структуру дерева.

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

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

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

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

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

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

Основные понятия и свойства дерева

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

Разбор задач

1. Проверяем, является ли граф деревом

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

1. Выбираем любую вершину и проверяем, можно ли по рёбрам добраться от неё до каждой другой. Если некоторые вершины недостижимы, граф несвязный и деревом не является.
2. Если граф связен, ищем цикл: например, замкнутый маршрут по рёбрам без повторения ребра. Найденный цикл означает, что граф не является деревом.
3. Только если граф связен и циклов нет, оба условия выполнены. Тогда граф является деревом.

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

2. Находим отношения и уровни

Условие. В корневом дереве даны вершины и рёбра, требуется найти родителей, детей, листья и уровни. В примере корень A соединён с B и C, B соединена с D и E, а C — с F. Считаем уровень корня равным нулю.

1. От корня A прослеживаем единственные пути: непосредственно соединённые с ним B и C получают уровень 1.
2. Вершины D и E находятся на два ребра от A через B, а F — на два ребра через C. Поэтому у всех трёх уровень 2.
3. Родитель B и C — A; родители D и E — B; родитель F — C. Дети A — B и C, B — D и E, C — F.
4. Проверяем, у каких вершин нет детей. D, E и F — листья; A, B и C листьями не являются.

Ответ. Уровни: A — 0, B и C — 1, D, E и F — 2. Листья — D, E и F, а высота дерева равна 2. Родителя каждой вершины, кроме A, можно определить как предыдущую вершину на пути от корня.

3. Считаем рёбра и проверяем добавление

Условие. Дерево имеет 12 вершин. Нужно определить число рёбер и выяснить, можно ли добавить одно ребро, сохранив свойство дерева. Рассматриваем добавление ребра между уже существующими вершинами. Для ответа используем свойство дерева и объясним, что изменится.

1. Обозначаем число вершин через n. Для дерева число рёбер равно n − 1, поэтому при n = 12 получаем 12 − 1 = 11.
2. Предполагаем, что добавлено ребро между двумя вершинами. В дереве уже есть единственный путь между ними.
3. Новое ребро вместе с существующим путём образует замкнутый маршрут. Значит, возникает цикл, и граф перестаёт быть деревом.

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

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

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

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

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

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

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

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

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

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