Berapa tinggi rata-rata pohon biner?

Apakah ada definisi formal tentang tinggi rata-rata pohon biner?

Saya punya pertanyaan tutorial tentang menemukan ketinggian rata-rata pohon biner menggunakan dua metode berikut:

1. Solusi alami mungkin mengambil panjang rata-rata dari semua jalur yang mungkin dari akar ke daun, yaitu

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

2. Pilihan lain adalah untuk mendefinisikannya secara rekursif, yaitu tinggi rata-rata untuk sebuah simpul adalah rata-rata di atas ketinggian rata-rata dari sub pohon ditambah satu, yaitu

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

   dengan untuk daun dan untuk slot kosong.l avh 2 ( _ ) = $\operatorname{avh}_2(l) = 1$$l$$\operatorname{avh}_2(\_) = 0$

Berdasarkan pemahaman saya saat ini, misalnya tinggi rata-rata pohon$T$

    1    
   / \
  2   3
 /
4

is dengan metode kedua, yaitu menggunakan rekursi.$\operatorname{avh}_2(T) = 1.25$

Namun, saya masih tidak mengerti bagaimana melakukan yang pertama. tidak benar.$\operatorname{avh}_1(T) = (1+2)/2=1.5$

Tidak ada alasan untuk percaya bahwa kedua definisi tersebut menggambarkan ukuran yang sama. Anda dapat menulis secara rekursif juga:$\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)}$

dengan untuk daun l . Jika Anda tidak percaya bahwa ini sama, buka definisi avh 1 di sebelah kanan, atau lakukan bukti induksi.$\operatorname{avh}_1(l) = 0$$l$$\operatorname{avh}_1$

Sekarang kita melihat bahwa bekerja sangat berbeda dari avh 2 . Sementara avh 2 menimbang ketinggian rekursif dari simpul anak - anak secara merata (menambah dan membaginya menjadi dua), avh 1 menimbang mereka sesuai dengan jumlah daun yang dikandungnya. Jadi mereka sama (modulo jangkar) untuk pohon-pohon yang seimbang daun, yang seimbang dalam arti bahwa pohon saudara memiliki banyak daun yang sama. Jika Anda menyederhanakan bentuk rekursif avh 1 dengan 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)$ini segera terlihat. Namun, pada pohon yang tidak seimbang, mereka berbeda.

Perhitungan Anda memang benar (diberikan definisi Anda); Perhatikan bahwa pohon contoh tidak seimbang.

Sunting: Jeffe membuat poin bagus dalam komentarnya di atas. Anda mungkin harus membaca "benar vs salah" dalam jawaban berikut sebagai "nyaman / konsisten vs tidak konsisten".

Tampaknya perhitungan kedua Anda salah. Biarkan ketinggian subtree dengan simpul tunggal (yaitu daun) menjadi 0. Kemudian ketinggian root subtree di:

• tinggi pada 4 adalah 0
• tinggi pada 3 adalah 0
• tinggi pada 2 adalah tinggi rata-rata pada 3 + 1 = 0 + 1 = 1
• tinggi pada 1 adalah rata-rata ketinggian pada 2 dan 3 = (0 + 1) / 2 + 1 = 1,5

Saya pikir Anda melakukan perhitungan pertama dengan benar, dan 1,5 adalah jawaban yang tepat.