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

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,

   .$\qquad \displaystyle \operatorname{avh}_1(T) = \frac{1}{\text{# leaves in } T} \cdot \sum_{v \text{ leaf of } T} \operatorname{depth}(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,

   $\qquad \displaystyle \operatorname{avh}_2(N(l,r)) = \frac{\operatorname{avh}_2(l) + \operatorname{avh}_2(r)}{2} + 1$

   com para folhas l e avh 2 ( _ ) = 0 para espaços vazios.$\operatorname{avh}_2(l) = 1$$l$$\operatorname{avh}_2(\_) = 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.$\operatorname{avh}_2(T) = 1.25$

$\operatorname{avh}_1(T) = (1+2)/2=1.5$

$\operatorname{avh}_1$

$\qquad \displaystyle \operatorname{avh}_1(N(l,r)) = \frac{\operatorname{lv}(l)(\operatorname{avh_1}(l) + 1) + \operatorname{lv}(r)(\operatorname{avh_1}(r) + 1)}{\operatorname{lv}(l) + \operatorname{lv}(r)}$

$\operatorname{avh}_1(l) = 0$$l$$\operatorname{avh}_1$

$\operatorname{avh}_1$$\operatorname{avh}_2$$\operatorname{avh}_2$$\operatorname{avh}_1$$\operatorname{avh}_1$$\operatorname{lv}(l) = \operatorname{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.

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.