Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej ⌈ nliści. Jak miałbym to robić z indukcją?
Dla osób, które śledziły pierwotne pytanie o stosy, zostało tu przeniesione .
Próbuję udowodnić, że drzewo binarne z węzłami ma co najwyżej ⌈ nliści. Jak miałbym to robić z indukcją?
Dla osób, które śledziły pierwotne pytanie o stosy, zostało tu przeniesione .
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 ⌈ nliści.
Pracujmy z definicją drzewa . Do T takiego drzewa, niech n T liczba węzłów T i L T liczba liści 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.
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 T, więc roszczenie dotyczy liści.
Hipoteza indukcyjna jest następująca: Załóżmy, że twierdzenie dotyczy wszystkich (binarnych) drzew z h ( T ) ≤ k , k ≥ 1 arbitralnie, ale ustalone.
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 (, the induction hypothesis applies and have
As all leaves of are either in or , we have that
The inequality marked with can be checked by (four way) case distinction over whether . By the power of induction, this concludes the proof.
As an exercise, you can use the same technique to prove the following statements:
I am a little confused by the question. If you are interested in trees with degree at most , which is what Wikipedia says you want, then we run into the problem that a single edge has nodes and leaves, but . Anyway, here is something close that has an easy argument.
Let be such a tree with nodes and leaves. Since is a tree, there are edges, and double counting them, we see that