Quelle est la hauteur moyenne d'un arbre binaire?

Existe-t-il une définition formelle de la hauteur moyenne d'un arbre binaire?

J'ai une question de didacticiel sur la recherche de la hauteur moyenne d'un arbre binaire en utilisant les deux méthodes suivantes:

1. La solution naturelle pourrait être de prendre la longueur moyenne de tous les chemins possibles de la racine à une feuille, c'est-à-dire

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

2. Une autre option consiste à le définir récursivement, c'est-à-dire que la hauteur moyenne d'un nœud est la moyenne sur les hauteurs moyennes des sous-arbres plus un, c'est-à-dire

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

   avec pour leafs et pour les emplacements vides.l avh 2 ( _ ) = $\operatorname{avh}_2(l) = 1$$l$$\operatorname{avh}_2(\_) = 0$

Sur la base de ma compréhension actuelle, par exemple la hauteur moyenne de l'arbre$T$

    1    
   / \
  2   3
 /
4

is par la deuxième méthode, qui utilise la récursivité.$\operatorname{avh}_2(T) = 1.25$

Cependant, je ne comprends toujours pas comment faire la première. n'est pas correct.$\operatorname{avh}_1(T) = (1+2)/2=1.5$

Il n'y a aucune raison de croire que les deux définitions décrivent la même mesure. Vous pouvez également écrire manière récursive:$\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)}$

avec pour les feuilles . Si vous ne pensez pas que ce soit la même chose, dépliez la définition de sur le côté droit ou effectuez une preuve d'induction.l avh $\operatorname{avh}_1(l) = 0$$l$$\operatorname{avh}_1$

Nous voyons maintenant que fonctionne assez différemment de . Alors que pèse les hauteurs récursives d'un enfant de nœuds aussi ( en ajoutant et en divisant par deux), les soupèse en fonction du nombre de feuilles qu'ils contiennent. Ils sont donc les mêmes (modulo l'ancre) pour les arbres à feuilles équilibrées, c'est-à-dire équilibrés dans le sens où les arbres frères ont autant de feuilles. Si vous simplifiez la forme récursive de avec cela apparaît immédiatement. Sur les arbres déséquilibrés, cependant, ils sont différents.avh 2 avh 2 avh 1 avh 1 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)$

Vos calculs sont en effet corrects (compte tenu de votre définition); notez que l'exemple d'arbre n'est pas équilibré en feuilles.

Edit: Jeffe fait un bon point dans son commentaire ci-dessus. Vous devriez probablement lire «correct vs incorrect» dans la réponse suivante comme «pratique / cohérent vs incohérent».

Il semble que votre deuxième calcul soit incorrect. Soit la hauteur d'un sous-arbre avec un seul nœud (c'est-à-dire une feuille) égale à 0. Ensuite, la hauteur de la racine du sous-arbre à:

• la hauteur à 4 est 0
• la hauteur à 3 est 0
• hauteur à 2 est la hauteur moyenne à 3 + 1 = 0 + 1 = 1
• la hauteur à 1 est la moyenne des hauteurs à 2 et 3 = (0 + 1) / 2 + 1 = 1,5

Je pense que vous faites correctement le premier calcul, et 1,5 est la bonne réponse.