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

9

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

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

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

E[hQ]=12((1+E[hQL])+(1+E[hQR])).

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

hQ=1+max{hQL,hQR},

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

E[hQ]=1+E[max{hQL,hQR}]=1+kP[max{hQL,hQR}=k].

Вероятность того, что максимум высоты двух поддеревьев равен k можно переписать, используя закон полной вероятности:

P[max{hQL,hQR}=k]=P[max{hQL,hQR}=khQLhQR]P[hQLhQR]+P[max{hQL,hQR}=khQL>hQR]P[hQL>hQR]=P[hQR=khQLhQR]P[hQLhQR]+P[hQL=khQL>hQR]P[hQL>hQR].

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

E[hQ]=1+k{P[hQR=khQLhQR]P[hQLhQR]+P[hQL=khQL>hQR]P[hQL>hQR]}.

Вот где я застрял. Я вижу, что более или менее равен (однако нам нужно самое большее ) , Но кроме этого ничего не привело к формуле с самого начала.P[hQL>hQR]1212

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

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

Матеуш Вышинский
источник

Ответы:

4

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

Кроме того, вы можете избежать индукции. Вероятность окончания на конкретном листе глубины составляет всего . Таким образом, ожидаемая продолжительность прогулкиd2d

leaves(Q)depth()2depth()

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

Луис
источник
1
Не могли бы вы объяснить более подробно, почему я не должен использовать индукцию? Я согласен с формулой ожидаемой длины. Я просто не понимаю, почему это должно быть O (logn)? Что вы подразумеваете под энтропией распределения по строкам?
Матеуш Вышинский
Поскольку хорошо известно, что энтропия распределения на множестве размера максимизируется равномерным распределением, в этом случае оно равно . nlogn
Луи