Udowodnienie, że drzewo binarne ma co najwyżej

14

Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej nnliści. Jak miałbym to robić z indukcją?n2

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

varatis
źródło
3
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
1
@Kaveh Ach tak, widzę twoje zamieszanie. Węzły sterty mają co najwyżej dwoje dzieci (stąd znacznik drzewa binarnego)
varatis
1
Widzę. Dzięki precyzyjnie sformułowanemu twierdzeniu nie ma potrzeby dalszych założeń. Właściwość ta dotyczy wszystkich drzew binarnych.
Raphael

Odpowiedzi:

7

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 nnliści.n2

Pracujmy z definicją drzewa . Do T takiego drzewa, niech n T liczba węzłów T i L T liczba liści T .Tree=EmptyLeafNode(Tree,Tree)TnTTlTT

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 T = E m p t y z l T = n T = 0 ; roszczenie wyraźnie odnosi się do pustego drzewa. Dla h ( t ) = 1 , tj. T = L e a f , podobnie mamy l T = 1 = n Th(t)=0T=EmptylT=nT=0h(t)=1T=Leaf, więc roszczenie dotyczy liści.lT=1=nT2

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

W kroku indukcyjnym rozważ dowolne drzewo binarne z h ( T ) = k + 1 . A k 1 , T = N O d e ( L , R ) , a n , T = n L + n R + 1 . Ponieważ L i R są również drzewami binarnymi (inaczej T nie byłby) i h ( L ) , h (Th(T)=k+1k1T=Node(L,R)nT=nL+nR+1LRTh(L),h(R)k, the induction hypothesis applies and have

lLnL2 and lRnR2.

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

lT=lL+lRnL2+nR2nL+nR+12()=nT2

The inequality marked with () can be checked by (four way) case distinction over whether nL,nR2N. 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 2h1 nodes.
  • Every full binary tree has an odd number of nodes.
Raphael
źródło
2

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 n1 edges, and double counting them, we see that

2n2L+3(nL)
which says that
2Ln+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 n3, then you can refine this argument to give
2Ln+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
1
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