Tumpukan Meldable Acak - Tinggi Diharapkan

Tumpukan Meldable Acak memiliki operasi "berbaur", yang kemudian kita gunakan untuk mendefinisikan semua operasi lain, termasuk memasukkan.

Pertanyaannya adalah, berapa tinggi yang diharapkan dari pohon itu dengan $n$ node?

Teorema 1 dari Gambin dan Malinkowski, Antrian Prioritas Acak yang Dapat Dipotong (Prosiding SOFSEM 1998, Catatan Kuliah dalam Ilmu Komputer vol. 1521, hlm. 344–349, 1998; PDF ) memberikan jawaban untuk pertanyaan ini dengan bukti. Namun, saya tidak mengerti mengapa kita bisa menulis:

$$\mathbb{E} [ h_Q] = \frac{1}{2} ((1 + \mathbb{E}[h_{Q_L}]) + (1 + \mathbb{E}[h_{Q_R}]))\,.$$

Bagi saya ketinggian pohon itu

$$h_Q = 1 + \max\, \{ h_{Q_L}, h_{Q_R}\}\,,$$

yang dapat saya kembangkan ke:

$$\mathbb{E} [ h_Q] = 1 + \mathbb{E}[\max \,\{ h_{Q_L}, h_{Q_R}\}] = 1 + \sum k \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k]\,.$$

Probabilitas bahwa ketinggian maksimum dua subtree sama dengan $k$ dapat ditulis ulang menggunakan hukum probabilitas total:

$$\begin{align*} \hspace{2em}&\hspace{-2em} \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k] \\ &= \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L}\leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\ &\hspace{2em} + \mathbb{P}[\max\, \{ h_{Q_L}, h_{Q_R}\} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \\ &= \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\ &\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}]\,. \end{align*}$$

Jadi pada akhirnya saya dapatkan:

$$\begin{align*}\mathbb{E} [ h_Q] &= 1 + \sum k \{ \mathbb{P}[h_{Q_R} = k \mid h_{Q_L} \leq h_{Q_R}]\,\mathbb{P}[h_{Q_L} \leq h_{Q_R}]\\ &\hspace{2em}+ \mathbb{P}[h_{Q_L} = k \mid h_{Q_L} > h_{Q_R}]\,\mathbb{P}[h_{Q_L} > h_{Q_R}] \}\,. \end{align*}$$

Di sinilah saya terjebak. Saya dapat melihat bahwa kurang lebih sama dengan (Namun kita membutuhkan paling banyak ) . Tapi kecuali itu tidak ada yang mengarah ke formula sejak awal.$\mathbb{P}[h_{Q_L} > h_{Q_R}]$$\frac{1}{2}$$\leq \frac{1}{2}$

Ketinggian anak-anak pohon sepertinya tidak tergantung padaku.

Terimakasih atas bantuannya.

Di koran, bukan tingginya. Itu adalah jarak berjalan acak dari akar di pohon biner penuh (mereka bersikeras setiap daun adalah "nihil"), jadi ungkapan yang mereka miliki adalah hal yang benar.$h_Q$

Anda juga dapat menghindari induksi. Probabilitas berakhir di daun spesifik kedalaman hanya . Jadi panjang jalan yang diharapkan adalah$d$$2^{-d}$

$$\sum_{\ell\in \text{leaves}(Q)} \text{depth}(\ell)2^{-\text{depth}(\ell)}$$

di mana entropi dari distribusi set ukuran.$|\text{leaves}(Q)|$