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ć:

E [h_{Q}] = \frac{1}{2} ((1 + E [h_{Q_{L}}]) + (1 + E [h_{Q_{R}}])) .

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

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

które mogę rozwinąć do:

E [h_{Q}] = 1 + E [max {h_{Q_{L}}, h_{Q_{R}}}] = 1 + \sum k P [max {h_{Q_{L}}, h_{Q_{R}}} = k] .

$\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{aligned} P [max {h_{Q_{L}}, h_{Q_{R}}} = k] \\ = P [max {h_{Q_{L}}, h_{Q_{R}}} = k ∣ h_{Q_{L}} \leq h_{Q_{R}}] P [h_{Q_{L}} \leq h_{Q_{R}}] \\ + P [max {h_{Q_{L}}, h_{Q_{R}}} = k ∣ h_{Q_{L}} > h_{Q_{R}}] P [h_{Q_{L}} > h_{Q_{R}}] \\ = P [h_{Q_{R}} = k ∣ h_{Q_{L}} \leq h_{Q_{R}}] P [h_{Q_{L}} \leq h_{Q_{R}}] \\ + P [h_{Q_{L}} = k ∣ h_{Q_{L}} > h_{Q_{R}}] P [h_{Q_{L}} > h_{Q_{R}}] . \end{aligned}

$\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{aligned} E [h_{Q}] & = 1 + \sum k {P [h_{Q_{R}} = k ∣ h_{Q_{L}} \leq h_{Q_{R}}] P [h_{Q_{L}} \leq h_{Q_{R}}] \\ + P [h_{Q_{L}} = k ∣ h_{Q_{L}} > h_{Q_{R}}] P [h_{Q_{L}} > h_{Q_{R}}]} . \end{aligned}

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

— Mateusz Wyszyński
źródło

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_{ℓ \in leaves (Q)} depth (ℓ) 2^{- depth (ℓ)}

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

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

— Louis
źródło

Czy możesz wyjaśnić bardziej szczegółowo, dlaczego nie muszę korzystać z indukcji? Zgadzam się z formułą oczekiwanej długości. Po prostu nie rozumiem, dlaczego powinien to być O (logn)? Co rozumiesz przez entropię rozkładu na łańcuchach?

— Mateusz Wyszyński

Ponieważ entropia rozkładu na zbiorze wielkości jest dobrze znana z tego, że maksymalizuje się przez rozkład równomierny, w którym to przypadku jest to .

n

$n$

\log n

$\log n$

— Louis