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

Question

Я знаю, что число листьев в бинарном дереве высотой h может быть не более 2^h, и я также знаю, как доказать это с помощью индукции. Куда мне идти отсюда?

Я нашел этот ранее отвеченный вопрос, но это не имеет никакого смысла для меня, потому что я не понимаю, какое доказательство от противного в разделе теоремы имеет какое-либо отношение к высоте двоичного дерева будучи по крайней мере log(n). Я ожидал, что он расскажет о том, как log(n) относится к числу листьев и росту, но вместо этого он продолжает говорить о том, как сделать доказательство от противного, используя n = 2^a + b.

Может кто-нибудь помочь мне понять, как мы можем доказать, что высота БТ с n листьями будет по крайней мере log n?

Answer 1

Итак, вы знаете, что ваше двоичное дерево имеет следующие свойства:

n <= 2 ^ h </p>

Теперь вы можете использовать журнал с обеих сторон, потому что оба положительны, и это все изматематическая точка зрения.

Чтобы лучше понять это, вы можете сделать следующее: Если у вас есть неполное дерево, вы обменяли 2 возможных листа на один фактический лист (потому что могло быть 2 ребенка),Таким образом, максимальное количество листьев для любой данной высоты - это полное дерево, которое имеет 2 ^ h листьев или log (n) высоты.

Answer 2

Рассмотрим двоичное дерево, и пусть h будет его высотой, а n будет числом его листьев.

По вашему первому предложению n <= 2^h.Взяв лог-базу 2 с обеих сторон (которая сохраняет неравенство, потому что log монотонна), мы имеем log(n) <= h.Это сразу дает вам то, что вы хотели: высота не менее log(n), где n - количество листьев.