В двоичном дереве для каждого узла разница между количеством узлов слева и справа

Question

В двоичном дереве для каждого узла разница между числом узлов в левом и правом поддеревах составляет не более 2. Если высота дерева равна h> 0, то минимальное количество узлов в дереве равно .

Мое понимание: Общее количество узлов в этом дереве = количество левых узлов поддерева + количество правых узлов поддерева + 1 (root узел)

= количество левых узлов поддерева + (№ левых узлов поддерева - 2) + 1

= № левых узлов поддерева + № левых узлов поддерева - 2 + 1

= 2 * № левого узлы поддеревьев - 1

H (n) = 2 * H (n-1) -1 здесь я решил это с помощью подстановки, но когда я ставлю h (0) = 1, он дает только 1 в качестве ответа, а не в терминах H. Можете ли вы помочь, почему я не могу поставить h (0) = 1 в качестве моего базового условия, потому что оно также удовлетворяет заданному двоичному дереву.

Answer 1

Когда n = 1, в минимальном случае левое поддерево из root имеет 1 узел, но правое поддерево имеет 0 узлов, а не -1 узлов, как подсказывают ваши рассуждения.

Для n > 1, ваши рассуждения верны.

Так что вам нужно принять H (1) = 2, и тогда вы получите правильные результаты.

Answer 2

Ваше повторение предполагает, что в вашем дереве есть узлы.

H(n) = 2*H(n-1) - 1 предполагает, что H(n-1) определено. Но для n = 0 H(n-1) = H(-1), что не имеет смысла. Таким образом, вам нужно установить sh ваш базовый случай для H(0), который вы можете сделать с помощью простого аргумента.

Таким образом, ваше повторение будет равно H, когда n = 0 и H(n) = 2*H(n-1) - 1, если n > 0.

Кроме того, вы должны использовать> = в своем аргументе. Левое поддерево может быть больше.

нет. левых узлов поддерева + нет. правых узлов поддерева + 1> = нет. левых узлов поддерева + (количество левых узлов поддерева - 2) + 1