6.6 Coût des opérations algorithmiques
271
d’insertion ou de recherche sont alors de coût moyen linéaire. D’autre part, si le
modèle des permutations uniformes est bien adapté à modéliser les arbres binaires
de recherche évoluant par insertions successives aux feuilles, il ne l’est plus dès que
les suppressions sont autorisées : les arbres ne suivent plus la loi Ord, et peuvent
là encore devenir de hauteur plus que logarithmique en leur taille, ce qui conduit
à de mauvaises performances algorithmiques. Pour un exemple d’arbres binaires
de recherche qui ne suivent plus la loi Ord, nous renvoyons à Panny [202] ou à
l’exercice 6.7 qui en est tiré.
Différentes variantes des arbres binaires de recherche « classiques » ont été
proposées, par exemple les arbres AVL ou les arbres 2–3–4 et leur implémentation
par les arbres bicolores ; tous sont des arbres dont la hauteur est toujours d’ordre
logarithmique.
Les arbres AVL d’Adel’son-Vel’skii et Landis [1] sont des arbres binaires de
recherche tels que, en chaque nœud, la hauteur des deux sous-arbres droit et gauche
diffère au plus de 1. Cette condition d’équilibre impose de garder en chaque
nœud une information sur la différence des hauteurs des sous-arbres gauche et
droit, différence qui appartient à {−1, 0, +1} ; le rééquilibrage de l’arbre lors des
opérations de mise à jour se fait par des rotations de sous-arbres, qui sont données
dans l’annexe A.1.4.
Les arbres 2–3–4 ne sont autres que des arbres-B prudents de paramètre m = 2,
cf. la remarque 3.3. Les arbres bicolores en sont une implémentation par des arbres
binaires, où chaque nœud est colorié par une couleur (classiquement, rouge et noir)
suivant des règles qui assurent que la hauteur totale de l’arbre est égale au plus à
deux fois son niveau de saturation.
Pour les arbres AVL comme pour les arbres bicolores, la structure sous-jacente
est toujours un arbre binaire, tout au plus augmentée pour garder une information
supplémentaire par nœud : la différence des hauteurs pour les arbres AVL, et
la couleur pour les arbres bicolores. Nous renvoyons par exemple au livre de
Sedgewick [231] pour une présentation détaillée de ces arbres et des algorithmes
qui permettent de les manipuler.
6.6.3 Arbres binaires de recherche randomisés
L’approche la plus simple à implémenter en pratique pour éviter les mauvaises
performances algorithmiques des arbres binaires de recherche dans le cas où les clés
sont corrélées, ou bien dans le cas de suppressions, est sans doute la randomisation
dans sa version donnée par Martinez et Roura [179] : elle permet de construire des
arbres binaires de recherche qui suivent la loi Ord quelles que soient les corrélations
des clés et les opérations autorisées.
Nous avons vu dans la section 6.5 qu’un arbre binaire de recherche randomisé est
de même loi qu’un arbre sous la loi Ord ; c’est le théorème 6.37. En conséquence,
le coût de recherche (avec ou sans succès) d’une clé dans un arbre de recherche
randomisé est le même que pour un arbre binaire de recherche sous la loi Ord.
271
d’insertion ou de recherche sont alors de coût moyen linéaire. D’autre part, si le
modèle des permutations uniformes est bien adapté à modéliser les arbres binaires
de recherche évoluant par insertions successives aux feuilles, il ne l’est plus dès que
les suppressions sont autorisées : les arbres ne suivent plus la loi Ord, et peuvent
là encore devenir de hauteur plus que logarithmique en leur taille, ce qui conduit
à de mauvaises performances algorithmiques. Pour un exemple d’arbres binaires
de recherche qui ne suivent plus la loi Ord, nous renvoyons à Panny [202] ou à
l’exercice 6.7 qui en est tiré.
Différentes variantes des arbres binaires de recherche « classiques » ont été
proposées, par exemple les arbres AVL ou les arbres 2–3–4 et leur implémentation
par les arbres bicolores ; tous sont des arbres dont la hauteur est toujours d’ordre
logarithmique.
Les arbres AVL d’Adel’son-Vel’skii et Landis [1] sont des arbres binaires de
recherche tels que, en chaque nœud, la hauteur des deux sous-arbres droit et gauche
diffère au plus de 1. Cette condition d’équilibre impose de garder en chaque
nœud une information sur la différence des hauteurs des sous-arbres gauche et
droit, différence qui appartient à {−1, 0, +1} ; le rééquilibrage de l’arbre lors des
opérations de mise à jour se fait par des rotations de sous-arbres, qui sont données
dans l’annexe A.1.4.
Les arbres 2–3–4 ne sont autres que des arbres-B prudents de paramètre m = 2,
cf. la remarque 3.3. Les arbres bicolores en sont une implémentation par des arbres
binaires, où chaque nœud est colorié par une couleur (classiquement, rouge et noir)
suivant des règles qui assurent que la hauteur totale de l’arbre est égale au plus à
deux fois son niveau de saturation.
Pour les arbres AVL comme pour les arbres bicolores, la structure sous-jacente
est toujours un arbre binaire, tout au plus augmentée pour garder une information
supplémentaire par nœud : la différence des hauteurs pour les arbres AVL, et
la couleur pour les arbres bicolores. Nous renvoyons par exemple au livre de
Sedgewick [231] pour une présentation détaillée de ces arbres et des algorithmes
qui permettent de les manipuler.
6.6.3 Arbres binaires de recherche randomisés
L’approche la plus simple à implémenter en pratique pour éviter les mauvaises
performances algorithmiques des arbres binaires de recherche dans le cas où les clés
sont corrélées, ou bien dans le cas de suppressions, est sans doute la randomisation
dans sa version donnée par Martinez et Roura [179] : elle permet de construire des
arbres binaires de recherche qui suivent la loi Ord quelles que soient les corrélations
des clés et les opérations autorisées.
Nous avons vu dans la section 6.5 qu’un arbre binaire de recherche randomisé est
de même loi qu’un arbre sous la loi Ord ; c’est le théorème 6.37. En conséquence,
le coût de recherche (avec ou sans succès) d’une clé dans un arbre de recherche
randomisé est le même que pour un arbre binaire de recherche sous la loi Ord.