Дерево. Предыдущие вершины

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

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

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

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

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

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

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

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

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

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

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

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

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

Разбор задач

Задача 1

В дереве с корнем A имеются рёбра A–B, A–C, B–D, B–E, C–F. Назвать предыдущую вершину для E и следующие вершины для B. Чтобы ответить, учитываем не положение букв на рисунке, а непосредственные рёбра и выбранный корень. Так мы не перепутаем соседей с более далёкими предками.

1. Из списка рёбер видно, что E соединена непосредственно с B.
2. Путь от E к корню A проходит через B: E—B—A. Первый шаг ведёт в B, значит, B — предыдущая вершина для E.
3. У B есть непосредственные связи с A, D и E. Но A ближе к корню, поэтому A — предыдущая для B, а не следующая.

Ответ: предыдущая вершина для E — B; следующие вершины для B — D и E.

Задача 2

По записи предыдущих вершин B←A, C←A, D←B, E←B, F←C построить дерево с корнем A и назвать его листья. Стрелка указывает, какая вершина является предыдущей: например, B←A означает, что предыдущая для B — A. Каждая такая запись задаёт одно ребро, поэтому для построения достаточно соединить все указанные пары.

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

Ответ: рёбра дерева — A–B, A–C, B–D, B–E, C–F; листья — D, E и F.

Задача 3

Даны связи A–B, A–C, B–D, C–E, E–F. Выбрать корень A, определить предыдущую вершину каждой вершины, уровни вершин и путь от D до F. Вначале нужно развернуть связи относительно корня, а затем проследить маршрут между заданными вершинами. Поскольку дерево связное и не содержит циклов, нужный путь будет единственным.

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

Ответ: предыдущие вершины: у A нет, у B и C — A, у D — B, у E — C, у F — E. Уровни: A — 0; B и C — 1; D и E — 2; F — 3. Путь от D до F: D—B—A—C—E—F.

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

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

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

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

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

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

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

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

• Дерево — связный граф без циклов.
• В дереве между любыми двумя вершинами существует единственный путь.
• Корень — выбранная начальная вершина дерева.
• У корня нет предыдущей вершины.
• У каждой другой вершины ровно одна предыдущая вершина.
• Следующие вершины — непосредственные потомки данной вершины.
• Предыдущие и следующие вершины определяются относительно выбранного корня.