Membuktikan pohon biner memiliki paling banyak

Saya mencoba untuk membuktikan bahwa pohon biner dengan node memiliki paling banyak $n$ daun. Bagaimana cara saya melakukan ini dengan induksi? $\left\lceil \frac{n}{2} \right\rceil$

Untuk orang-orang yang mengikuti pertanyaan awal tentang tumpukan, sudah dipindahkan ke sini .

data-structures binary-trees combinatorics graph-theory proof-techniques varatis
sumber

Pertama, perhatikan bahwa kita dapat menggunakan LaTeX di sini. Klik "edit" untuk melihat bagaimana saya melakukannya. Kedua, saya tidak melihat induksi. Anda melempar beberapa angka di sana tetapi tidak ada struktur bukti dan tidak ada hubungannya dengan tumpukan sama sekali. Bisakah Anda memperbaikinya? Dan terakhir, klaim itu salah: daftar yang disortir memenuhi properti tumpukan dan hanya memiliki satu daun. Sudahkah Anda mengabaikan beberapa asumsi?

Raphael

Apakah @ Kaveh mengedit apa yang ada dalam pikiran Anda, yaitu "paling banyak"?

Raphael

@ Raphael, membaca pertanyaan lagi, saya pikir mungkin tentang tumpukan di mana setiap simpul internal memiliki tepat dua anak (dalam hal ini pertanyaan awal masuk akal dan klaim itu benar, atau sesuatu yang serupa).

Kaveh

@ Kaveh Ah ya, saya melihat kebingungan Anda. Node heap memiliki paling banyak dua anak (karenanya tag binary-tree)

varatis

Saya melihat. Dengan klaim yang dirumuskan dengan tepat, memang tidak ada kebutuhan untuk asumsi lebih lanjut. Properti ini berlaku untuk semua pohon biner.

Raphael

Jawaban:

Saya berasumsi sekarang bahwa pertanyaannya adalah sebagai berikut:

Diberi pohon biner dengan simpul, buktikan bahwa ia mengandung paling banyak $n$ $\left\lceil \frac{n}{2} \right\rceil$ daun.

Mari kita bekerja dengan definisi pohon . Untuk seperti pohon, biarkan jumlah node dalam dan jumlah daun dalam $\mathrm{Tree}= \mathrm{Empty}\mid \mathrm{Leaf} \mid \mathrm{Node}(\mathrm{Tree},\mathrm{Tree})$ $T$ $n_T$ $T$ $l_T$ $T$ .

Anda benar untuk melakukan ini dengan induksi, tetapi Anda akan memerlukan induksi struktural yang mengikuti struktur pohon. Untuk pohon, ini sering dilakukan sebagai induksi lengkap pada ketinggian pohon. $h(T)$

Jangkar induksi memiliki dua bagian. Pertama, untuk kita memiliki dengan ; klaim jelas berlaku untuk pohon kosong. Untuk , yaitu , kami memiliki $h(t)=0$ $T=\mathrm{Empty}$ $l_T=n_T=0$ $h(t)=1$ $T = \mathrm{Leaf}$ $l_T=1=\left\lceil \frac{n_T}{2} \right\rceil$ , jadi klaimnya berlaku untuk daun.

Hipotesis induksi adalah: Asumsikan bahwa klaim berlaku untuk semua (binary) pohon dengan , $T$ $h(T)\leq k$ $k\geq 1$ sewenang-wenang tetapi tetap.

Untuk langkah induktif, pertimbangkan pohon biner acak dengan . Sebagai , dan . Karena dan juga merupakan pohon biner (jika tidak tidak akan) dan $T$ $h(T)=k+1$ $k\geq 1$ $T=\mathrm{Node}(L,R)$ $n_T = n_L+ n_R+1$ $L$ $R$ $T$ $h(L),h(R)\leq k$ , hipotesis induksi berlaku dan miliki

$\qquad \displaystyle l_L \leq \left\lceil \frac{n_L}{2} \right\rceil \text{ and } l_R \leq \left\lceil \frac{n_R}{2} \right\rceil.$

Karena semua daun berada di atau , kami memilikinya $T$ $L$ $R$

$\qquad \begin{align*} l_T &= l_L + l_R \\ &\leq \left\lceil \frac{n_L}{2} \right\rceil + \left\lceil \frac{n_R}{2} \right\rceil \\ &\leq \left\lceil \frac{n_L + n_R + 1}{2} \right\rceil \qquad (*)\\ &= \left\lceil \frac{n_T}{2} \right\rceil \end{align*}$

Ketimpangan yang ditandai dengan dapat diperiksa dengan (empat arah) kasus perbedaan apakah . Dengan kekuatan induksi, ini menyimpulkan buktinya. $(*)$ $n_L,n_R\in 2\mathbb{N}$

Sebagai latihan, Anda dapat menggunakan teknik yang sama untuk membuktikan pernyataan berikut:

Setiap pohon biner sempurna dengan ketinggian memiliki node. $h$ $2^h-1$
Setiap pohon biner penuh memiliki jumlah ganjil node.

Raphael
sumber

$3$ $n=2$ $n=2$ $n/2 = 1$ . Bagaimanapun, ini adalah sesuatu yang dekat yang memiliki argumen yang mudah.

$T$ $n$ $L$ $T$ $n-1$ tepi, dan menghitung dua kali lipat, kita melihat itu

2 n - 2 \leq L. + 3 (n - L.)

$2n - 2 \le L + 3(n - L)$ yang mengatakan itu

2 L. \leq n + 2

$2L\le n + 2$ dan ini ketat pada contoh dua-simpul di atas. Saya kira jika Anda ingin berasumsi bahwa ada satu akar tingkat dua dan

n \geq 3

$n\ge 3$ , maka Anda dapat mempersempit argumen ini untuk diberikan

2 L. \leq n + 1

$2L \le n + 1$ itulah yang Anda cari, dan ini kencang ketika pohonnya sudah penuh.

Louis
sumber

Saya kira kita diam-diam menganggap pohon yang berakar di sini; Wikipedia juga melakukannya.

Raphael

Wikipedia mengelak, mengatakan: "Di luar pohon, sering ada referensi ke simpul" root "(nenek moyang semua node), jika ada." Lagi pula, argumen ini tampaknya layak ditulis, karena berbeda dan cukup mudah.

Louis

Jika Anda membaca terus, semua ujung diarahkan, mereka berbicara tentang "anak-anak" dan "orang tua". Itu tidak masuk akal di pohon-pohon yang tidak dijarah. Karena itu, daun akan menjadi simpul dengan outdegree 0.

Raphael