6.6 Coût des opérations algorithmiques
269
Longueur de cheminement Nous avons étudié la longueur de cheminement et
la profondeur d’insertion dans la section 6.1. Nous avons d’abord obtenu leur
moyenne dans le théorème 6.2, puis la variance de la longueur de cheminement
dans le théorème 6.3, et la fonction génératrice de la loi de la profondeur d’insertion
dans la proposition 6.7. Nous avons ensuite montré dans le théorème 6.8 qu’après
renormalisation, le polynôme de niveau, qui synthétise l’information sur le nombre
de feuilles à chaque niveau, est une martingale, et en avons déduit différentes
convergences. Puis nous avons repris l’étude de la longueur de cheminement dans
le théorème 6.11, et montré qu’elle aussi, après normalisation, est une martingale et
converge vers une limite aléatoire, que nous avons précisée dans le théorème 6.17
comme solution d’une équation de point fixe en distribution. La méthode de
contraction de la section 6.1.3 fournit un outil permettant de simuler cette limite,
ce que nous avons fait en section 6.1.4. Au passage, nous avons obtenu dans le
théorème 6.12 une convergence du nombre de feuilles à niveau donné (à l’échelle
log n), après normalisation, vers la martingale limite.
Hauteur En ce qui concerne la hauteur, un argument simple nous a d’abord servi à
montrer dans la section 6.2.1 que, contrairement aux arbres binaires sous le modèle
de Catalan dont la hauteur est d’ordre
√
n (cf. le théorème 5.20), les arbres binaires
de recherche ont une hauteur d’ordre log n. Le théorème 6.22 a ensuite montré que la
hauteur et le niveau de saturation sont effectivement tous les deux asymptotiquement
équivalents à c log n et c log n respectivement, en identifiant les deux constantes c
et c . Enfin, dans le théorème 6.27, plus raffiné, puisqu’il concerne les fluctuations
de la hauteur autour de sa moyenne, il apparaît que ces fluctuations convergent en
probabilité, mais non presque sûrement.
Insertion et recherche D’un point de vue algorithmique, les résultats que nous
venons de rappeler nous permettent d’étudier finement les coûts des opérations
d’insertion et de recherche. 11 La recherche peut elle-même être avec ou sans succès,
selon qu’elle porte sur une clé x déjà présente dans l’arbre, ou non. Dans ce dernier
cas le coût, en terme de comparaisons de clés présentes dans l’arbre avec x, est égal
au nombre de comparaisons qu’il faudrait faire pour insérer x : la recherche sans
succès s’arrête sur la feuille de l’arbre complété où irait x. Le coût d’une insertion
aux feuilles, comme celui d’une recherche sans succès, est donné par la profondeur
d’insertion et lié à la longueur de cheminement externe de l’arbre complété ; il est
d’ordre logarithmique en moyenne, et converge après normalisation vers une loi
limite non gaussienne.
Le coût d’une recherche avec succès est lié à la longueur de cheminement
interne ; lui aussi est en moyenne d’ordre logarithmique, et converge vers une loi
limite non gaussienne.
Quant au maximum du coût des opérations précédentes sur un arbre, il est
donné par la hauteur : la configuration la plus défavorable est celle où l’insertion
(ou la recherche) conduit à une des feuilles les plus profondes de l’arbre. Bien
11 Nous avons déjà mis en lien ces coûts avec les paramètres de l’arbre en section 3.2.1.
269
Longueur de cheminement Nous avons étudié la longueur de cheminement et
la profondeur d’insertion dans la section 6.1. Nous avons d’abord obtenu leur
moyenne dans le théorème 6.2, puis la variance de la longueur de cheminement
dans le théorème 6.3, et la fonction génératrice de la loi de la profondeur d’insertion
dans la proposition 6.7. Nous avons ensuite montré dans le théorème 6.8 qu’après
renormalisation, le polynôme de niveau, qui synthétise l’information sur le nombre
de feuilles à chaque niveau, est une martingale, et en avons déduit différentes
convergences. Puis nous avons repris l’étude de la longueur de cheminement dans
le théorème 6.11, et montré qu’elle aussi, après normalisation, est une martingale et
converge vers une limite aléatoire, que nous avons précisée dans le théorème 6.17
comme solution d’une équation de point fixe en distribution. La méthode de
contraction de la section 6.1.3 fournit un outil permettant de simuler cette limite,
ce que nous avons fait en section 6.1.4. Au passage, nous avons obtenu dans le
théorème 6.12 une convergence du nombre de feuilles à niveau donné (à l’échelle
log n), après normalisation, vers la martingale limite.
Hauteur En ce qui concerne la hauteur, un argument simple nous a d’abord servi à
montrer dans la section 6.2.1 que, contrairement aux arbres binaires sous le modèle
de Catalan dont la hauteur est d’ordre
√
n (cf. le théorème 5.20), les arbres binaires
de recherche ont une hauteur d’ordre log n. Le théorème 6.22 a ensuite montré que la
hauteur et le niveau de saturation sont effectivement tous les deux asymptotiquement
équivalents à c log n et c log n respectivement, en identifiant les deux constantes c
et c . Enfin, dans le théorème 6.27, plus raffiné, puisqu’il concerne les fluctuations
de la hauteur autour de sa moyenne, il apparaît que ces fluctuations convergent en
probabilité, mais non presque sûrement.
Insertion et recherche D’un point de vue algorithmique, les résultats que nous
venons de rappeler nous permettent d’étudier finement les coûts des opérations
d’insertion et de recherche. 11 La recherche peut elle-même être avec ou sans succès,
selon qu’elle porte sur une clé x déjà présente dans l’arbre, ou non. Dans ce dernier
cas le coût, en terme de comparaisons de clés présentes dans l’arbre avec x, est égal
au nombre de comparaisons qu’il faudrait faire pour insérer x : la recherche sans
succès s’arrête sur la feuille de l’arbre complété où irait x. Le coût d’une insertion
aux feuilles, comme celui d’une recherche sans succès, est donné par la profondeur
d’insertion et lié à la longueur de cheminement externe de l’arbre complété ; il est
d’ordre logarithmique en moyenne, et converge après normalisation vers une loi
limite non gaussienne.
Le coût d’une recherche avec succès est lié à la longueur de cheminement
interne ; lui aussi est en moyenne d’ordre logarithmique, et converge vers une loi
limite non gaussienne.
Quant au maximum du coût des opérations précédentes sur un arbre, il est
donné par la hauteur : la configuration la plus défavorable est celle où l’insertion
(ou la recherche) conduit à une des feuilles les plus profondes de l’arbre. Bien
11 Nous avons déjà mis en lien ces coûts avec les paramètres de l’arbre en section 3.2.1.