Где ошибки в моем индуктивном доказательстве?

Question

Мне задали следующий вопрос на экзамене, и он был помечен как неправильный, без других отметок на нем.Я пошел к ТА, который отметил это, и он мог только сказать мне, что это было неправильно.Я подозреваю, что у него не было времени, чтобы объяснить это мне.Это беспокоит, потому что у меня не должно быть такого понимания индукции, как я думал.Любая помощь будет принята с благодарностью, поскольку это будет не последний раз, когда я буду видеть индукцию.

Вопрос:

Для правильного бинарного дерева докажите e = i + 1, где e - этоколичество листьев (внешних узлов) в дереве, а i - количество внутренних узлов в дереве.

Моя лучшая попытка доказательства:

Базовый случай: есть один узелв дереве, которое является внешним.

i = 0

e = i + 1 = 1

Предположим: e = i + 1

, если мыЕсли добавить узел, узел (родитель) станет внутренним узлом, а количество внешних узлов останется неизменным.Теперь у нас есть е = я.Однако, чтобы дерево было правильным двоичным деревом, мы должны добавить еще одного потомка, так что e = i + 1.

Answer 1

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

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

1. n - количество внутренних узлов

Чтобы создать дерево с n+1 внутренними узлами, мы должны взять дерево с n внутренними узлами и изменить некоторые поля с внутренним узлом. Этот новый внутренний узел должен иметь двух детей, которые являются листьями. Это означает, что у нового дерева есть еще один внутренний узел и еще один отпуск, чем дерево, из которого оно создано. Поскольку свойство (e=i+1) выполняется для исходного дерева, оно также выполняется (e+1=i+1+1) для нового дерева.

2. п - глубина дерева

Давайте возьмем дерево (T) глубины n+1. Он состоит из корня и двух дочерних деревьев. Каждое детское дерево имеет глубину <= n, и для того и другого свойства владения (e_1=i_1+1, e_2=i_2+1). Таким образом, число внешних узлов в T равно e = e_1 + e_2. Количество внутренних узлов в T составляет i = (i_1+1) + (i_2+1) + 1. Легко понять, что e = i + 1.