102
3 Arbres, algorithmes et données
Attention, si l’union ensembliste de deux classes C i et C j est une opération
symétrique, ce ne sera pas toujours le cas des opérations algorithmiques d’union :
pour les algorithmes (a) et (b) ci-dessous, Union(C i , C j ) et Union(C j , C i ) sont
deux arbres distincts (mais de même taille et sur le même ensemble de marques
pour les sommets). Pour marquer cette différence, nous parlerons de l’union de C i
avec C j .
(a) Dans la version la plus simple, tous les sommets d’une classe sont rattachés à
sa racine. Les arbres sont alors de hauteur 0 ou 1, puisque chaque nœud est soit
identifiant et racine de sa classe d’équivalence, soit enfant de l’identifiant ; par
contre leur largeur est égale à leur cardinalité moins 1. Pour trouver la classe
d’un élément, il suffit de remonter à la racine, ce qui se fait en une opération.
L’union de la classe C i avec la classe C j se fait en rattachant tous les éléments
de la classe C j à la racine de C i . Elle nécessite un temps d’ordre égal à la largeur
de l’arbre associé à C j , donc (à 1 près) à la taille de C j , et a une complexité
linéaire dans le cas le pire. Cet algorithme est illustré dans la figure 3.28.
(b) Pour tenter d’améliorer la complexité de l’union de deux ensembles, une
première possibilité est de rattacher à la racine de la première classe C i , non
pas tous les éléments de la classe C j , mais uniquement sa racine. La complexité
de la recherche de la classe d’un élément augmente alors : il faut remonter
à la racine de l’arbre pour connaître l’identifiant d’un élément. Dans le cas
le pire, elle est égale à la hauteur de l’arbre, soit jusqu’à n dans le cas où
l’arbre est filiforme. La fusion de deux classes se fait en temps constant, une
fois trouvées les racines des deux arbres. Les deux opérations sont donc de
complexité linéaire dans le cas le pire. Cf. la figure 3.29 pour une illustration.
(c) Une nouvelle amélioration consiste, dans l’algorithme (b), à rattacher systématiquement le plus petit arbre à la racine du plus grand. Cela impose de garder,
Fig. 3.28 En haut, trois ensembles {4, 3, 7, 8, 9}, {2, 10} et {1, 5, 6}, représentés sous forme
d’arbres. Par convention, l’identifiant de chaque ensemble est la marque de la racine, et les enfants
d’un sommet sont ordonnés par ordre de marque croissante. Au milieu, les arbres après union de C 2
avec C 4 par l’algorithme (a). En bas, l’arbre final après union de C 1 avec l’ensemble précédemment
obtenu ; cet arbre est de hauteur 1 et de largeur 9, et la profondeur moyenne d’un nœud est
9
10
3 Arbres, algorithmes et données
Attention, si l’union ensembliste de deux classes C i et C j est une opération
symétrique, ce ne sera pas toujours le cas des opérations algorithmiques d’union :
pour les algorithmes (a) et (b) ci-dessous, Union(C i , C j ) et Union(C j , C i ) sont
deux arbres distincts (mais de même taille et sur le même ensemble de marques
pour les sommets). Pour marquer cette différence, nous parlerons de l’union de C i
avec C j .
(a) Dans la version la plus simple, tous les sommets d’une classe sont rattachés à
sa racine. Les arbres sont alors de hauteur 0 ou 1, puisque chaque nœud est soit
identifiant et racine de sa classe d’équivalence, soit enfant de l’identifiant ; par
contre leur largeur est égale à leur cardinalité moins 1. Pour trouver la classe
d’un élément, il suffit de remonter à la racine, ce qui se fait en une opération.
L’union de la classe C i avec la classe C j se fait en rattachant tous les éléments
de la classe C j à la racine de C i . Elle nécessite un temps d’ordre égal à la largeur
de l’arbre associé à C j , donc (à 1 près) à la taille de C j , et a une complexité
linéaire dans le cas le pire. Cet algorithme est illustré dans la figure 3.28.
(b) Pour tenter d’améliorer la complexité de l’union de deux ensembles, une
première possibilité est de rattacher à la racine de la première classe C i , non
pas tous les éléments de la classe C j , mais uniquement sa racine. La complexité
de la recherche de la classe d’un élément augmente alors : il faut remonter
à la racine de l’arbre pour connaître l’identifiant d’un élément. Dans le cas
le pire, elle est égale à la hauteur de l’arbre, soit jusqu’à n dans le cas où
l’arbre est filiforme. La fusion de deux classes se fait en temps constant, une
fois trouvées les racines des deux arbres. Les deux opérations sont donc de
complexité linéaire dans le cas le pire. Cf. la figure 3.29 pour une illustration.
(c) Une nouvelle amélioration consiste, dans l’algorithme (b), à rattacher systématiquement le plus petit arbre à la racine du plus grand. Cela impose de garder,
Fig. 3.28 En haut, trois ensembles {4, 3, 7, 8, 9}, {2, 10} et {1, 5, 6}, représentés sous forme
d’arbres. Par convention, l’identifiant de chaque ensemble est la marque de la racine, et les enfants
d’un sommet sont ordonnés par ordre de marque croissante. Au milieu, les arbres après union de C 2
avec C 4 par l’algorithme (a). En bas, l’arbre final après union de C 1 avec l’ensemble précédemment
obtenu ; cet arbre est de hauteur 1 et de largeur 9, et la profondeur moyenne d’un nœud est
9
10