Уровень вершины дерева

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

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

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

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

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

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

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

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

При переходе по одному ребру от родительской вершины к дочерней расстояние от корня увеличивается ровно на одно ребро. Значит, если родитель имеет уровень k, ребёнок имеет уровень k + 1. Благодаря этому уровни можно назначать последовательно, начиная с корня и двигаясь по ветвям.

Чтобы найти уровень вершины, нужно проследить путь от корня и посчитать рёбра. Например, в пути корень — a — b — c четыре вершины, но только три ребра, поэтому уровень c равен 3. Число вершин на таком пути всегда на единицу больше числа рёбер, если учитываются и корень, и конечная вершина.

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

Основные понятия и способы определения уровня вершины

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

Разбор задач

Определение уровней всех вершин

Условие. На схеме дано дерево с указанным корнем. Требуется определить уровень каждой вершины. Схема может быть нарисована по-разному, но правило отсчёта всегда одно.

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

Ответ. Уровни назначаются слоями: корень имеет уровень 0, его дети — 1, следующие потомки — 2 и так далее. Такой порядок позволяет не пропустить вершину и не посчитать одну ветвь независимо от другой.

Подсчёт по последовательности вершин

Условие. Дан путь от корня до вершины v: корень — a — b — c — v. Нужно определить уровень v и найти ошибку в подсчёте, если кто-то получил число 5, посчитав все названные вершины. Требуется отличить длину пути в рёбрах от количества его вершин.

1. Считаем переходы между соседними вершинами: корень–a, a–b, b–c, c–v.
2. Получаем 4 ребра, значит, расстояние от корня до v равно 4.
3. Сравниваем с числом вершин: их 5, потому что в список входит и начальная вершина, и конечная.
4. Исправляем результат: уровень v равен числу рёбер, а не числу записанных вершин.

Ответ. Уровень вершины v равен 4. Ошибка состояла в том, что вместо четырёх рёбер посчитали пять вершин пути.

Восстановление пропущенных уровней и высоты

Условие. Известны уровни нескольких вершин и связи между ними, но уровни некоторых вершин пропущены. Например, корень имеет уровень 0, его ребёнок p — уровень 1, а цепочка p — q — r заканчивается листом r. Нужно восстановить пропуски и определить высоту дерева.

1. От корня к p уровень увеличивается с 0 до 1, что подтверждает правило перехода к ребёнку.
2. Так как q — ребёнок p, его уровень равен 1 + 1 = 2.
3. Вершина r является ребёнком q, поэтому её уровень равен 3.
4. Если остальные ветви заканчиваются на уровнях 1 или 2, сравниваем их с уровнем r и выбираем наибольшее значение.

Ответ. Пропущенные уровни q и r равны соответственно 2 и 3. При указанных условиях высота дерева равна 3, поскольку это наибольший уровень конечной вершины.

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

Уровень корня считают равным 1. Так происходит, когда номер первого элемента путают с расстоянием от начала. Проверьте себя вопросом: сколько рёбер нужно пройти от корня до него самого; правильный ответ — 0.

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

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

Забывают о выбранном корне. Уровень не является постоянным свойством вершины безотносительно к дереву с корнем. Если корень изменили, заново отсчитайте расстояния и сравните новые уровни.

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

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

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

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

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

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