270
6 Arbres binaires de recherche
Fig. 6.16 Un arbre binaire
de recherche ; la plus grande
clé de l’arbre est 25, et la
feuille la plus à droite
contient la clé 13
évidemment, il existe des arbres binaires de recherche « filiformes » de hauteur n
pour un arbre de taille n, et donc pour ces arbres le coût maximal d’une opération
sera n. Considérons cependant la moyenne, sur tous les arbres de taille n pris sous
la loi Ord, du coût maximal d’une opération, i.e., la hauteur moyenne d’un arbre :
celle-ci est d’ordre logarithmique. Par ailleurs, la probabilité de s’éloigner de la
hauteur moyenne est exponentiellement faible (cf. la remarque 6.25).
Suppression Le modèle des arbres binaires de recherche sous la loi Ord n’est
plus conservé par une suppression ; nous donnons cependant ci-après quelques
indications sur le coût d’une suppression de clé dans un arbre qui suit initialement
cette loi (nous renvoyons à l’annexe A.2.3 pour la présentation de l’algorithme
« classique » de suppression dans un arbre binaire de recherche). Cette suppression
se fait en deux temps : d’abord la recherche de la clé à supprimer dans l’arbre, c’est
une recherche avec succès dont nous venons de voir le coût ; ensuite la suppression
proprement dite de la clé, qui est alors à la racine d’un sous-arbre. Cette deuxième
étape se fait en nombre d’opérations borné (et faible) si cette racine n’est pas un
nœud double ; sinon il s’agit de trouver la plus grande clé du sous-arbre gauche
puis de l’amener à la racine, et le nombre d’opérations pour cela est donné par la
longueur de la branche droite de ce sous-arbre – ici, nous entendons par « branche
droite » la branche conduisant au nœud le plus à droite et qui contient donc la plus
grande clé de l’arbre ; ce n’est pas toujours celle conduisant à la feuille la plus à
droite, comme cela peut être constaté sur l’arbre de la figure 6.16.
6.6.2 Arbres équilibrés
D’un point de vue algorithmique, il est souvent essentiel de certifier que les
arbres binaires de recherche gardent de « bonnes » performances. Cela se fait en
s’assurant qu’ils restent relativement équilibrés, ou en d’autres termes que leur
hauteur est d’ordre logarithmique en leur taille, y compris lorsque les clés ne sont
pas tirées selon le modèle des permutations uniformes ou lorsque les mises à jour
de l’arbre incluent des suppressions. Or en pratique les clés ne sont pas toujours
indépendantes ; l’insertion de clés triées, par exemple, conduit à un arbre filiforme,
et donc à une hauteur égale à n − 1 : la profondeur moyenne d’un nœud dans un
tel arbre (tous les nœuds étant supposés équiprobables) est de
n−1
2 , et les opérations
6 Arbres binaires de recherche
Fig. 6.16 Un arbre binaire
de recherche ; la plus grande
clé de l’arbre est 25, et la
feuille la plus à droite
contient la clé 13
évidemment, il existe des arbres binaires de recherche « filiformes » de hauteur n
pour un arbre de taille n, et donc pour ces arbres le coût maximal d’une opération
sera n. Considérons cependant la moyenne, sur tous les arbres de taille n pris sous
la loi Ord, du coût maximal d’une opération, i.e., la hauteur moyenne d’un arbre :
celle-ci est d’ordre logarithmique. Par ailleurs, la probabilité de s’éloigner de la
hauteur moyenne est exponentiellement faible (cf. la remarque 6.25).
Suppression Le modèle des arbres binaires de recherche sous la loi Ord n’est
plus conservé par une suppression ; nous donnons cependant ci-après quelques
indications sur le coût d’une suppression de clé dans un arbre qui suit initialement
cette loi (nous renvoyons à l’annexe A.2.3 pour la présentation de l’algorithme
« classique » de suppression dans un arbre binaire de recherche). Cette suppression
se fait en deux temps : d’abord la recherche de la clé à supprimer dans l’arbre, c’est
une recherche avec succès dont nous venons de voir le coût ; ensuite la suppression
proprement dite de la clé, qui est alors à la racine d’un sous-arbre. Cette deuxième
étape se fait en nombre d’opérations borné (et faible) si cette racine n’est pas un
nœud double ; sinon il s’agit de trouver la plus grande clé du sous-arbre gauche
puis de l’amener à la racine, et le nombre d’opérations pour cela est donné par la
longueur de la branche droite de ce sous-arbre – ici, nous entendons par « branche
droite » la branche conduisant au nœud le plus à droite et qui contient donc la plus
grande clé de l’arbre ; ce n’est pas toujours celle conduisant à la feuille la plus à
droite, comme cela peut être constaté sur l’arbre de la figure 6.16.
6.6.2 Arbres équilibrés
D’un point de vue algorithmique, il est souvent essentiel de certifier que les
arbres binaires de recherche gardent de « bonnes » performances. Cela se fait en
s’assurant qu’ils restent relativement équilibrés, ou en d’autres termes que leur
hauteur est d’ordre logarithmique en leur taille, y compris lorsque les clés ne sont
pas tirées selon le modèle des permutations uniformes ou lorsque les mises à jour
de l’arbre incluent des suppressions. Or en pratique les clés ne sont pas toujours
indépendantes ; l’insertion de clés triées, par exemple, conduit à un arbre filiforme,
et donc à une hauteur égale à n − 1 : la profondeur moyenne d’un nœud dans un
tel arbre (tous les nœuds étant supposés équiprobables) est de
n−1
2 , et les opérations