Tas soudable randomisé - Hauteur prévue

9

Les tas soudables randomisés ont une opération "fusion", que nous utilisons ensuite pour définir toutes les autres opérations, y compris l'insertion.

La question est, quelle est la hauteur attendue de cet arbre à n nœuds?

Le théorème 1 de Gambin et Malinkowski, Randomized Meldable Priority Queues (Proceedings of SOFSEM 1998, Lecture Notes in Computer Science vol. 1521, pp. 344–349, 1998; PDF ) donne la réponse à cette question avec preuve. Cependant, je ne comprends pas pourquoi on peut écrire:

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

Pour moi, la hauteur de l'arbre est

hQ=1+max{hQL,hQR},

que je peux développer pour:

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

La probabilité que le maximum d'une hauteur de deux sous-arbres soit égal à peut être réécrite en utilisant la loi de probabilité totale: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].

Donc à la fin je reçois:

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

C'est là que je suis coincé. Je peux voir que est plus ou moins égal (Cependant, nous avons besoin d'au plus ) . Mais sauf que rien ne mène à la formule depuis le début.P[hQL>hQR]1212

Les hauteurs des sous-arbres ne me semblent pas indépendantes.

Merci pour l'aide.

Mateusz Wyszyński
la source

Réponses:

4

Dans le papier, n'est pas la hauteur. C'est la longueur d'une marche aléatoire loin de la racine dans un arbre binaire complet (ils insistent sur le fait que chaque feuille est "nulle"), donc l'expression qu'ils ont est la bonne chose.hQ

De plus, vous pouvez éviter l'induction. La probabilité de se terminer à une feuille spécifique de profondeur n'est que de 2 - d . La durée prévue de la marche est donc2-

feuilles(Q)profondeur()2-profondeur()

dont l'entropie d'une distribution un ensemble de taille.|feuilles(Q)|

Louis
la source
1
Pourriez-vous expliquer plus en détail pourquoi je ne dois pas utiliser l'induction? Je suis d'accord avec la formule pour la durée prévue. Je ne vois tout simplement pas pourquoi ce devrait être O (logn)? Qu'entendez-vous par entropie d'une distribution sur des chaînes?
Mateusz Wyszyński
nJournaln