3.4 Modélisations par des structures arborescentes
101
Nous avons, pour chaque classe d’objets combinatoires susceptibles d’être
engendrés par la méthode ECO, un arbre de génération (unique !) qui résume les
choix possibles à chaque niveau ; de plus nous trouvons au niveau n de l’arbre
les objets de taille n, et les propriétés structurelles du système de réécriture fourni
par la méthode ECO se reflètent dans celles de l’arbre. Plus précisément, si f n est
le nombre de nœuds au niveau n, la fonction génératrice F (z) =
n≥0 f n z n est
celle du profil de l’arbre, et ses propriétés algébriques permettent de déterminer, par
exemple, l’ordre de grandeur de f n , et donc de se faire une idée de l’efficacité d’un
algorithme utilisant cette méthode de génération aléatoire uniforme. Pour plus de
détails, nous renvoyons à l’article [14].
3.4.3 Arbres Union-Find
Gestion d’ensembles Un certain nombre de situations (gestion de classes
d’équivalence, recherche de composantes connexes ou de forêt couvrante minimale
d’un graphe, etc.) conduisent à gérer des ensembles disjoints, sur lesquels les
opérations de base sont la recherche de l’ensemble auquel appartient un élément
donné, et l’union de deux ensembles. Une référence générale, bien qu’un peu
ancienne, pour la gestion de classes d’équivalence est l’article de synthèse de Galil
et Italiano [114] ; les algorithmes que nous allons présenter ci-dessous sont traités
en détail dans le chapitre 21 du livre de Cormen et al. [51].
La situation générale est la suivante :
– Il y a n éléments, que nous supposons numérotés de 1 à n.
– Dans chaque ensemble, un des éléments est désigné comme son identifiant, ou
représentant.
– L’opération « Trouver » (« Find » en anglais) associe à chaque élément
l’identifiant de l’ensemble auquel il appartient, nous parlerons aussi de sa
« classe ». 22 Chercher à quel ensemble appartient un élément revient à trouver
l’identifiant de cet ensemble.
– L’opération « Union » fusionne deux ensembles.
Nous présentons maintenant différentes manières de réaliser ceci. Notons C j
l’ensemble ayant pour identifiant j ; nous allons organiser les éléments d’un
ensemble en arbre, et identifier un ensemble et l’arbre le représentant. L’identifiant
de cet ensemble sera la marque de la racine de l’arbre. Pour les complexités qui
suivent, nous supposons que, pour tout sommet d’un arbre, il est possible d’accéder
en temps constant à son parent. 23
22 Ce terme vient de la vision « classes d’équivalence », la relation d’équivalence étant « appartenir
au même ensemble ».
23 Cela se fait, par exemple, en gardant dans un tableau ces parents.
101
Nous avons, pour chaque classe d’objets combinatoires susceptibles d’être
engendrés par la méthode ECO, un arbre de génération (unique !) qui résume les
choix possibles à chaque niveau ; de plus nous trouvons au niveau n de l’arbre
les objets de taille n, et les propriétés structurelles du système de réécriture fourni
par la méthode ECO se reflètent dans celles de l’arbre. Plus précisément, si f n est
le nombre de nœuds au niveau n, la fonction génératrice F (z) =
n≥0 f n z n est
celle du profil de l’arbre, et ses propriétés algébriques permettent de déterminer, par
exemple, l’ordre de grandeur de f n , et donc de se faire une idée de l’efficacité d’un
algorithme utilisant cette méthode de génération aléatoire uniforme. Pour plus de
détails, nous renvoyons à l’article [14].
3.4.3 Arbres Union-Find
Gestion d’ensembles Un certain nombre de situations (gestion de classes
d’équivalence, recherche de composantes connexes ou de forêt couvrante minimale
d’un graphe, etc.) conduisent à gérer des ensembles disjoints, sur lesquels les
opérations de base sont la recherche de l’ensemble auquel appartient un élément
donné, et l’union de deux ensembles. Une référence générale, bien qu’un peu
ancienne, pour la gestion de classes d’équivalence est l’article de synthèse de Galil
et Italiano [114] ; les algorithmes que nous allons présenter ci-dessous sont traités
en détail dans le chapitre 21 du livre de Cormen et al. [51].
La situation générale est la suivante :
– Il y a n éléments, que nous supposons numérotés de 1 à n.
– Dans chaque ensemble, un des éléments est désigné comme son identifiant, ou
représentant.
– L’opération « Trouver » (« Find » en anglais) associe à chaque élément
l’identifiant de l’ensemble auquel il appartient, nous parlerons aussi de sa
« classe ». 22 Chercher à quel ensemble appartient un élément revient à trouver
l’identifiant de cet ensemble.
– L’opération « Union » fusionne deux ensembles.
Nous présentons maintenant différentes manières de réaliser ceci. Notons C j
l’ensemble ayant pour identifiant j ; nous allons organiser les éléments d’un
ensemble en arbre, et identifier un ensemble et l’arbre le représentant. L’identifiant
de cet ensemble sera la marque de la racine de l’arbre. Pour les complexités qui
suivent, nous supposons que, pour tout sommet d’un arbre, il est possible d’accéder
en temps constant à son parent. 23
22 Ce terme vient de la vision « classes d’équivalence », la relation d’équivalence étant « appartenir
au même ensemble ».
23 Cela se fait, par exemple, en gardant dans un tableau ces parents.