Randomized Meldable Heap - Oczekiwana wysokość

Randomizowane zgrzewalne stosy mają operację „łączenie”, której następnie używamy do zdefiniowania wszystkich innych operacji, w tym wstawiania.

Pytanie brzmi: jaka jest oczekiwana wysokość tego drzewa $n$ węzły?

Twierdzenie 1 Gambina i Malinkowskiego, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, ss. 344–349, 1998; PDF ) daje odpowiedź na to pytanie wraz z dowodem. Nie rozumiem jednak, dlaczego możemy pisać:

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

Dla mnie wysokość drzewa jest

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

które mogę rozwinąć do:

$$\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]\,.$$

Prawdopodobieństwo, że maksymalna wysokość dwóch poddrzewa jest równa może zostać przepisane na podstawie zasady całkowitego prawdopodobieństwa:$k$

$$\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*}$$

Na koniec otrzymuję:

$$\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*}$$

Tu utknąłem. Widzę, że jest mniej więcej równy (jednak potrzebujemy co najwyżej ) . Ale z wyjątkiem tego, że nic nie prowadzi do formuły od samego początku.$\mathbb{P}[h_{Q_L} > h_{Q_R}]$$\frac{1}{2}$$\leq \frac{1}{2}$

Wysokości poddrzewa nie wydają mi się niezależne.

Dzięki za pomoc.

W artykule nie jest wysokością. Jest to długość przypadkowego odejścia od korzenia w pełnym drzewie binarnym (twierdzą, że każdy liść jest „zero”), więc wyrażenie, które mają, jest właściwe.$h_Q$

Możesz także uniknąć indukcji. Prawdopodobieństwo zakończenia na określonym liściu głębokości wynosi zaledwie . Tak więc oczekiwana długość spaceru to$d$$2^{-d}$

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

której entropia rozkładu jest zbiorem rozmiaru.$|\text{leaves}(Q)|$