104
3 Arbres, algorithmes et données
Fig. 3.31 L’arbre obtenu en appliquant au dernier arbre de la figure 3.30 la compression de
chemin lors de la recherche de l’élément 5. Il est toujours de hauteur 2, mais la largeur et la
profondeur moyenne d’un nœud sont maintenant respectivement 7 et
11
10
classe d’un élément ont toujours une complexité au pire bornée par la hauteur
de l’arbre, mais maintenant cette hauteur est très petite. Plus précisément,
dans le cas où les seules opérations effectuées sont des unions de classes, la
hauteur d’un arbre est logarithmique en sa taille, mais cette hauteur peut être
sensiblement réduite par les opérations de recherche. Tarjan a ainsi montré
(cf. [241], démonstration ensuite simplifiée par Seidel et Sharir [234]) que, lors
d’une suite d’opérations comprenant n − 1 unions et m ≥ n recherches, le
coût moyen d’une opération est borné par une fonction α(n) 24 à croissance très
lente : α(n) ≤ 4 pour n < 10 80 , et nous pouvons la considérer comme bornée
par 4 pour toute application réelle. En pratique, c’est donc ce dernier algorithme
qui est utilisé.
Lien avec les arbres binaires de recherche Dans ce qui suit, nous désignons par
« arbre Union-Find » un arbre obtenu par une suite d’opérations « Union » suivant
l’algorithme (b). Les arbres obtenus par cet algorithme d’union sont étroitement liés
aux arbres binaires de recherche ; nous explorons maintenant ce lien.
Appliquons l’algorithme « Union » à une forêt initiale de n arbres T 1 , . . . , T n
réduits à leur racine étiquetée par 1, 2, . . . , n. La construction d’un arbre UnionFind de taille n génère un arbre binaire associé de la façon suivante (voir la
figure 3.32) : à chaque fois qu’est appelée Union(C i , C j ), alors
– d’une part à droite de la figure, l’arbre de racine j devient enfant de la racine i ;
c’est bien l’opération (b).
– d’autre part à gauche de la figure, l’arbre T j devient sous-arbre gauche de i et
l’arbre T i devient sous-arbre droit de i.
Il est alors clair par construction que le niveau d’un nœud i dans l’arbre final
Union-Find est exactement son niveau à gauche, i.e., le nombre de branches gauches
entre la racine et le nœud, dans l’arbre binaire associé.
En outre, l’arbre binaire associé pousse comme un abr (ce n’est pas un abr) : pour
le voir il suffit de montrer que la forme d’arbre Union-Find construit avec n objets
pousse uniformément, au sens où
24 Cette fonction est en fait l’inverse d’une variante de la fonction d’Ackermann, bien connue en
théorie de la récursivité.
3 Arbres, algorithmes et données
Fig. 3.31 L’arbre obtenu en appliquant au dernier arbre de la figure 3.30 la compression de
chemin lors de la recherche de l’élément 5. Il est toujours de hauteur 2, mais la largeur et la
profondeur moyenne d’un nœud sont maintenant respectivement 7 et
11
10
classe d’un élément ont toujours une complexité au pire bornée par la hauteur
de l’arbre, mais maintenant cette hauteur est très petite. Plus précisément,
dans le cas où les seules opérations effectuées sont des unions de classes, la
hauteur d’un arbre est logarithmique en sa taille, mais cette hauteur peut être
sensiblement réduite par les opérations de recherche. Tarjan a ainsi montré
(cf. [241], démonstration ensuite simplifiée par Seidel et Sharir [234]) que, lors
d’une suite d’opérations comprenant n − 1 unions et m ≥ n recherches, le
coût moyen d’une opération est borné par une fonction α(n) 24 à croissance très
lente : α(n) ≤ 4 pour n < 10 80 , et nous pouvons la considérer comme bornée
par 4 pour toute application réelle. En pratique, c’est donc ce dernier algorithme
qui est utilisé.
Lien avec les arbres binaires de recherche Dans ce qui suit, nous désignons par
« arbre Union-Find » un arbre obtenu par une suite d’opérations « Union » suivant
l’algorithme (b). Les arbres obtenus par cet algorithme d’union sont étroitement liés
aux arbres binaires de recherche ; nous explorons maintenant ce lien.
Appliquons l’algorithme « Union » à une forêt initiale de n arbres T 1 , . . . , T n
réduits à leur racine étiquetée par 1, 2, . . . , n. La construction d’un arbre UnionFind de taille n génère un arbre binaire associé de la façon suivante (voir la
figure 3.32) : à chaque fois qu’est appelée Union(C i , C j ), alors
– d’une part à droite de la figure, l’arbre de racine j devient enfant de la racine i ;
c’est bien l’opération (b).
– d’autre part à gauche de la figure, l’arbre T j devient sous-arbre gauche de i et
l’arbre T i devient sous-arbre droit de i.
Il est alors clair par construction que le niveau d’un nœud i dans l’arbre final
Union-Find est exactement son niveau à gauche, i.e., le nombre de branches gauches
entre la racine et le nœud, dans l’arbre binaire associé.
En outre, l’arbre binaire associé pousse comme un abr (ce n’est pas un abr) : pour
le voir il suffit de montrer que la forme d’arbre Union-Find construit avec n objets
pousse uniformément, au sens où
24 Cette fonction est en fait l’inverse d’une variante de la fonction d’Ackermann, bien connue en
théorie de la récursivité.