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

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

Проблема:

Определите высоту дерева как максимальное количество ребер между корнем и любым листом. Мы считаем, что высота пустого дерева равна -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 (1) = 2 Когда высота равна 0, дерево состоит из одного, поэтому да, 1 узел меньше 2 узлов. Индуктивный шаг = h меньше или больше 0 Вот где я застрял ... Я знаю, что утверждение верно, так как высота всегда будет на 1 меньше, чем количество узлов, я просто не знаю, как доказать это алгебраически.

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


induction computer-science-theory
person Hannah Holloway    schedule 26.01.2019    source источник
comment
Подумайте о том, чтобы построить дерево h + 1, продублировав дерево h и добавив корневой узел. И вы должны отредактировать свой вопрос и заменить 2h + 1 на 2 ^ (h + 1).   -  person Alain Merigot    schedule 26.01.2019

Ответы (1)


arrow_upward
1
arrow_downward

Предположим, у вас есть дерево высотой 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), как требуется.

person Null Terminator    schedule 25.03.2019