3.4 Modélisations par des structures arborescentes
103
Fig. 3.29 Avec les mêmes ensembles de départ que dans la figure 3.28 et la même suite
d’opérations : union de C 2 avec C 4 , puis de C 1 avec le résultat, mais maintenant avec
l’algorithme (b). L’arbre final est de hauteur 3, et la profondeur moyenne d’un nœud est
21
10
Fig. 3.30 Avec les mêmes ensembles de départ et la même suite d’opérations que dans les figures
précédentes, les arbres obtenus par l’application de l’algorithme (c). L’arbre final est maintenant
de hauteur 2 et de largeur 6, et la profondeur moyenne d’un nœud est
12
10
pour chaque arbre, sa taille ; la mise à jour de cette taille lors d’une union peut
se faire en temps constant. Cette opération d’union est maintenant symétrique :
les arbres obtenus par Union(C i , C j ) et par Union(C j , C i ) sont identiques.
Un exemple est donné en figure 3.30. La complexité d’une opération d’union
(une fois trouvées les racines des arbres) reste en temps constant, et celle de
la recherche est toujours bornée par la hauteur de l’arbre ; mais maintenant un
argument simple montre que la hauteur de l’arbre est bornée par log 2 n (voir par
exemple [111, p. 432]).
(d) L’amélioration finale vient de la compression des chemins : il s’agit, lors de la
recherche de la classe d’un élément j , de rattacher les éléments rencontrés sur le
chemin de j à la racine, y compris bien sûr j lui-même, directement à la racine
de l’arbre. L’union se fait de la même manière que pour l’algorithme (c). Cf. la
figure 3.31 pour un exemple. L’union de deux classes comme la recherche de la