¿Cuál es la altura promedio de un árbol binario?

¿Existe alguna definición formal sobre la altura promedio de un árbol binario?

Tengo una pregunta tutorial sobre cómo encontrar la altura promedio de un árbol binario usando los siguientes dos métodos:

1. La solución natural podría ser tomar la longitud promedio de todos los caminos posibles desde la raíz hasta una hoja, es decir

   $\qquad \displaystyle \operatorname{avh}_1(T) = \frac{1}{\text{# leaves in } T} \cdot \sum_{v \text{ leaf of } T} \operatorname{depth}(v)$ .

2. Otra opción es definirlo de forma recursiva, es decir, la altura promedio de un nodo es el promedio sobre las alturas promedio de los subárboles más uno, es decir

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

   con para hojas y para espacios vacíos.l avh 2 ( _ ) = $\operatorname{avh}_2(l) = 1$$l$$\operatorname{avh}_2(\_) = 0$

Según mi comprensión actual, por ejemplo, la altura promedio del árbol$T$

    1    
   / \
  2   3
 /
4

is por el segundo método, que es usar recursividad.$\operatorname{avh}_2(T) = 1.25$

Sin embargo, todavía no entiendo cómo hacer el primero. no es correcto.$\operatorname{avh}_1(T) = (1+2)/2=1.5$

No hay razón para creer que ambas definiciones describan la misma medida. También puede escribir recursiva:$\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)}$

con para hojas l . Si no cree que esto sea lo mismo, despliegue la definición de avh 1 en el lado derecho o realice una prueba de inducción.$\operatorname{avh}_1(l) = 0$$l$$\operatorname{avh}_1$

Ahora vemos que funciona de manera bastante diferente a avh 2 . Mientras que avh 2 pesa las alturas recursivas de los niños nodos por igual (sumando y dividiendo entre dos), avh 1 los pesa de acuerdo con la cantidad de hojas que contienen. Por lo tanto, son los mismos (módulo de anclaje) para los árboles con balance de hojas, que se equilibra en el sentido de que los árboles hermanos tienen igualmente tantas hojas. Si simplifica la forma recursiva de avh 1 con lv ( l ) = lv ( r $\operatorname{avh}_1$$\operatorname{avh}_2$$\operatorname{avh}_2$$\operatorname{avh}_1$$\operatorname{avh}_1$$\operatorname{lv}(l) = \operatorname{lv}(r)$Esto es inmediatamente evidente. En los árboles desequilibrados, sin embargo, son diferentes.

Sus cálculos son correctos (dada su definición); tenga en cuenta que el árbol de ejemplo no está balanceado en hojas.

Editar: Jeffe hace un buen punto en su comentario anterior. Probablemente debería leer "correcto versus incorrecto" en la siguiente respuesta como "conveniente / consistente versus inconsistente".

Parece ser que su segundo cálculo es incorrecto. Deje que la altura de un subárbol con un solo nodo (es decir, una hoja) sea 0. Luego, la altura de la raíz del subárbol en:

• la altura a las 4 es 0
• la altura a 3 es 0
• la altura a 2 es la altura promedio a 3 + 1 = 0 + 1 = 1
• la altura en 1 es el promedio de las alturas en 2 y 3 = (0 + 1) / 2 + 1 = 1.5

Creo que está haciendo el primer cálculo correctamente, y 1.5 es la respuesta correcta.