Qual é a altura média de uma árvore binária?

10

Existe alguma definição formal sobre a altura média de uma árvore binária?

Eu tenho uma pergunta tutorial sobre como encontrar a altura média de uma árvore binária usando os dois métodos a seguir:

  1. A solução natural pode ser usar o comprimento médio de todos os caminhos possíveis, da raiz até a folha, ou seja,

    .avh1(T)=1# leaves in Tv leaf of Tdepth(v)

  2. Outra opção é defini-lo recursivamente, ou seja, a altura média de um nó é a média sobre as alturas médias das subárvores mais uma, ou seja,

    avh2(N(l,r))=avh2(l)+avh2(r)2+1

    com para folhas l e avh 2 ( _ ) = 0 para espaços vazios.avh2(l)=1lavh2(_)=0

Com base no meu entendimento atual, por exemplo, a altura média da árvore T

    1    
   / \
  2   3
 /
4

é pelo segundo método, que está usando recursão.avh2(T)=1.25

avh1(T)=(1+2)/2=1.5

Eterno
fonte
11
Você pode fornecer algum contexto? Não existe uma definição matemática "correta"; você pode definir "altura média de uma árvore binária" como desejar. (Média do que calcula em que distribuição ?) Mas definições diferentes serão mais ou menos úteis para aplicativos diferentes.
JeffE 16/07
@JeffE "Não é imediatamente óbvio como definir a altura média de uma árvore binária. Talvez a solução mais natural seja o comprimento médio dos caminhos possíveis, da raiz à folha. Uma solução mais simples (talvez até simplista) quer dizer que a altura média de um nó é a média acima das alturas médias das subárvores mais uma. Você acha mais fácil codificar essa alternativa. Você pode dar exemplos para demonstrar a diferença? "
Timeless
Tentei deixar sua postagem mais clara, fornecendo definições precisas das duas variantes. Verifique se eu interpretei seu texto corretamente. Em particular, estava faltando a âncora para a segunda variante; se você pega folhas com altura um ou zero faz a diferença.
Raphael

Respostas:

3

avh1

avh1(N(l,r))=lv(l)(avh1(l)+1)+lv(r)(avh1(r)+1)lv(l)+lv(r)

avh1(l)=0lavh1

avh1avh2avh2avh1avh1lv(l)=lv(r)isso é imediatamente aparente. Em árvores desequilibradas, no entanto, elas são diferentes.

Seus cálculos estão realmente corretos (de acordo com sua definição); observe que a árvore de exemplo não é balanceada para folhas.

Rafael
fonte
avh1
avh1
Quero dizer o código de implementação usando recursão
Timeless
@ nulo: Você pode copiar a fórmula quase literalmente , desde que incorpore o caso base. Como fazer isso depende precisamente da linguagem de programação e da implementação da árvore. Eu sugiro que você recorra ao Stack Overflow se a implementação for um obstáculo para você.
Raphael
2

Edit: Jeffe faz um bom ponto em seu comentário acima. Você provavelmente deve ler "correto x incorreto" na resposta a seguir como "conveniente / consistente x inconsistente".

Parece que seu segundo cálculo está incorreto. Deixe a altura de uma subárvore com um único nó (ou seja, uma folha) seja 0. Em seguida, a altura da raiz da subárvore em:

  • altura em 4 é 0
  • altura em 3 é 0
  • altura em 2 é altura média em 3 + 1 = 0 + 1 = 1
  • altura em 1 é a média das alturas em 2 e 3 = (0 + 1) / 2 + 1 = 1,5

Acho que você está fazendo o primeiro cálculo corretamente e 1,5 é a resposta certa.

Joe
fonte
a ideia é nó nulo com altura -1, com base na segunda abordagem, a altura média de um nó é média de subárvores mais 1, a altura média do nó 4 é ((-1) + (- 1)) / 2 + 1 = 0 , a altura média do nó 2 é (0 + (- 1)) / 2 + 1 = 0,5 e, portanto, a altura média da raiz é 1,25.
Timeless
@ null Você pode definir dessa maneira se insistir, mas as duas definições não serão consistentes.
21712 Joe