Доказательство, что бинарное дерево имеет не более

Я пытаюсь доказать, что бинарное дерево с узлами имеет самое большее ⌈ $n$листья. Как мне поступить с индукцией?$\left\lceil \frac{n}{2} \right\rceil$

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

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

Если дано двоичное дерево с узлами, докажите, что оно содержит не более ⌈ $n$листья.$\left\lceil \frac{n}{2} \right\rceil$

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

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

Индукционный якорь состоит из двух частей. Во-первых, для имеем T = E m p t y с l T = n T = 0 ; претензия явно относится к пустому дереву. Для h ( t ) = 1 , т.е. T = L e a f , аналогично имеем l T = 1 = ⌈ n $h(t)=0$$T=\mathrm{Empty}$$l_T=n_T=0$$h(t)=1$$T = \mathrm{Leaf}$, так что претензия распространяется на листья.$l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$

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

Для индуктивного шага рассмотрим произвольное двоичное дерево с h ( T ) = k + 1 . Поскольку k ≥ 1 , T = N o d e ( L , R ) и n T = n L + n R + 1 . Поскольку L и R также являются бинарными деревьями (иначе T не будет) и h ( L ) , h $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} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

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

$\qquad \begin{align*} l_T &= l_L + l_R \\ &\leq \left\lceil \frac{n_L}{2} \right\rceil + \left\lceil \frac{n_R}{2} \right\rceil \\ &\leq \left\lceil \frac{n_L + n_R + 1}{2} \right\rceil \qquad (*)\\ &= \left\lceil \frac{n_T}{2} \right\rceil \end{align*}$

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

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

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

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

Пусть такое дерево с n узлами и L листьями. Так как T - дерево, существует n - 1 ребер, и их двойной счет, мы видим, что 2 n - 2 ≤ L + 3 ( n - L ), который говорит, что 2 L ≤ n + 2, и это тесно в двух Пример вершины выше. Я думаю, что если вы хотите предположить, что существует один корень степени два и n ≥ 3 , то вы можете уточнить этот аргумент, чтобы дать 2 $T$$n$$L$$T$$n-1$