218
6 Arbres binaires de recherche
Fig. 6.1 En haut, un arbre binaire de recherche de taille 200 tiré aléatoirement selon la distribution
« des permutations uniformes » ou loi Ord. En bas le même arbre a été complété : il possède donc
200 nœuds internes et 201 noœud externes
ceux-ci étant étroitement liés aux arbres binaires de recherche. Nous présentons
ensuite en section 6.4 une extension du processus de croissance des arbres bourgeonnants qui consiste à biaiser les formes d’arbres binaires de recherche sous la
loi Ord (cf. la remarque 2.11). La section 6.5, qui traite des arbres binaires de
recherche randomisés, montre comment une variante algorithmique simple permet,
quelle que soit la corrélation sur les données insérées dans l’arbre et quelle que
soit la suite de mises à jour (insertions ou suppressions), d’assurer que les arbres
binaires de recherche obtenus suivent la même loi que ceux construits sur le modèle
des permutations uniformes. La traduction des résultats des sections précédentes, en
termes de coûts des algorithmes sur les arbres binaires de recherche, est effectuée
dans la section 6.6. Enfin, la section 6.7 reprend le lien entre le tri rapide et les
arbres binaires de recherche déjà présenté en section 3.3.1, pour fournir des éléments
d’analyse du coût de ce tri.
Quelques rappels
Tel qu’il a été introduit dans la section 1.2.5, un abr τ n de taille n possède n
clés ou marques dans ses noeuds, et a n + 1 possibilités d’insertion, qui sont les
feuilles de l’arbre complété. Nous avons vu par ailleurs dans la section 2.2.3 que
le processus abr (τ n ) n≥0 (c’est-à-dire la suite des arbres τ n ) a été défini de la façon
suivante : l’arbre de départ τ 0 ne contient pas de clé, il est réduit à une feuille ; pour
n ≥ 0, τ n+1 est obtenu à partir de τ n par insertion aux feuilles de la (n + 1)-ième clé
uniformément sur l’une des n + 1 possibilités d’insertion de τ n . La figure 6.2 donne
un exemple d’insertion dans un abr de taille 7.
Pour simplifier la rédaction et lorsque le contexte ne prête pas à ambiguïté,
nous parlons souvent dans les sections 6.1 à 6.4 simplement d’« arbre binaire de
recherche » pour désigner l’arbre complété.
6 Arbres binaires de recherche
Fig. 6.1 En haut, un arbre binaire de recherche de taille 200 tiré aléatoirement selon la distribution
« des permutations uniformes » ou loi Ord. En bas le même arbre a été complété : il possède donc
200 nœuds internes et 201 noœud externes
ceux-ci étant étroitement liés aux arbres binaires de recherche. Nous présentons
ensuite en section 6.4 une extension du processus de croissance des arbres bourgeonnants qui consiste à biaiser les formes d’arbres binaires de recherche sous la
loi Ord (cf. la remarque 2.11). La section 6.5, qui traite des arbres binaires de
recherche randomisés, montre comment une variante algorithmique simple permet,
quelle que soit la corrélation sur les données insérées dans l’arbre et quelle que
soit la suite de mises à jour (insertions ou suppressions), d’assurer que les arbres
binaires de recherche obtenus suivent la même loi que ceux construits sur le modèle
des permutations uniformes. La traduction des résultats des sections précédentes, en
termes de coûts des algorithmes sur les arbres binaires de recherche, est effectuée
dans la section 6.6. Enfin, la section 6.7 reprend le lien entre le tri rapide et les
arbres binaires de recherche déjà présenté en section 3.3.1, pour fournir des éléments
d’analyse du coût de ce tri.
Quelques rappels
Tel qu’il a été introduit dans la section 1.2.5, un abr τ n de taille n possède n
clés ou marques dans ses noeuds, et a n + 1 possibilités d’insertion, qui sont les
feuilles de l’arbre complété. Nous avons vu par ailleurs dans la section 2.2.3 que
le processus abr (τ n ) n≥0 (c’est-à-dire la suite des arbres τ n ) a été défini de la façon
suivante : l’arbre de départ τ 0 ne contient pas de clé, il est réduit à une feuille ; pour
n ≥ 0, τ n+1 est obtenu à partir de τ n par insertion aux feuilles de la (n + 1)-ième clé
uniformément sur l’une des n + 1 possibilités d’insertion de τ n . La figure 6.2 donne
un exemple d’insertion dans un abr de taille 7.
Pour simplifier la rédaction et lorsque le contexte ne prête pas à ambiguïté,
nous parlons souvent dans les sections 6.1 à 6.4 simplement d’« arbre binaire de
recherche » pour désigner l’arbre complété.