Bukti bahwa pohon pencarian biner yang dibangun secara acak memiliki tinggi logaritmik

Bagaimana Anda membuktikan bahwa ketinggian yang diharapkan dari pohon pencarian biner yang dibangun secara acak dengan node adalah ? Ada bukti dalam CLRS Pengantar Algoritma (bab 12.4), tapi saya tidak memahaminya.O ( log n $n$$O(\log n)$

Mari kita pikirkan hal ini secara intuitif. Dalam skenario kasus terbaik, pohon itu seimbang sempurna; dalam skenario terburuk, pohon sepenuhnya tidak seimbang:

Mulai dari simpul akar , pohon kiri ini memiliki dua kali lebih banyak node pada setiap kedalaman berikutnya, sehingga pohon tersebut memiliki node dan tinggi (yang dalam hal ini 3). Dengan sedikit matematika, , yang artinya memiliki tinggi. Untuk pohon yang sama sekali tidak seimbang, ketinggian pohon hanyalah . Jadi kita punya batasan.n = ∑ h i = 0 2 i = 2 h + 1 - 1 h n ≤ 2 h + 1 - 1 → h ≤ ⌈ log 2 ( n + 1 ) - 1 ⌉ ≤ ⌊ l o g 2 n ⌋ O ( log n ) n - 1 → O ( n $p$$n=\sum_{i=0}^{h}2^i =2^{h+1}-1$$h$$n\le2^{h+1}-1\rightarrow h\le\lceil\log_2(n+1)-1\rceil\le\lfloor log_2 n\rfloor$$O(\log n)$$n-1\rightarrow O(n)$

Jika kami membangun pohon seimbang dari daftar yang diurutkan , kami akan memilih elemen tengah untuk menjadi simpul akar kami. Jika kita sebaliknya membangun pohon secara acak, salah satu dari simpul tersebut kemungkinan besar akan dipetik dan ketinggian pohon kita adalah: Kita tahu bahwa di pohon pencarian biner, subtree kiri hanya boleh berisi kunci kurang dari simpul root. Jadi, jika kita secara acak memilih elemen , subtree kiri memiliki elemen dan subtree kanan memiliki elemen , jadi lebih kompak:n h e i g h t t r e e = 1 + max ( h e i g h t l e f t s u b t r e e , h e i g h t r i g h t s u b t r e $\{ 1,2,\dots,n\}$$n$i t h i - 1 n - i h n = 1 + maks ( h i - 1 , h n - i ) E [ h n ] =

$$height_{tree}=1+\max (height_{left\space subtree}, height_{right\space subtree})$$ $i^{th}$$i-1$$n-i$$h_n=1+\max (h_{i-1},h_{n-i})$. Dari sana, masuk akal bahwa jika setiap elemen sama-sama cenderung dipetik, nilai yang diharapkan hanyalah rata-rata dari semua kasus (bukan rata-rata tertimbang). Karenanya:$\operatorname{E}[h_n]=\frac{1}{n}\sum_{i=1}^{n}[1+\max (h_{i-1},h_{n-i})]$

Seperti yang saya yakin Anda perhatikan, saya telah sedikit menyimpang dari bagaimana CLRS membuktikan ini, karena CLRS menggunakan dua teknik bukti yang relatif umum yang membingungkan bagi yang belum tahu. Yang pertama adalah menggunakan eksponen (atau logaritma) dari apa yang ingin kita temukan (dalam hal ini tinggi), yang membuat matematika bekerja sedikit lebih bersih; yang kedua adalah menggunakan fungsi indikator (yang saya akan abaikan saja di sini). CLRS mendefinisikan tinggi eksponensial sebagai , sehingga perulangan analognya adalah . Y n = 2 × maks ( Y i - 1 , Y n - i$Y_n=2^{h_n}$$Y_n=2\times\max (Y_{i-1},Y_{n-i})$

Dengan asumsi independensi (bahwa setiap undian elemen (dari elemen yang tersedia) untuk menjadi akar subtree terlepas dari semua undian sebelumnya), kami masih memiliki hubungan: mana saya melakukan dua langkah: (1) memindahkan luar karena itu adalah konstanta dan salah satu sifat penjumlahan adalah , dan (2) memindahkan 2 di luar karena juga merupakan konstanta dan salah satu sifat dari nilai yang diharapkan adalah . Sekarang kita akan mengganti

$$\operatorname{E}[Y_n]=\sum_{i=1}^{n}\frac{1}{n}\operatorname{E}[2\times\max (Y_{i-1},Y_{n-i})]=\frac{2}{n}\sum_{i=1}^{n}\operatorname{E}[\max (Y_{i-1},Y_{n-i})]$$ $\frac{1}{n}$$\sum_i ci=c\sum_i i$$\operatorname{E}[ax]=a\operatorname{E}[x]$$\max$berfungsi dengan sesuatu yang lebih besar karena jika tidak menyederhanakan sulit. Jika kita berdebat untuk tidak negatif , : , lalu: sedemikian sehingga langkah terakhir mengikuti dari pengamatan bahwa untuk , dan dan pergi semua cara untuk , dan , jadi setiap istilah$X$$Y$$\operatorname{E}[\max(X,Y)]\le\operatorname{E}[\max(X,Y)+\min(X,Y)]=\operatorname{E}[X]+\operatorname{E}[Y]$ $$\operatorname{E}[Y_n]\le\frac{2}{n}\sum_{i=1}^{n}(\operatorname{E}[Y_{i-1}]+\operatorname{E}[Y_{n-i}])=\frac{2}{n}\sum_{i=0}^{n-1}2\operatorname{E}[Y_{i}]$$ $i=1$$Y_{i-1}=Y_{0}$$Y_{n-i}=Y_{n-1}$$i=n$$Y_{i-1}=Y_{n-1}$$Y_{n-i}=Y_{0}$$Y_0$untuk muncul dua kali, sehingga kami dapat mengganti seluruh penjumlahan dengan yang penjumlahan. Berita baiknya adalah kita memiliki perulangan ; berita buruknya adalah kita tidak jauh dari tempat kita mulai.$Y_{n-1}$$\operatorname{E}[Y_n]\le\frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_{i}]$

Pada titik ini, CLRS menarik bukti induksi dari ... repertoar pengalaman matematika, yang termasuk identitas mereka serahkan kepada pengguna untuk dibuktikan. Yang penting tentang pilihan mereka adalah istilah terbesarnya adalah , dan ingat bahwa kita menggunakan tinggi eksponensial sedemikian rupa sehingga . Mungkin seseorang akan berkomentar mengapa binomial khusus ini dipilih. Gagasan umum adalah untuk mengikat dari atas pengulangan kita dengan ekspresi untuk beberapa konstanta .$\operatorname{E}[Y_n]\le\frac{1}{4}\binom{n+3}{3}$$\sum_{i=0}^{n-1}\binom{i+3}{3}=\binom{n+3}{4}$$n^3$$Y_n=2^{h_n}$$h_n=\log_2n^3=3\log_2n\rightarrow O(\log n)$$n^k$$k$

Untuk mengakhiri dengan satu liner:

$$2^{\operatorname{E}[X_n]}\le \operatorname{E}[Y_n]\le \frac{4}{n}\sum_{i=0}^{n-1}\operatorname{E}[Y_i]\le\frac{1}{4}\binom{n+3}{3}=\frac{(n+3)(n+2)(n+1)}{24}\rightarrow \operatorname{E}[h_n]=O(\log n)$$