Was ist die durchschnittliche Höhe eines Binärbaums?

Gibt es eine formale Definition für die durchschnittliche Höhe eines Binärbaums?

Ich habe eine Tutorial-Frage zum Ermitteln der durchschnittlichen Höhe eines Binärbaums mithilfe der folgenden zwei Methoden:

1. Die natürliche Lösung könnte darin bestehen, die durchschnittliche Länge aller möglichen Pfade von der Wurzel zu einem Blatt zu nehmen

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

2. Eine andere Möglichkeit besteht darin, es rekursiv zu definieren, dh die durchschnittliche Höhe eines Knotens ist der Durchschnitt über die durchschnittlichen Höhen der Teilbäume plus eins

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

   mit $\operatorname{avh}_2(l) = 1$ für Blätter $l$ und $\operatorname{avh}_2(\_) = 0$ für leere Slots.

Nach meinem derzeitigen Verständnis zum Beispiel die durchschnittliche Höhe des Baumes $T$

    1    
   / \
  2   3
 /
4

ist $\operatorname{avh}_2(T) = 1.25$ nach der zweiten Methode, die Rekursion verwendet.

Ich verstehe jedoch immer noch nicht ganz, wie ich den ersten machen soll. $\operatorname{avh}_1(T) = (1+2)/2=1.5$ ist nicht korrekt.

Es gibt keinen Grund zu der Annahme, dass beide Definitionen dasselbe Maß beschreiben. Sie können rekursiv schreiben :$\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)}$

mit für Blätter . Wenn Sie nicht glauben, dass dies dasselbe ist, entfalten Sie die Definition von auf der rechten Seite oder führen Sie einen Induktionsnachweis durch.$\operatorname{avh}_1(l) = 0$$l$$\operatorname{avh}_1$

Jetzt sehen wir, dass ganz anders funktioniert als . Während die rekursive Höhen von einem Knoten Kinder wiegt gleich (Hinzufügen und Division durch zwei), wiegt sie gemäß der Anzahl der Blätter die sie enthalten. Sie sind also die gleichen (Modulo der Anker) für Bäume mit Blattausgleich, dh in dem Sinne, dass Geschwisterbäume gleich viele Blätter haben. Wenn Sie die rekursive Form von mit vereinfachen, ist dies sofort ersichtlich. Bei unausgeglichenen Bäumen sind sie jedoch unterschiedlich.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)$

Ihre Berechnungen sind in der Tat korrekt (gemäß Ihrer Definition); Beachten Sie, dass der Beispielbaum nicht blattausgeglichen ist.

Bearbeiten: Jeffe macht einen guten Punkt in seinem Kommentar oben. Sie sollten in der folgenden Antwort wahrscheinlich "richtig gegen falsch" als "bequem / konsistent gegen inkonsistent" lesen.

Es scheint, dass Ihre zweite Berechnung falsch ist. Die Höhe eines Teilbaums mit einem einzelnen Knoten (dh einem Blatt) sei 0. Dann ist die Höhe der Teilbaumwurzel bei:

• Höhe bei 4 ist 0
• Höhe bei 3 ist 0
• Höhe bei 2 ist durchschnittliche Höhe bei 3 + 1 = 0 + 1 = 1
• Die Höhe bei 1 ist der Durchschnitt der Höhen bei 2 und 3 = (0 + 1) / 2 + 1 = 1,5

Ich denke, Sie machen die erste Berechnung richtig und 1.5 ist die richtige Antwort.