272
6 Arbres binaires de recherche
Contrairement aux arbres AVL et aux arbres bicolores, les arbres binaires de
recherche randomisés n’offrent pas la garantie que le maximum de la hauteur soit
d’ordre logarithmique : cette hauteur peut atteindre une valeur proportionnelle au
nombre de clés. La randomisation assure cependant que l’arbre suit la loi Ord, et les
arbres filiformes n’ont qu’une probabilité exponentiellement faible de se produire,
ce qui est généralement suffisant en pratique.
Regardons donc le coût d’une mise à jour : insertion faisant appel à la coupure,
ou suppression faisant appel à la fusion. En détaillant l’exécution de l’algorithme
de coupure d’un arbre τ suivant une clé X (cf. l’annexe A.2.4), nous voyons que
cet algorithme suit exactement le chemin conduisant à la feuille f où l’algorithme
d’insertion aux feuilles insérerait X. Le nombre de nœuds visités, qui mesure la
complexité de la coupure, est donc égal à la profondeur de f ; sa valeur maximale
est la hauteur de l’arbre, et sa valeur moyenne est la profondeur moyenne d’une
feuille de τ .
La fusion de deux arbres indépendants τ 1 et τ 2 , quant à elle, suit dans chacun des
deux arbres un chemin allant de la racine vers une feuille, disons f 1 pour τ 1 et f 2
pour τ 2 ; son coût est donc au plus égal à la somme des profondeurs de f 1 et f 2 et
il est déterminé dans le cas le pire par la hauteur d’un arbre sous la loi Ord, et en
moyenne par la profondeur d’une feuille sous cette même loi.
Attention : le coût d’une mise à jour randomisée (insertion ou suppression)
dans un arbre binaire de recherche comprend maintenant deux parties : le coût des
comparaisons de clés faites pour modifier la structure de l’arbre, que nous venons de
regarder, et le coût du générateur aléatoire utilisé à chaque étape pour décider, dans
le cas de l’insertion, si elle se fait à la racine ou dans un sous-arbre, et quels sousarbres sont fusionnés dans le cas de la suppression. Cependant, le nombre d’appels
au générateur aléatoire est, comme le nombre de nœuds visités, étroitement lié à la
profondeur d’une feuille.
6.7 Un algorithme proche : le tri rapide
Nous avons vu dans la section 3.3.1 que, pour une version « idéalisée » du tri rapide,
le nombre de comparaisons entre clés pour trier un tableau de n clés suit la même loi
que le nombre de comparaisons pour créer un arbre binaire de recherche à partir de
la suite de ces n clés dans le même ordre. Nous présentons ci-dessous une analyse
pour le tri rapide, 12 qui fournit un encadrement du nombre moyen de comparaisons
faites par l’algorithme de tri, avant de donner quelques indications sur le nombre
d’échanges de clés.
12 En réalité, la procédure de partition du tri rapide, telle que le plus souvent implémentée, fait un
nombre de comparaisons légèrement différent : pour éviter de tester de manière répétitive que nous
ne sortons pas des bornes du (sous-)tableau en cours de partitionnement, nous acceptons de faire
quelques comparaisons supplémentaires de clés, avec la sentinelle.
6 Arbres binaires de recherche
Contrairement aux arbres AVL et aux arbres bicolores, les arbres binaires de
recherche randomisés n’offrent pas la garantie que le maximum de la hauteur soit
d’ordre logarithmique : cette hauteur peut atteindre une valeur proportionnelle au
nombre de clés. La randomisation assure cependant que l’arbre suit la loi Ord, et les
arbres filiformes n’ont qu’une probabilité exponentiellement faible de se produire,
ce qui est généralement suffisant en pratique.
Regardons donc le coût d’une mise à jour : insertion faisant appel à la coupure,
ou suppression faisant appel à la fusion. En détaillant l’exécution de l’algorithme
de coupure d’un arbre τ suivant une clé X (cf. l’annexe A.2.4), nous voyons que
cet algorithme suit exactement le chemin conduisant à la feuille f où l’algorithme
d’insertion aux feuilles insérerait X. Le nombre de nœuds visités, qui mesure la
complexité de la coupure, est donc égal à la profondeur de f ; sa valeur maximale
est la hauteur de l’arbre, et sa valeur moyenne est la profondeur moyenne d’une
feuille de τ .
La fusion de deux arbres indépendants τ 1 et τ 2 , quant à elle, suit dans chacun des
deux arbres un chemin allant de la racine vers une feuille, disons f 1 pour τ 1 et f 2
pour τ 2 ; son coût est donc au plus égal à la somme des profondeurs de f 1 et f 2 et
il est déterminé dans le cas le pire par la hauteur d’un arbre sous la loi Ord, et en
moyenne par la profondeur d’une feuille sous cette même loi.
Attention : le coût d’une mise à jour randomisée (insertion ou suppression)
dans un arbre binaire de recherche comprend maintenant deux parties : le coût des
comparaisons de clés faites pour modifier la structure de l’arbre, que nous venons de
regarder, et le coût du générateur aléatoire utilisé à chaque étape pour décider, dans
le cas de l’insertion, si elle se fait à la racine ou dans un sous-arbre, et quels sousarbres sont fusionnés dans le cas de la suppression. Cependant, le nombre d’appels
au générateur aléatoire est, comme le nombre de nœuds visités, étroitement lié à la
profondeur d’une feuille.
6.7 Un algorithme proche : le tri rapide
Nous avons vu dans la section 3.3.1 que, pour une version « idéalisée » du tri rapide,
le nombre de comparaisons entre clés pour trier un tableau de n clés suit la même loi
que le nombre de comparaisons pour créer un arbre binaire de recherche à partir de
la suite de ces n clés dans le même ordre. Nous présentons ci-dessous une analyse
pour le tri rapide, 12 qui fournit un encadrement du nombre moyen de comparaisons
faites par l’algorithme de tri, avant de donner quelques indications sur le nombre
d’échanges de clés.
12 En réalité, la procédure de partition du tri rapide, telle que le plus souvent implémentée, fait un
nombre de comparaisons légèrement différent : pour éviter de tester de manière répétitive que nous
ne sortons pas des bornes du (sous-)tableau en cours de partitionnement, nous acceptons de faire
quelques comparaisons supplémentaires de clés, avec la sentinelle.