Pilha fundível aleatória - altura esperada

9

Heaps mescláveis ​​aleatórios possuem uma operação "meld", que usamos para definir todas as outras operações, incluindo insert.

A questão é: qual é a altura esperada dessa árvore com nós?n

O teorema 1 de Gambin e Malinkowski, Filas de prioridade aleatória fundível (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF ) dá a resposta a esta pergunta com prova. No entanto, não entendo por que podemos escrever:

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

Para mim, a altura da árvore é

hQ=1 1+max{hQeu,hQR},

que posso expandir para:

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

A probabilidade de que a altura máxima de duas subárvores seja igual a pode ser reescrita usando a lei da probabilidade total:k

P[max{hQeu,hQR}=k]=P[max{hQeu,hQR}=khQeuhQR]P[hQeuhQR]+P[max{hQeu,hQR}=khQeu>hQR]P[hQeu>hQR]=P[hQR=khQeuhQR]P[hQeuhQR]+P[hQeu=khQeu>hQR]P[hQeu>hQR].

Então, no final, eu recebo:

E[hQ]=1 1+k{P[hQR=khQeuhQR]P[hQeuhQR]+P[hQeu=khQeu>hQR]P[hQeu>hQR]}.

É aqui que estou preso. Eu posso ver que é mais ou menos igual 1P[hQeu>hQR] (No entanto, precisamos no máximo11 12 ) Mas exceto que nada levando à fórmula desde o início.12

As alturas das subárvores não parecem independentes para mim.

Obrigado pela ajuda.

Mateusz Wyszyński
fonte

Respostas:

4

hQnão é a altura. É o comprimento de uma caminhada aleatória da raiz em uma árvore binária completa (eles insistem que todas as folhas são "nulas"), então a expressão que elas têm é a coisa certa.

Além disso, você pode evitar a indução. A probabilidade de terminar em uma folha específica de profundidaded é apenas 2-d. Portanto, a duração esperada da caminhada é

folhas(Q)profundidade()2-profundidade()

qual a entropia de uma distribuição um conjunto de tamanho |folhas(Q)|.

Louis
fonte
11
Você poderia explicar com mais detalhes por que não preciso usar a indução? Eu concordo com a fórmula para o comprimento esperado. Eu simplesmente não vejo por que deveria ser O (logn)? O que você quer dizer com entropia de uma distribuição em strings?
Mateusz Wyszyński 21/03
Porque a entropia de uma distribuição em um conjunto de tamanho n é conhecido por ser maximizado por uma distribuição uniforme; nesse caso, é registron.
Louis