3.4 Modélisations par des structures arborescentes
105
Fig. 3.32 Un exemple de construction simultanée à droite d’un arbre Union-Find à 5 nœuds et
à gauche de l’arbre binaire associé. La séquence d’appels est : Union(C 1 , C 2 ), Union(C 1 , C 3 ),
Union(C 4 , C 5 ) et Union(C 4 , C 1 )
Lemme 3.16 Une forme d’arbre Union-Find de taille n + 1 a même loi qu’une
forme d’arbre Union-Find de taille n, auquel on ajoute, sur l’un des n nœuds choisi
uniformément (avec probabilité 1/n), une feuille supplémentaire.
En effet, construisons un arbre Union-Find à partir de n + 1 objets. À la première
étape, on obtient un petit arbre à deux sommets (colorions les deux sommets de ce
petit arbre et considérons que c’est un gros sommet coloré) et n − 1 arbres réduits
à leur racine. C’est une forêt de n arbres, qui donne donc par l’algorithme UnionFind une forme d’arbre Union-Find de taille n. Or, une forme d’arbre Union-Find
de taille n a même loi qu’une forme d’arbre Union-Find de taille n dont un des
sommets est coloré. Et la loi de cette forme d’arbres Union-Find de taille n dont un
des sommets est coloré ne dépend pas du choix de l’objet que l’on colore. Ainsi est
justifiée la propriété du lemme 3.16 ci-dessus.
Grâce à la bijection plus haut (celle de la figure 3.32), cette uniformité sur
le processus d’arbres Union-Find se traduit par la pousse uniforme de l’arbre
binaire associé en chacune de ses feuilles justement étiquetées par 1, 2, . . . , n. Cet
arbre binaire associé pousse donc comme un abr, autrement dit comme un arbre
bourgeonnant. Ainsi, la hauteur d’un arbre Union-Find est la même que la hauteur
à gauche d’un abr.
Ces bijections et ces dynamiques sont connues depuis les travaux de Doyle et
Rivest [66], Knuth et Schönhage [158], Devroye [56, 57], Pittel [209].
105
Fig. 3.32 Un exemple de construction simultanée à droite d’un arbre Union-Find à 5 nœuds et
à gauche de l’arbre binaire associé. La séquence d’appels est : Union(C 1 , C 2 ), Union(C 1 , C 3 ),
Union(C 4 , C 5 ) et Union(C 4 , C 1 )
Lemme 3.16 Une forme d’arbre Union-Find de taille n + 1 a même loi qu’une
forme d’arbre Union-Find de taille n, auquel on ajoute, sur l’un des n nœuds choisi
uniformément (avec probabilité 1/n), une feuille supplémentaire.
En effet, construisons un arbre Union-Find à partir de n + 1 objets. À la première
étape, on obtient un petit arbre à deux sommets (colorions les deux sommets de ce
petit arbre et considérons que c’est un gros sommet coloré) et n − 1 arbres réduits
à leur racine. C’est une forêt de n arbres, qui donne donc par l’algorithme UnionFind une forme d’arbre Union-Find de taille n. Or, une forme d’arbre Union-Find
de taille n a même loi qu’une forme d’arbre Union-Find de taille n dont un des
sommets est coloré. Et la loi de cette forme d’arbres Union-Find de taille n dont un
des sommets est coloré ne dépend pas du choix de l’objet que l’on colore. Ainsi est
justifiée la propriété du lemme 3.16 ci-dessus.
Grâce à la bijection plus haut (celle de la figure 3.32), cette uniformité sur
le processus d’arbres Union-Find se traduit par la pousse uniforme de l’arbre
binaire associé en chacune de ses feuilles justement étiquetées par 1, 2, . . . , n. Cet
arbre binaire associé pousse donc comme un abr, autrement dit comme un arbre
bourgeonnant. Ainsi, la hauteur d’un arbre Union-Find est la même que la hauteur
à gauche d’un abr.
Ces bijections et ces dynamiques sont connues depuis les travaux de Doyle et
Rivest [66], Knuth et Schönhage [158], Devroye [56, 57], Pittel [209].