Дерево

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

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

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

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

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

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

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

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

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

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

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

Роли вершин в дереве

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

Разбор задач

Задача 1

Дано дерево с корнем A и рёбрами A–B, A–C, B–D. Нужно назвать корень, листья и потомков вершины A. Сначала восстановим направление ветвей от A, потому что именно оно задаёт отношения между вершинами.

1. Корень уже указан в условии: это A.
2. От A идут ветви к B и C, а от B — к D.
3. У C и D нет потомков, значит, они листья.
4. Вершины, расположенные ниже A, — B, C и D; непосредственные потомки A — B и C.

Ответ: корень — A, листья — C и D. Потомки A — B, C и D, а непосредственные потомки A — B и C. Вершина D является потомком A через B.

Задача 2

Для дерева с корнем A заданы рёбра A–B, A–C, B–D, B–E, C–F. Требуется указать предка и потомков вершины E, а также уровень вершины F. Для этого нужно проследить путь от корня, не ограничиваясь только соседними вершинами.

1. Путь к E имеет вид A–B–E.
2. Значит, непосредственный предок E — B, а более дальний предок — A.
3. У E нет ветвей вниз, поэтому потомков у неё нет.
4. Путь к F имеет вид A–C–F и содержит два ребра, поэтому после корня и C вершина F находится на третьем уровне.

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

Задача 3

Проверим, может ли структура с рёбрами A–B, A–C, B–D, C–D быть деревом с корнем A. На первый взгляд схема похожа на разветвление, но нужно проверить единственность пути к каждой вершине. Особенно важно рассмотреть вершину D.

1. Из A в D можно попасть по пути A–B–D.
2. Существует и второй путь: A–C–D.
3. Следовательно, у D два пути от корня и две возможные непосредственные связи с B и C.
4. Это нарушает основное свойство дерева, даже если замкнутого цикла на рисунке нет.

Ответ: структура не является деревом с корнем A. К вершине D ведут два разных пути, а у D оказалось бы два непосредственных предка. Для дерева такой случай недопустим.

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

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

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

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

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

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

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

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

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

• У дерева есть один корень.
• От корня к каждой вершине ведёт единственный путь.
• У каждой вершины, кроме корня, есть один непосредственный предок.
• Лист не имеет потомков.
• Уровень вершины определяется её удалённостью от корня.
• Ветви дерева показывают отношения между вершинами.