Доказательство того, что двоичное дерево имеет не более $ \ lceil n / 2 ceil $ листьев

Question

Я пытаюсь доказать, что бинарное дерево с $ n $ узлами имеет не более $\left\lceil \frac{n}{2} ight ceil$ листьев.Как бы я мог сделать это с помощью индукции?

Для людей, которые следили за первоначальным вопросом о кучах, он был перенесен здесь.

Answer 1

Теперь я предполагаю, что вопрос заключается в следующем:

Учитывая двоичное дерево с $n $ узлами, докажите, что оно содержит не более $\left\lceil \frac{n}{2} ight ceil$ листьев.

Давайте поработаем с определением дерева $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$.Для $T$ такого дерева пусть $n_T$ количество узлов в $T$ и $l_T $ количество листьев в $T $.

Вы правы, делая это методом индукции, но вам понадобится структурный индукция, которая следует древовидной структуре.Для деревьев это часто делается как полная индукция по высота $h(T)$ деревьев.

Индукционный якорь состоит из двух частей.Во-первых, для $h (t)=0 $ мы имеем $T=\mathrm{Empty}$ с $l_T=n_T=0 $;утверждение явно справедливо для пустого дерева.Для $h(t)=1$, т.е.$ T = \ mathrm {Лист} $, аналогично у нас есть $ l_T = 1= \left \lceil \ frac {n_T} {2} \ right \ rceil $, поэтому утверждение справедливо для листьев.

Гипотеза индукции такова:Предположим, что утверждение справедливо для всех (двоичных) деревьев $ T $ с $ h (T) \ leq k $, $ k \ geq 1 $ произвольным, но фиксированным.

Для индуктивного шага рассмотрим произвольное двоичное дерево $ T $ с $h (T)=k+1 $.Как $k\geq 1$, $T=\mathrm{Node}(L,R)$ и $n_T = n_L+ n_R+1 $.Поскольку $ L $ и $ R $ также являются бинарными деревьями (иначе $ T $ не было бы) и $ h (L), h (R) \ leq k $, применяется гипотеза индукции и имеют

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L} {2} ight ceil ext{ и } l_R \leq \left\lceil \frac{n_R}{2} ight ceil.$

Поскольку все листья $ T $ находятся либо в $ L $, либо в $ R $, мы имеем, что

$\qquad \begin{выровнять *} l_T &= l_L + l_R \\ &\leq \left\lceil \frac{n_L}{2} ight ceil + \left\lceil \frac{n_R}{2} ight ceil \\ &\leq \left\lceil \frac{n_L + n_R + 1}{2} ight ceil \qquad (*)\\ &= \left\lceil \frac{n_T}{2} ight ceil \end{выровнять*}$

Неравенство, отмеченное знаком $ (*) $, может быть проверено с помощью (четырехстороннего) различия в зависимости от того, являются ли $ n_L, n_R\in 2\mathbb{N} $.По силе индукции на этом доказательство завершается.

---

В качестве упражнения вы можете использовать ту же технику для доказательства следующих утверждений:

• Каждое идеальное двоичное дерево высотой $h$ имеет $2^h-1$ узлов.
• Каждое полное двоичное дерево имеет нечетное число узлов.

Answer 2

Я немного смущен вопросом. Если вы заинтересованы в деревьях со степенью, не более 3 $, что является то, что вы хотите, тогда мы сталкиваемся с проблемой, что у одного края $ n = 2 $ узлы и $ n = 2 $ листья, но $ n// 2 = 1 $. Во всяком случае, вот что -то близкое, что имеет легкий аргумент.

Пусть $ t $ будет таким деревом с узлами $ n $ и листьями $ l $. Поскольку $ t $ - это дерево, есть края $ n -1 $, и двойной подсчет их, мы видим, что $$ 2n - 2 le l + 3 (n - l) $$, который говорит, что $$ 2l le n + 2 $$, и это жестко в примере двух веществ. Я предполагаю, что если вы хотите предположить, что есть один корень из степени 2 и $ n ge 3 $ Это плотно, когда дерево заполнено.