Доказательство того, что бинарное дерево с n листьями имеет высоту не менее log n

Question

Мне удалось создать доказательство, которое показывает, что максимальное количество узлов в дереве равно n = 2^(h+1) - 1, и логически я знаю, что высота двоичного дерева равна log n (могу нарисовать его) чтобы увидеть) но у меня возникли проблемы с построением формального доказательства, чтобы показать, что дерево с n листьев "по крайней мере" log n. Каждое доказательство, которое я встречал или смог собрать, всегда имеет дело с идеальными бинарными деревьями, но мне нужно что-то для любой ситуации. Любые советы, чтобы привести меня в правильном направлении?

Answer 1

Лемма: количество листьев в дереве высоты h не более чем 2^h,

Доказательство: доказательство по индукции на h,

Базовый случай: для h = 0дерево состоит только из одного корневого узла, который также является листом; Вот, n = 1 = 2^0 = 2^h, как требуется.

Гипотеза индукции: предположим, что все деревья высоты k или меньше, чем меньше 2^k узлы.

Шаг индукции: мы должны показать, что деревья высоты k+1 не более чем 2^(k+1) листья. Рассмотрим левое и правое поддеревья корня. Это деревья высотой не более kна один меньше высоты всего дерева. Поэтому каждый имеет не более 2^k листья, по предположению индукции. Так как общее количество листьев является просто суммой чисел листьев поддеревьев корня, мы имеем n = 2^k + 2^k = 2^(k+1), как требуется. Это доказывает претензию.

Теорема: двоичное дерево с n листья имеют высоту не менее log(n),

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

Позволять n = 2^a + b где 0 < b <= 2^a, Теперь предположим, что высота дерева меньше a + 1вопреки теореме мы намерены доказать. Тогда высота не более a, По лемме максимальное количество листьев в дереве высоты a является 2^a, Но наше дерево имеет n = 2^a + b > 2^a листья, так как 0 < b; противоречие. Поэтому предположение, что высота была меньше a+1 должно быть, был неверным. Это доказывает претензию.