Tas soudable randomisé - Hauteur prévue

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

Pour moi, la hauteur de l'arbre est

h_{Q} = 1 + max {h_{Q_{L}}, h_{Q_{R}}},

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

que je peux développer pour:

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

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$

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

Donc à la fin je reçois:

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

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. $\mathbb{P}[h_{Q_L} > h_{Q_R}]$ $\frac{1}{2}$ $\leq \frac{1}{2}$

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

Merci pour l'aide.

algorithm-analysis data-structures randomized-algorithms heaps Mateusz Wyszyński
la source

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

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

\sum_{ℓ \in feuilles (Q)} profondeur (ℓ) 2^{- profondeur (ℓ)}

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

dont l'entropie d'une distribution un ensemble de taille. $|\text{leaves}(Q)|$

Louis
la source

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

n

$n$

\log n

$\log n$

Tas soudable randomisé - Hauteur prévue

Réponses: