6.3 Arbres récursifs
255
Lien avec les arbres bourgeonnants
Dans l’exemple de la figure 6.10, l’arbre récursif τ a 14 nœuds et est en bijection
avec un arbre binaire τ de taille 13. Il y a 14 possibilités d’insertion dans l’arbre
récursif : nous pouvons choisir d’attacher une nouvelle feuille à chaque nœud et il
y a une seule manière de le faire, l’arbre étant non planaire ; si nous complétons
l’arbre binaire, nous obtenons un arbre à 13 nœuds internes et 14 feuilles, donc avec
14 possibilités d’insertion.
Regardons maintenant comment pousse un tel arbre : une suite d’arbres récursifs
se transforme en une suite d’arbres binaires croissants et ils poussent de la même
façon que les arbres bourgeonnants de la section 2.1.2 : l’insertion uniforme sur les
nœuds de l’arbre récursif se transforme en insertion uniforme sur les nœuds externes
de l’arbre binaire croissant. C’est donc un arbre bourgeonnant.
Remarque 6.29 L’arbre binaire τ obtenu à partir de τ n’est pas un arbre binaire de
recherche ; par contre sa forme π( τ) est bien un arbre bourgeonnant, c’est-à-dire la
forme d’un arbre binaire de recherche.
Lien avec les arbres Union-Find
Dans la section 3.4.3 a été présentée la bijection entre un arbre Union-Find construit
avec l’un des algorithmes Union-Find et un arbre binaire de recherche (voir la
figure 3.32). Dans cette bijection, le niveau d’un nœud dans l’arbre final UnionFind est exactement son niveau à gauche dans l’arbre binaire associé. En outre, il
apparaît que le processus d’arbres binaires associés pousse comme un abr, autrement
dit comme un processus d’arbres bourgeonnants. Par conséquent la hauteur d’un
arbre Union-Find est la même que la hauteur à gauche d’un abr.
La proposition suivante résume la section. Ces bijections ainsi que la dynamique
de ces processus d’arbres sont utilisées dans l’étude de la hauteur et du profil des
arbres récursifs dans Fuchs et al. [112] et dans le chapitre 4 de la thèse de JabbourHattab [140]. C’est pour cette raison que les résultats sur la hauteur des arbres
récursifs sont analogues à ceux sur la hauteur des abr.
Proposition 6.30 Un processus d’arbres récursifs a même loi qu’un processus
d’arbres Union-Find. Pour chacun d’eux est associé un processus d’arbres binaires
qui sont des arbres bourgeonnants. En particulier, leur hauteur est aussi la hauteur
à gauche de l’arbre binaire associé.
255
Lien avec les arbres bourgeonnants
Dans l’exemple de la figure 6.10, l’arbre récursif τ a 14 nœuds et est en bijection
avec un arbre binaire τ de taille 13. Il y a 14 possibilités d’insertion dans l’arbre
récursif : nous pouvons choisir d’attacher une nouvelle feuille à chaque nœud et il
y a une seule manière de le faire, l’arbre étant non planaire ; si nous complétons
l’arbre binaire, nous obtenons un arbre à 13 nœuds internes et 14 feuilles, donc avec
14 possibilités d’insertion.
Regardons maintenant comment pousse un tel arbre : une suite d’arbres récursifs
se transforme en une suite d’arbres binaires croissants et ils poussent de la même
façon que les arbres bourgeonnants de la section 2.1.2 : l’insertion uniforme sur les
nœuds de l’arbre récursif se transforme en insertion uniforme sur les nœuds externes
de l’arbre binaire croissant. C’est donc un arbre bourgeonnant.
Remarque 6.29 L’arbre binaire τ obtenu à partir de τ n’est pas un arbre binaire de
recherche ; par contre sa forme π( τ) est bien un arbre bourgeonnant, c’est-à-dire la
forme d’un arbre binaire de recherche.
Lien avec les arbres Union-Find
Dans la section 3.4.3 a été présentée la bijection entre un arbre Union-Find construit
avec l’un des algorithmes Union-Find et un arbre binaire de recherche (voir la
figure 3.32). Dans cette bijection, le niveau d’un nœud dans l’arbre final UnionFind est exactement son niveau à gauche dans l’arbre binaire associé. En outre, il
apparaît que le processus d’arbres binaires associés pousse comme un abr, autrement
dit comme un processus d’arbres bourgeonnants. Par conséquent la hauteur d’un
arbre Union-Find est la même que la hauteur à gauche d’un abr.
La proposition suivante résume la section. Ces bijections ainsi que la dynamique
de ces processus d’arbres sont utilisées dans l’étude de la hauteur et du profil des
arbres récursifs dans Fuchs et al. [112] et dans le chapitre 4 de la thèse de JabbourHattab [140]. C’est pour cette raison que les résultats sur la hauteur des arbres
récursifs sont analogues à ceux sur la hauteur des abr.
Proposition 6.30 Un processus d’arbres récursifs a même loi qu’un processus
d’arbres Union-Find. Pour chacun d’eux est associé un processus d’arbres binaires
qui sont des arbres bourgeonnants. En particulier, leur hauteur est aussi la hauteur
à gauche de l’arbre binaire associé.