Связывание внутренних узлов с внешними узлами в правильном двоичном дереве

Question

Я изучаю двоичное дерево с '' структурами данных и алгоритмами в Python "

Когда автор сообщает" Связывание внутренних узлов с внешними узлами в правильном двоичном дереве ", он читает

Предложение 8.9: В непустом собственном двоичном дереве T с nE внешними узлами и n I внутренними узлами мы имеем n E = n I + 1.

(`` n E, n I` и h обозначают количество узлов, количество внешних узлов, количество внутренних узлов,)

автор продолжил:

Обоснование: МыОбоснуйте это предложение, удалив узлы из T и разделив их на две «стопки», стопку внутренних узлов и стопку внешних узлов, пока T не станет пустым. Сваи изначально пусты. К концу мы покажемчто куча внешних узлов имеет на один узел больше, чем куча внутренних узлов. Мы рассмотрим два случая:

• Случай 1: Если T имеет только один узел v, мы удаляем v и помещаем его всвая внешнего узла. Таким образом, свая внешнего узла hкак один узел, а куча внутреннего узла пуста.
• Случай 2: В противном случае (T имеет более одного узла), мы удаляем из T (произвольный) внешний узел w и его родительский элемент v, который является внутренним узлом.Мы помещаем w в стопку внешних узлов и v в стопку внутренних узлов.Если у v есть родительский элемент u, то мы воссоединяем u с прежним братом z из w, как показано на рисунке 8.10.Эта операция удаляет один внутренний узел и один внешний узел и оставляет дерево соответствующим двоичным деревом.Повторяя эту операцию, мы в конечном итоге получаем конечное дерево, состоящее из одного узла.Обратите внимание, что одинаковое количество внешних и внутренних узлов было удалено и размещено на их соответствующих кучах в результате последовательности операций, ведущих к этому конечному дереву.Теперь мы удаляем узел конечного дерева и помещаем его в стопку внешних узлов.Таким образом, куча внешних узлов имеет на один узел больше, чем куча внутренних узлов.

Я только начинаю изучать алгоритмы, но нахожу скважину- Знающий автор смешно смешной, он изо всех сил пытается навязать такой обходной путь, чтобы n E = n I` +1, Да, конечно, лист (внешний) еще один оргинайте из внутреннего узла.Я думаю, что очень глупо доказывать, что «1 + 1 = 2» или «это земля, инопланетяне»

Я что-то упускаю?

Answer 1

Да, конечно, лист (внешний) происходит от внутреннего узла еще один.Я думаю, что очень глупо доказывать «1 + 1 = 2»

Не уверен, что я последую вашему доказательству.Рассмотрим следующее:

1. Действительно, каждый внешний узел имеет родительский (внутренний) узел, за исключением случаев, когда дерево состоит из одного узла, но
2. Два внешних узла имеют одного и того же родителя (внутренний) узел, поэтому приведенное выше приведет к двойному счету, и
3. Может быть несколько внутренних узлов, которые не имеют внешних узлов в качестве прямых дочерних элементов.

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

Конечно, это можно доказать несколькими способами, но сравнить его с 1 + 1 = 2 я могумнение упрощение.

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

Альтернативное доказательство

Альтернативное доказательство будет иметь в качестве второго (рекурсивного) шагаудаление двух родственных внешних узлов.Сначала мы должны доказать, что такую ​​пару можно найти, когда дерево - это не просто один узел:

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

Это удаление пары одного брата превращает их общий родительский узел во внешний узел.Отметим, что мы сохранили свойство «правильное двоичное дерево».Таким образом, мы удаляем 2 внешних узла и превращаем один внутренний узел во внешний узел.Таким образом, мы получаем один внешний и один внутренний узел меньше.Инвариантность сохраняется.Мы отмечаем, что мы всегда можем повторить эту операцию, пока не останется только один узел, который затем будет внешним узлом.

Это не так тривиально, как 1 + 1 = 2, хотя я бы понял, если бы у вас былпредпочтения.