Доказательством по индукции, что каждое непустое дерево высоты h содержит менее 2 ^ n + 1 узлов

Question

Я застрял на индукционном случае проблемы.

Проблема:

Определите высоту дерева как максимальное количество ребер между корень и любой лист. Мы считаем, что высота пустого дерева равна -1, и высота дерева, состоящего из одного узла, равна 0. Докажите по индукции, что каждое непустое двоичное дерево высоты h содержит менее 2 ^{(h + 1)} узлов.

So I started:

Base case: h = 0 (Since a non-empty tree consists of a single node 
or 
more, the first case would be an empty node)

= 2 ^{(0 + 1)} = 2 ⁽¹⁾ = 2 Когда высота равна 0, дерево состоит из одного, так что да 1 узел менее 2 узлов. Шаг индукции = h меньше или больше 0 Вот где я застрял ... Я знаю, что это утверждение верно, так как высота всегда будет на 1 меньше, чем количество узлов, я просто не знаю, как это доказать алгебраически.

Заранее спасибо.

Answer 1

Предположим, у вас есть дерево с высотой n + 1.

Высота его левого поддерева и правого поддерева ограничена значением n.По индукции каждое поддерево имеет менее 2 ^ (n + 1) узлов, что означает не более 2 ^ (n + 1) - 1 узлов.

Поскольку у нас есть два поддерева, мы имеем не более 2 * (2 ^ (n + 1) - 1) = 2 ^ (n + 2) - 2. Добавьте один для корня, и дерево высоты n + 1 имеет не более 2 ^ (n + 2) - 1, чтоменее 2 ^ (n + 2), при необходимости.