Provar que uma árvore binária tem no máximo

14

Estou tentando provar que uma árvore binária com nós tem no máximo leaves. Como eu faria isso com indução?nn2

Para as pessoas que estavam seguindo a pergunta original sobre pilhas, ela foi movida para aqui .

varatis
fonte
3
Primeiro, observe que podemos usar o LaTeX aqui. Clique em "editar" para ver como eu fiz. Em segundo lugar, não vejo indução. Você está jogando alguns números por aí, mas não existe uma estrutura de prova e nenhuma relação com as pilhas. Você pode melhorar isso? E, finalmente, a afirmação está errada: uma lista classificada cumpre a propriedade heap e possui apenas uma folha. Você deixou de lado algumas suposições?
Raphael
A edição de @ Kaveh's é o que você tinha em mente, ou seja, "no máximo"?
Raphael
@ Rafael, lendo a pergunta novamente, acho que pode ser sobre montões onde cada nó interno tem exatamente dois filhos (nesse caso, a pergunta original faz sentido e a afirmação está correta, ou algo semelhante).
precisa
1
@ Kaveh Ah sim, vejo sua confusão. Nós do heap ter no máximo duas crianças (daí a tag binário-árvore)
varatis
1
Entendo. Com a alegação formulada com precisão, de fato não há necessidade de suposições adicionais. A propriedade é válida para todas as árvores binárias.
Raphael

Respostas:

7

Suponho agora que a pergunta seja a seguinte:

Dada uma árvore binária com nós, prove que ela contém no máximo leaves.nnn2

Vamos trabalhar com a definição de árvore . Para árvore tal, vamos o número de nós em e o número de folhas em .T N T T G T TTree=EmptyLeafNode(Tree,Tree)TnTTlTT

Você está correto ao fazer isso por indução, mas precisará de indução estrutural que segue a estrutura em árvore. Para as árvores, isso geralmente é feito como uma indução completa sobre a altura das árvores.h(T)

A âncora de indução possui duas partes. Primeiro, para , temos T = E m p t y com l T = n T = 0 ; a reivindicação claramente vale para a árvore vazia. Para h ( t ) = 1 , isto é, T = L um e um f , que têm semelhante l T = 1 = n th(t)=0T=EmptylT=nT=0h(t)=1T=Leaf, então a reivindicação é válida para folhas.lT=1=nT2

A hipótese de indução é: Suponha que a reivindicação seja válida para todas as árvores (binárias) com h ( T ) k , k 1 arbitrário, mas fixo.Th(T)kk1

Para a etapa indutiva, considere uma árvore binária arbitrária com h ( T ) = k + 1 . Como k 1 , T = N o d e ( L , R ) e n t = n L + n R + 1 . Como L e R também são árvores binárias (caso contrário, T não seria) e h ( L ) , h (Th(T)=k+1k1T=Node(eu,R)nT=neu+nR+1euRT , a hipótese de indução se aplica e temh(eu),h(R)k

eueuneu2 e euRnR2.

Como todas as folhas de estão em L ou R , temos queTeuR

euT=eueu+euRneu2+nR2neu+nR+12()=nT2

A desigualdade marcado com pode ser verificada por (quatro vias) caso distinção sobre se n G , N R2 N . Pelo poder da indução, isso conclui a prova.()neu,nR2N


Como exercício, você pode usar a mesma técnica para provar as seguintes afirmações:

  • Toda árvore binária perfeita de altura tem 2 h - 1 nós.h2h-1
  • Toda árvore binária completa possui um número ímpar de nós.
Rafael
fonte
2

Estou um pouco confuso com a pergunta. Se você está interessado em árvores com grau máximo de , que é o que a Wikipedia diz que deseja, encontramos o problema de que uma única aresta tem n = 2 nós en = 2 folhas, mas n / 2 = 1 . Enfim, aqui está algo próximo que tem um argumento fácil. 3n=2n=2n/2=1

Seja uma árvore com n nós e L folhas. Como T é uma árvore, existem n - 1 arestas, e as conta duas vezes, vemos que 2 n - 2 L + 3 ( n - L ) que diz que 2 L n + 2 e isso é apertado nas duas Exemplo -vertex acima. Eu acho que se você quiser assumir que existe uma raiz de grau dois en = 3 , então você pode refinar esse argumento para dar 2 LTneuTn-1

2n-2eu+3(n-eu)
2eun+2
n3 que é o que você está procurando, e isso é apertado quando a árvore está cheia.
2eun+1
Louis
fonte
Eu acho que silenciosamente assumimos árvores enraizadas aqui; A Wikipedia também o faz.
Raphael
1
A Wikipedia meio que equivoca, dizendo: "Fora da árvore, geralmente há uma referência ao nó" raiz "(o ancestral de todos os nós), se existir." Enfim, esse argumento parece valer a pena ser anotado, pois é diferente e bastante fácil.
Louis
Se você ler, todas as arestas são direcionadas, elas falam de "filhos" e "pais". Isso não faz sentido em árvores não enraizadas. Em conseqüência, uma folha seria um nó com outdegree 0.
Raphael