Duas definições de árvores binárias balanceadas

26

Eu vi duas definições de árvores binárias balanceadas, que parecem diferentes para mim.

  1. Uma árvore binária é equilibrada se, para cada nó, considerar que o número de nós internos na subárvore esquerda e o número de nós internos na subárvore direita diferem no máximo em 1.

  2. Uma árvore binária é equilibrada se, para duas folhas, a diferença de profundidade for no máximo 1.

Toda árvore que satisfaz def. 1 também satisfaz a def. 2? E o contrário?

Forrest Gump
fonte
2
Você já tentou provar qualquer direção? Quais são as suas descobertas?
Raphael

Respostas:

17

A definição 1. também é conhecida como equilíbrio de peso weight e a definição 2. como equilíbrio de altura .

O equilíbrio da altura não implica o equilíbrio do peso; exemplos são AVL e Red-Black-Trees. Veja aqui e aqui as provas, respectivamente.

O equilíbrio de peso implica o equilíbrio de altura, no entanto. Isso pode ser comprovado mostrando o seguinte fato mais forte por indução (acima da altura): uma árvore com peso equilibrado é completa em todos os níveis, exceto o mais profundo². O argumento essencial na etapa indutiva é que as subárvores não podem ter uma diferença de altura de mais de um porque - ambas tendo a propriedade reivindicada pela hipótese de indução -, elas não seriam então equilibradas em peso.


  1. O artigo fornece uma definição diferente e mais geral.
  2. Em outras palavras, uma árvore de altura sem as folhas no nível k é uma árvore perfeita de altura k - 1 .kkk1
Rafael
fonte
Acabei de perceber que o fato mais forte pode ser usado para simplificar muito as provas às quais vinculo.
Raphael
Talvez seja uma boa ideia incorporar essa percepção em sua resposta.
Lagarto discreto
@Discretelizard Você quer dizer, as outras respostas?
Raphael
Ah, eu não sabia que esses links eram respostas sobre Ciência da Computação ou que eram suas respostas. De qualquer forma, tudo o que eu queria dizer é que seria uma boa idéia escrever as provas simplificadas. Suas respostas vinculadas parecem ser o local apropriado.
Lagarto discreto