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

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

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

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

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

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

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

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

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

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

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

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

Элементы дерева последовательностей бусин

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

Разбор задач

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• Дерево начинается с корня.
• Вершины соединяются рёбрами.
• Каждый путь от корня задаёт одну последовательность бусин.
• Предыдущая вершина находится на один шаг ближе к корню.
• Новый уровень соответствует следующему шагу построения.
• Конечная вершина не имеет продолжений.
• Запрещённый переход не должен появляться в дереве.