Batas bawah pada jumlah jalur "pendek" di pohon berakar dengan ukuran polinomial

Biarkan menjadi pohon biner yang di-root. Setiap jalur dari akar ke daun memiliki panjang . Setiap simpul selalu memiliki simpul anak kiri dan kanan tetapi ada kemungkinan bahwa keduanya sama (Jadi selalu ada jalur yang mungkin). Ukuran dibatasi oleh . Sebuah simpul dengan simpul anak yang berbeda disebut simpul percabangan .$T$$T$$n$$T$$2^n$$T$$O(poly(n))$

Kita mengatakan bahwa dua jalur berbeda jika ada satu simpul percabangan bersama dan satu jalur menuju ke simpul anak kiri dan jalur lainnya menuju ke simpul anak yang tepat. Jelas bahwa setidaknya ada satu jalur di dengan node bercabang. Jika tidak akan ada terlalu banyak node di .$T$$O(\log n)$$T$

Apakah ada batas bawah yang lebih baik pada jumlah lintasan dengan simpul bercabang jika saya tahu ada simpul percabangan di pohon?$O(\log n)$$\omega(\log n)$

Batas bawah adalah jalur dengan O ( log n ) node bercabang, jika Anda memiliki setidaknya Ω ( log n ) node bercabang di pohon.$\Omega(\log n)$$O(\log n)$$\Omega(\log n)$

Ini dapat dicapai: gunakan pohon yang memiliki satu jalur panjang (panjang ) yang semua simpulnya adalah simpul bercabang, tanpa simpul percabangan lain di pohon itu.$n$

Berikut ini adalah sketsa dari batas bawah.

Pertama, kompakkan pohon dengan mengontrak setiap simpul interior yang bukan simpul percabangan. Jika ukuran asli dari pohon itu , pohon baru masih harus < n c , karena Anda hanya mengurangi jumlah node. Sekarang, kedalaman daun adalah jumlah node bercabang di jalur asli ke daun itu, dan kami memiliki pohon biner lengkap (setiap node memiliki derajat 2 atau 0).$< n^c$$< n^c$

$\Omega(\log n)$$\Omega(\log n)$$\Omega(\log n)$

$d(v)$$\Sigma_{v \mathrm{\ leaf}} 2^{-d(v)} = 1$

$n^c$$O(\log n)$$\log_2(n^{c+1}) = (c+1) \log_2 n$$1/n$$v$$d(v)\leq (c+1) \log_2 n$$\sum_{v\mathrm{\ low \ depth \ leaf}} 2^{-d(v)} > 1-\frac{1}{n}$$\sum_{v\mathrm{\ low\ depth\ leaf}} 2^{-d(v)} < 1$

$2^{-k}$$1$$1-\frac{1}{n}$$\log_2 n$$\Omega(\log n)$$O(\log n)$