Chapitre 6
Arbres binaires de recherche
Les arbres binaires de recherche (en abrégé abr) ont été introduits dans la section 1.2.5, et l’aléa sur ces arbres dans la section 2.2.3. Le mot aléatoire est
sous-entendu dans la suite, mais ils le sont bien, et l’aléa sur les abr est la loi
Ord dans les sections 6.1 à 6.4. Nous rappelons (cf. la définition 2.9) que cette loi
Ord est la loi sur les arbres binaires de recherche sous le modèle des permutations
uniformes, lorsque les clés insérées sont des variables aléatoires i.i.d. de même loi
uniforme sur l’intervalle [0, 1], et que l’arbre est construit par insertions successives
aux feuilles (figure 6.1).
Nous avons vu dans la section 3.2.1 que les performances des opérations de
recherche, avec et sans succès, et d’insertion dans un arbre binaire de recherche sont
déterminées par des paramètres de l’arbre tels que ses longueurs de cheminement et
sa hauteur. Nous allons voir dans ce chapitre que la longueur de cheminement est
asymptotiquement d’ordre 2n log n, et que la hauteur est asymptotiquement d’ordre
c log n pour une constante c = 4,31107 . . . ; nous aurons également une idée de la
forme de l’arbre avec l’étude de son profil.
Les analyses qui suivent mettent en évidence deux points de vue possibles sur
les arbres binaires de recherche. D’une part, le point de vue combinatoire, avec
utilisation de séries génératrices, fournit des résultats en moyenne et en distribution
sur les paramètres analysés. D’autre part, ces paramètres vus comme variables
aléatoires se prêtent à une analyse probabiliste, par utilisation de martingales, qui
fournit des résultats asymptotiques presque sûrs.
Ces deux approches sont présentées de façon complémentaire, en les utilisant
conjointement le plus souvent possible. Par conséquent, les deux premières sections
de ce chapitre reposent sur le type de paramètre étudié (longueur de cheminement,
profil, profondeur d’insertion d’une clé, hauteur, niveau de saturation), en distinguant les paramètres additifs (en section 6.1) ou non (section 6.2). La section 6.3
donne quelques résultats pour les arbres récursifs (notamment leur hauteur),
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_6
217
Arbres binaires de recherche
Les arbres binaires de recherche (en abrégé abr) ont été introduits dans la section 1.2.5, et l’aléa sur ces arbres dans la section 2.2.3. Le mot aléatoire est
sous-entendu dans la suite, mais ils le sont bien, et l’aléa sur les abr est la loi
Ord dans les sections 6.1 à 6.4. Nous rappelons (cf. la définition 2.9) que cette loi
Ord est la loi sur les arbres binaires de recherche sous le modèle des permutations
uniformes, lorsque les clés insérées sont des variables aléatoires i.i.d. de même loi
uniforme sur l’intervalle [0, 1], et que l’arbre est construit par insertions successives
aux feuilles (figure 6.1).
Nous avons vu dans la section 3.2.1 que les performances des opérations de
recherche, avec et sans succès, et d’insertion dans un arbre binaire de recherche sont
déterminées par des paramètres de l’arbre tels que ses longueurs de cheminement et
sa hauteur. Nous allons voir dans ce chapitre que la longueur de cheminement est
asymptotiquement d’ordre 2n log n, et que la hauteur est asymptotiquement d’ordre
c log n pour une constante c = 4,31107 . . . ; nous aurons également une idée de la
forme de l’arbre avec l’étude de son profil.
Les analyses qui suivent mettent en évidence deux points de vue possibles sur
les arbres binaires de recherche. D’une part, le point de vue combinatoire, avec
utilisation de séries génératrices, fournit des résultats en moyenne et en distribution
sur les paramètres analysés. D’autre part, ces paramètres vus comme variables
aléatoires se prêtent à une analyse probabiliste, par utilisation de martingales, qui
fournit des résultats asymptotiques presque sûrs.
Ces deux approches sont présentées de façon complémentaire, en les utilisant
conjointement le plus souvent possible. Par conséquent, les deux premières sections
de ce chapitre reposent sur le type de paramètre étudié (longueur de cheminement,
profil, profondeur d’insertion d’une clé, hauteur, niveau de saturation), en distinguant les paramètres additifs (en section 6.1) ou non (section 6.2). La section 6.3
donne quelques résultats pour les arbres récursifs (notamment leur hauteur),
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_6
217