2.1 Aléa sur les arbres non marqués
43
Fig. 2.2 Croissance d’un arbre bourgeonnant : la feuille (verte) de l’arbre de gauche est remplacée
par un nœud interne et deux feuilles (rouges) dans l’arbre de droite
– puis deux familles d’arbres planaires équilibrés : les arbres 2-3 et les arbres-B,
tous deux compris comme formes d’arbres et non comme arbres de recherche ;
nous considérerons l’ensemble des arbres 2-3 et arbres-B de hauteur fixée, et
l’ensemble des arbres 2-3 à nombre de clés fixé (dans les deux cas, le nombre de
nœuds de l’arbre est variable) ;
– et enfin, les arbres de Pólya, qui sont non planaires.
2.1.2 Arbres bourgeonnants
Nous pouvons définir un processus discret d’arbres binaires complets, c’est-à-dire
une suite (τ n ) n≥0 d’arbres binaires complets, en faisant pousser l’arbre entre les
instants n et n + 1 comme suit : au temps 0, partons de l’arbre réduit à une feuille ;
au temps n, choisissons uniformément l’une des n + 1 feuilles de l’arbre τ n et
remplaçons-la par un nœud interne et deux feuilles (figure 2.2). Nous appelons
ces arbres des arbres bourgeonnants. 1 Ici, nous convenons que la taille d’un arbre
binaire complet est le nombre de ses nœuds internes, donc |τ 0 | = 0 et l’arbre τ n est
de taille n.
Autrement dit, en appelant V n la feuille de τ n choisie uniformément parmi ses
n + 1 feuilles, sur laquelle poussent deux nouvelles feuilles V n 0 et V n 1, la suite
(τ n ) n≥0 est une chaîne de Markov à valeurs dans l’ensemble B des arbres binaires
complets, définie par τ 0 = {ε} et τ n+1 = τ n ∪ {V n 0, V n 1} avec
P(V n = u | τ n ) =
1
n + 1
, u ∈ ∂τ n .
(2.1)
1 Ce nom peut parfois désigner un autre type d’arbres, utilisé pour l’énumération de cartes planaires
et introduit par Schaeffer [230].
43
Fig. 2.2 Croissance d’un arbre bourgeonnant : la feuille (verte) de l’arbre de gauche est remplacée
par un nœud interne et deux feuilles (rouges) dans l’arbre de droite
– puis deux familles d’arbres planaires équilibrés : les arbres 2-3 et les arbres-B,
tous deux compris comme formes d’arbres et non comme arbres de recherche ;
nous considérerons l’ensemble des arbres 2-3 et arbres-B de hauteur fixée, et
l’ensemble des arbres 2-3 à nombre de clés fixé (dans les deux cas, le nombre de
nœuds de l’arbre est variable) ;
– et enfin, les arbres de Pólya, qui sont non planaires.
2.1.2 Arbres bourgeonnants
Nous pouvons définir un processus discret d’arbres binaires complets, c’est-à-dire
une suite (τ n ) n≥0 d’arbres binaires complets, en faisant pousser l’arbre entre les
instants n et n + 1 comme suit : au temps 0, partons de l’arbre réduit à une feuille ;
au temps n, choisissons uniformément l’une des n + 1 feuilles de l’arbre τ n et
remplaçons-la par un nœud interne et deux feuilles (figure 2.2). Nous appelons
ces arbres des arbres bourgeonnants. 1 Ici, nous convenons que la taille d’un arbre
binaire complet est le nombre de ses nœuds internes, donc |τ 0 | = 0 et l’arbre τ n est
de taille n.
Autrement dit, en appelant V n la feuille de τ n choisie uniformément parmi ses
n + 1 feuilles, sur laquelle poussent deux nouvelles feuilles V n 0 et V n 1, la suite
(τ n ) n≥0 est une chaîne de Markov à valeurs dans l’ensemble B des arbres binaires
complets, définie par τ 0 = {ε} et τ n+1 = τ n ∪ {V n 0, V n 1} avec
P(V n = u | τ n ) =
1
n + 1
, u ∈ ∂τ n .
(2.1)
1 Ce nom peut parfois désigner un autre type d’arbres, utilisé pour l’énumération de cartes planaires
et introduit par Schaeffer [230].