Рандомизированная складываемая куча - ожидаемая высота

Рандомизированные связываемые кучи имеют операцию «соединение», которую мы затем используем для определения всех других операций, включая вставку.

Вопрос в том, какова ожидаемая высота этого дерева с узлами?$n$

Теорема 1 Гамбина и Малинковского « Рандомизированные смешиваемые приоритетные очереди» (Труды SOFSEM 1998, лекция по информатике, том 1521, с. 344–349, 1998; PDF ) дает ответ на этот вопрос с доказательством. Однако я не понимаю, почему мы можем написать:

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

Для меня высота дерева

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

который я могу расширить до:

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

Вероятность того, что максимум высоты двух поддеревьев равен $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*}$$

Итак, в конце я получаю:

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

Вот где я застрял. Я вижу, что более или менее равен (однако нам нужно самое большее ) , Но кроме этого ничего не привело к формуле с самого начала.$\mathbb{P}[h_{Q_L} > h_{Q_R}]$$\frac{1}{2}$$\leq \frac{1}{2}$

Высоты поддеревьев не кажутся мне независимыми.

Спасибо за помощь.

В статье не высота. Это длина случайного отхода от корня в полном двоичном дереве (они настаивают на том, что каждый лист «ноль»), поэтому выражение, которое они имеют, является правильным.$h_Q$

Кроме того, вы можете избежать индукции. Вероятность окончания на конкретном листе глубины составляет всего . Таким образом, ожидаемая продолжительность прогулки$d$$2^{-d}$

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

какая энтропия распределения множество размеров,$|\text{leaves}(Q)|$