6.3 Arbres récursifs
253
Remarque 6.28 La méthode décrite dans cette section permet de considérer un arbre
binaire de recherche de taille n comme un arbre de branchement (ici un arbre de
Yule) arrêté à un instant T n qui est le premier instant où il y a n individus. Il ne
faut pas confondre (et d’ailleurs les résultats sont très différents) avec un arbre de
Galton-Watson (qui est aussi un arbre de branchement) sous-critique ou critique, qui
n’est pas arrêté mais grossit jusqu’à son extinction, et que l’on conditionne par sa
taille.
6.3 Arbres récursifs
6.3.1 Définition et dynamique
Construction algorithmique
Définissons récursivement 10 un processus (τ n , n ≥ 1) d’arbres dits récursifs comme
suit, de sorte que pour tout n ≥ 1, l’arbre τ n contient n nœuds marqués de 1 à n.
– Pour n = 1, τ 1 est réduit à la racine marquée par 1.
– Pour tout n ≥ 1, l’arbre τ n+1 est obtenu à partir de τ n en reliant un nouveau
nœud, marqué par n + 1, à l’un des n nœuds de τ n , choisi uniformément.
Nous allons voir que les arbres récursifs en tant que processus d’arbres (c’est-àdire leur dynamique) sont en bijection avec les arbres bourgeonnants, c’est-à-dire les
formes d’arbres binaires de recherche. En effet, ils sont en bijection avec des arbres
binaires croissants qui poussent comme des abr. C’est aussi le cas des arbres UnionFind (cf. la section 3.4.3) que l’on peut également associer à des arbres binaires qui
poussent comme des abr, c’est-à-dire des arbres bourgeonnants.
Représentation par un arbre binaire croissant
Bien que les arbres récursifs ne soient pas planaires, nous avons vu en section 1.2.4
que la manière classique de les représenter est d’ordonner les enfants d’un nœud
par ordre croissant de leurs marques. Soit τ un arbre récursif ; nous lui associons
donc un unique représentant planaire R(τ ). Ensuite, par la transformation habituelle
« fille ainée-sœur cadette » (voir la section 1.1.3) appliquée à R(τ ), nous obtenons
un arbre binaire, appelons-le τ , dont les marques croissent le long des branches
allant de la racine vers les feuilles. Nous donnons en figure 6.10 un tel exemple,
avec un arbre récursif et l’arbre binaire qui lui correspond.
Dans cette transformation, le niveau d’un nœud de l’arbre récursif devient (à 1
près) le niveau à gauche de l’arbre binaire associé (le niveau à gauche d’un nœud
10 D’où le nom !
253
Remarque 6.28 La méthode décrite dans cette section permet de considérer un arbre
binaire de recherche de taille n comme un arbre de branchement (ici un arbre de
Yule) arrêté à un instant T n qui est le premier instant où il y a n individus. Il ne
faut pas confondre (et d’ailleurs les résultats sont très différents) avec un arbre de
Galton-Watson (qui est aussi un arbre de branchement) sous-critique ou critique, qui
n’est pas arrêté mais grossit jusqu’à son extinction, et que l’on conditionne par sa
taille.
6.3 Arbres récursifs
6.3.1 Définition et dynamique
Construction algorithmique
Définissons récursivement 10 un processus (τ n , n ≥ 1) d’arbres dits récursifs comme
suit, de sorte que pour tout n ≥ 1, l’arbre τ n contient n nœuds marqués de 1 à n.
– Pour n = 1, τ 1 est réduit à la racine marquée par 1.
– Pour tout n ≥ 1, l’arbre τ n+1 est obtenu à partir de τ n en reliant un nouveau
nœud, marqué par n + 1, à l’un des n nœuds de τ n , choisi uniformément.
Nous allons voir que les arbres récursifs en tant que processus d’arbres (c’est-àdire leur dynamique) sont en bijection avec les arbres bourgeonnants, c’est-à-dire les
formes d’arbres binaires de recherche. En effet, ils sont en bijection avec des arbres
binaires croissants qui poussent comme des abr. C’est aussi le cas des arbres UnionFind (cf. la section 3.4.3) que l’on peut également associer à des arbres binaires qui
poussent comme des abr, c’est-à-dire des arbres bourgeonnants.
Représentation par un arbre binaire croissant
Bien que les arbres récursifs ne soient pas planaires, nous avons vu en section 1.2.4
que la manière classique de les représenter est d’ordonner les enfants d’un nœud
par ordre croissant de leurs marques. Soit τ un arbre récursif ; nous lui associons
donc un unique représentant planaire R(τ ). Ensuite, par la transformation habituelle
« fille ainée-sœur cadette » (voir la section 1.1.3) appliquée à R(τ ), nous obtenons
un arbre binaire, appelons-le τ , dont les marques croissent le long des branches
allant de la racine vers les feuilles. Nous donnons en figure 6.10 un tel exemple,
avec un arbre récursif et l’arbre binaire qui lui correspond.
Dans cette transformation, le niveau d’un nœud de l’arbre récursif devient (à 1
près) le niveau à gauche de l’arbre binaire associé (le niveau à gauche d’un nœud
10 D’où le nom !