6.6 Coût des opérations algorithmiques
267
– Si x n’est pas à la racine de τ (ce qui se produit avec probabilité
n
n+1 ), alors la
suppression a lieu dans l’un des deux sous-arbres de τ , et la marque de la racine
de τ est celle de la racine de τ ; donc elle vaut z avec probabilité 1/n.
– Si x est à la racine de τ (ce qui se produit avec probabilité
1
n+1 ), alors l’arbre
τ est le résultat de la fusion des sous-arbres gauche et droit de τ . D’après le
lemme 6.40, il est de loi Ord et de taille n, et donc la marque de sa racine vaut z
avec probabilité 1/n.
La probabilité globale que z se retrouve à la racine de τ vaut donc
n
n + 1
1
n
+
1
n + 1
1
n
=
1
n
.
La proposition 6.36 permet de conclure que τ suit la loi Ord.
6.6 Coût des opérations algorithmiques
Voyons maintenant comment les résultats théoriques obtenus sur divers paramètres
des arbres binaires de recherche se traduisent en termes de coûts algorithmiques.
Nous reprenons ces résultats, d’abord pour les arbres « classiques » obtenus
par insertions successives aux feuilles de clés sous la loi Ord, en section 6.6.1,
puis pour les arbres randomisés en section 6.6.3 ; au passage nous donnons
quelques indications sur les variantes équilibrées des arbres binaires de recherche
en section 6.6.2.
6.6.1 Arbres binaires de recherche classiques
L’analyse des performances des arbres binaires de recherche que nous avons
présentée dans les sections 6.1 et 6.2 suppose que les clés sont indépendantes et
de même loi : c’est le modèle des permutations uniformes présenté en section 2.2.3,
où les clés sont supposées i.i.d. sur [0, 1].
Intuitivement, dans ce modèle les arbres les plus équilibrés, i.e., ceux dont la
hauteur est d’ordre log n, ont la plus forte probabilité d’apparition et les arbres
filiformes « dégénérés », dont la hauteur est d’ordre n, ont une probabilité
exponentiellement faible ; cf. l’exercice 6.1 pour les arbres de taille au plus 4. Nous
donnons dans la figure 6.14 un exemple d’arbre binaire de recherche de taille 1 000,
tiré selon la loi des permutations uniformes : le profil est dans la figure 6.15.
La convergence de la hauteur et de la largeur étant très lente (d’ordre 1/
√
log n
pour la largeur, voir la proposition 6.10), ce dessin correspond à un cas loin du
régime asymptotique (le profil de la figure 6.3, pour un arbre de taille 10 000, donne
une meilleure idée de l’asymptotique).
267
– Si x n’est pas à la racine de τ (ce qui se produit avec probabilité
n
n+1 ), alors la
suppression a lieu dans l’un des deux sous-arbres de τ , et la marque de la racine
de τ est celle de la racine de τ ; donc elle vaut z avec probabilité 1/n.
– Si x est à la racine de τ (ce qui se produit avec probabilité
1
n+1 ), alors l’arbre
τ est le résultat de la fusion des sous-arbres gauche et droit de τ . D’après le
lemme 6.40, il est de loi Ord et de taille n, et donc la marque de sa racine vaut z
avec probabilité 1/n.
La probabilité globale que z se retrouve à la racine de τ vaut donc
n
n + 1
1
n
+
1
n + 1
1
n
=
1
n
.
La proposition 6.36 permet de conclure que τ suit la loi Ord.
6.6 Coût des opérations algorithmiques
Voyons maintenant comment les résultats théoriques obtenus sur divers paramètres
des arbres binaires de recherche se traduisent en termes de coûts algorithmiques.
Nous reprenons ces résultats, d’abord pour les arbres « classiques » obtenus
par insertions successives aux feuilles de clés sous la loi Ord, en section 6.6.1,
puis pour les arbres randomisés en section 6.6.3 ; au passage nous donnons
quelques indications sur les variantes équilibrées des arbres binaires de recherche
en section 6.6.2.
6.6.1 Arbres binaires de recherche classiques
L’analyse des performances des arbres binaires de recherche que nous avons
présentée dans les sections 6.1 et 6.2 suppose que les clés sont indépendantes et
de même loi : c’est le modèle des permutations uniformes présenté en section 2.2.3,
où les clés sont supposées i.i.d. sur [0, 1].
Intuitivement, dans ce modèle les arbres les plus équilibrés, i.e., ceux dont la
hauteur est d’ordre log n, ont la plus forte probabilité d’apparition et les arbres
filiformes « dégénérés », dont la hauteur est d’ordre n, ont une probabilité
exponentiellement faible ; cf. l’exercice 6.1 pour les arbres de taille au plus 4. Nous
donnons dans la figure 6.14 un exemple d’arbre binaire de recherche de taille 1 000,
tiré selon la loi des permutations uniformes : le profil est dans la figure 6.15.
La convergence de la hauteur et de la largeur étant très lente (d’ordre 1/
√
log n
pour la largeur, voir la proposition 6.10), ce dessin correspond à un cas loin du
régime asymptotique (le profil de la figure 6.3, pour un arbre de taille 10 000, donne
une meilleure idée de l’asymptotique).