Jaka jest średnia wysokość drzewa binarnego?

Czy istnieje formalna definicja średniej wysokości drzewa binarnego?

Mam pytanie instruktażowe dotyczące znalezienia średniej wysokości drzewa binarnego przy użyciu następujących dwóch metod:

1. Naturalnym rozwiązaniem może być przyjęcie średniej długości wszystkich możliwych ścieżek od korzenia do liścia

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

2. Inną opcją jest zdefiniowanie go rekurencyjnie, to znaczy średnia wysokość dla węzła to średnia ponad średnich wysokości poddrzewa plus jeden, to znaczy

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

   z dla liści oraz$\operatorname{avh}_2(l) = 1$$l$$\operatorname{avh}_2(\_) = 0$ dla pustych miejsc.

Na podstawie mojego obecnego zrozumienia, na przykład średniej wysokości drzewa $T$

    1    
   / \
  2   3
 /
4

jest według drugiej metody, która wykorzystuje rekurencję.$\operatorname{avh}_2(T) = 1.25$

Nadal jednak nie rozumiem, jak zrobić ten pierwszy. jest niepoprawny.$\operatorname{avh}_1(T) = (1+2)/2=1.5$

Nie ma powodu sądzić, że obie definicje opisują tę samą miarę. Możesz rekurencyjnie napisać avh 1 :$\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)}$

z dla liści l . Jeśli nie wierzysz, że to jest to samo, rozwiń definicję avh 1 po prawej stronie lub wykonaj dowód indukcyjny.$\operatorname{avh}_1(l) = 0$$l$$\operatorname{avh}_1$

Teraz widzimy, że działa zupełnie inaczej niż avh 2 . Podczas gdy avh 2 waży równomiernie wysokości rekurencyjne dzieci węzłów (dodając i dzieląc przez dwa), avh 1 waży je zgodnie z liczbą zawartych w nich liści. Są więc takie same (modulo the anchor) dla drzew zrównoważonych liśćmi, co jest zrównoważone w tym sensie, że rodzeństwo ma tyle samo liści. Jeśli uprościsz rekurencyjną formę avh 1 za pomocą 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)$jest to natychmiast widoczne. Jednak na niezrównoważonych drzewach są one inne.

Twoje obliczenia są rzeczywiście poprawne (biorąc pod uwagę Twoją definicję); zauważ, że przykładowe drzewo nie jest zrównoważone liśćmi.

Edycja: Jeffe ma rację w swoim komentarzu powyżej. Prawdopodobnie powinieneś przeczytać „poprawny kontra nieprawidłowy” w następującej odpowiedzi jako „wygodny / spójny kontra niespójny”.

Wygląda na to, że twoje drugie obliczenie jest nieprawidłowe. Niech wysokość poddrzewa z pojedynczym węzłem (tj. Liściem) będzie wynosić 0. Następnie wysokość korzenia poddrzewa przy:

• wysokość przy 4 wynosi 0
• wysokość przy 3 wynosi 0
• wysokość przy 2 oznacza średnią wysokość przy 3 + 1 = 0 + 1 = 1
• wysokość przy 1 jest średnią wysokości przy 2 i 3 = (0 + 1) / 2 + 1 = 1,5

Myślę, że poprawnie wykonujesz pierwsze obliczenia, a 1.5 to właściwa odpowiedź.