Udowodnienie, że drzewo binarne ma co najwyżej

Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej $n$ liści. Jak miałbym to robić z indukcją? $\left\lceil \frac{n}{2} \right\rceil$

Dla osób, które śledziły pierwotne pytanie o stosy, zostało tu przeniesione .

— varatis
źródło

Po pierwsze, pamiętaj, że możemy użyć LaTeX tutaj. Kliknij „edytuj”, aby zobaczyć, jak to zrobiłem. Po drugie, nie widzę indukcji. Rzucasz tam jakieś liczby, ale nie ma żadnej struktury dowodu ani żadnego związku ze stertami. Czy możesz to poprawić? I wreszcie, twierdzenie jest błędne: posortowana lista spełnia właściwość sterty i ma tylko jeden liść. Czy pominąłeś pewne założenia?

— Raphael

Czy @ Kaveh's edit ma na myśli to, co „najwyżej”?

— Raphael

@ Rafael, ponownie czytając pytanie, myślę, że może dotyczyć hałd, w których każdy wewnętrzny węzeł ma dokładnie dwoje dzieci (w którym to przypadku oryginalne pytanie ma sens, a twierdzenie jest poprawne lub coś podobnego).

— Kaveh

@Kaveh Ach tak, widzę twoje zamieszanie. Węzły sterty mają co najwyżej dwoje dzieci (stąd znacznik drzewa binarnego)

— varatis

Widzę. Dzięki precyzyjnie sformułowanemu twierdzeniu nie ma potrzeby dalszych założeń. Właściwość ta dotyczy wszystkich drzew binarnych.

— Raphael

Odpowiedzi:

Zakładam teraz, że pytanie jest następujące:

Biorąc pod uwagę drzewo binarne z węzłami, udowodnij, że zawiera co najwyżej $n$ liści. $\left\lceil \frac{n}{2} \right\rceil$

Pracujmy z definicją drzewa . Do takiego drzewa, niech liczba węzłów i liczba liści . $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$ $T$ $n_T$ $T$ $l_T$ $T$

Masz rację, robiąc to indukcyjnie, ale potrzebujesz indukcji strukturalnej, która podąża za strukturą drzewa. W przypadku drzew jest to często wykonywane jako całkowita indukcja powyżej wysokości drzew. $h(T)$

Kotwica indukcyjna składa się z dwóch części. Po pierwsze, dla mamy z ; roszczenie wyraźnie odnosi się do pustego drzewa. Dla , tj. , podobnie mamy $h(t)=0$ $T=\mathrm{Empty}$ $l_T=n_T=0$ $h(t)=1$ $T = \mathrm{Leaf}$ , więc roszczenie dotyczy liści. $l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$

Hipoteza indukcyjna jest następująca: Załóżmy, że twierdzenie dotyczy wszystkich (binarnych) drzew z , arbitralnie, ale ustalone. $T$ $h(T)\leq k$ $k\geq 1$

W kroku indukcyjnym rozważ dowolne drzewo binarne z . A , , a . Ponieważ i są również drzewami binarnymi (inaczej nie byłby) i $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$ , the induction hypothesis applies and have

$\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.$

As all leaves of $T$ are either in $L$ or $R$ , we have that

$\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*}$

The inequality marked with $(*)$ can be checked by (four way) case distinction over whether $n_L,n_R\in 2\mathbb{N}$ . By the power of induction, this concludes the proof.

As an exercise, you can use the same technique to prove the following statements:

Every perfect binary tree of height $h$ has $2^h-1$ nodes.
Every full binary tree has an odd number of nodes.

— Raphael
źródło

I am a little confused by the question. If you are interested in trees with degree at most $3$ , which is what Wikipedia says you want, then we run into the problem that a single edge has $n=2$ nodes and $n=2$ leaves, but $n/2 = 1$ . Anyway, here is something close that has an easy argument.

Let $T$ be such a tree with $n$ nodes and $L$ leaves. Since $T$ is a tree, there are $n-1$ edges, and double counting them, we see that

2 n - 2 \leq L + 3 (n - L)

$2n - 2 \le L + 3(n - L)$ which says that

2 L \leq n + 2

$2L\le n + 2$ and this is tight in the two-vertex example above. I guess that if you want to assume that there one root of degree two and

n \geq 3

$n\ge 3$ , then you can refine this argument to give

2 L \leq n + 1

$2L \le n + 1$ which is what you are looking for, and this is tight when the tree is full.

— Louis
źródło

I guess we silently assume rooted trees here; Wikipedia does so, too.

— Raphael

Wikipedia sort of equivocates, saying: "Outside the tree, there is often a reference to the "root" node (the ancestor of all nodes), if it exists." Anyway, this argument seems worth writing down, since it is different and quite easy.

— Louis

If you read on, all edges are directed, they talk of "children" and "parents". That does not make sense in unrooted trees. In consequence, a leaf would be a node with outdegree 0.

— Raphael