6.2 Analyse de la hauteur
249
Plusieurs méthodes (Devroye et Reed [62, 218], Drmota [67]) permettent de
montrer que la variance de la hauteur d’un arbre binaire de recherche est d’ordre
de grandeur constant. Des conjectures, encore non résolues, concernent le nombre
de feuilles au dernier niveau de l’arbre.
6.2.3 Connexion abr - arbre de Yule
L’idée de plonger un processus discret en temps continu est ancienne et très
fructueuse. Nous en reparlerons pour les urnes à la section 9.4. Pour l’arbre binaire
de recherche, ou plutôt pour la forme de l’abr, l’idée remonte à Pittel [207] et peut
être décrite de la façon suivante.
Considérons le processus de branchement à temps continu suivant, appelé
processus de Yule : il y a un ancêtre à l’instant 0 situé en 0 et il a une durée de
vie qui est une variable aléatoire de loi exponentielle de paramètre 1. À sa mort,
il donne naissance à deux enfants, qui sont situés à la position +1 et qui vivent
chacun indépendamment l’un de l’autre, chacun ayant une durée de vie de loi
exponentielle de paramètre 1. Ainsi de suite, chaque individu a une durée de vie de
loi exponentielle de paramètre 1 et quand il meurt, il donne naissance à deux enfants
situés à une distance +1 de lui-même. La figure 6.8 en donne une représentation.
Le processus d’arbres ainsi produit est noté (τ Yule
t
) t ≥0 , et l’arbre τ Yule
t
s’appelle
arbre de Yule, c’est un arbre binaire complet dont les nœuds internes (qui sont des
mots binaires) sont marqués par leur position sur R, ici par des entiers ; autrement
dit, dans ce processus, chaque nœud de l’arbre est marqué par son numéro de
génération. Une autre représentation est possible, où l’on voit mieux les générations,
comme sur la figure 6.9.
•
0
ε
R
T 1
T 2
T 3
t
1
2
3
•
0
•
1
•
00
•
01
•
010
011
•
Fig. 6.8 Une représentation d’un arbre de Yule
249
Plusieurs méthodes (Devroye et Reed [62, 218], Drmota [67]) permettent de
montrer que la variance de la hauteur d’un arbre binaire de recherche est d’ordre
de grandeur constant. Des conjectures, encore non résolues, concernent le nombre
de feuilles au dernier niveau de l’arbre.
6.2.3 Connexion abr - arbre de Yule
L’idée de plonger un processus discret en temps continu est ancienne et très
fructueuse. Nous en reparlerons pour les urnes à la section 9.4. Pour l’arbre binaire
de recherche, ou plutôt pour la forme de l’abr, l’idée remonte à Pittel [207] et peut
être décrite de la façon suivante.
Considérons le processus de branchement à temps continu suivant, appelé
processus de Yule : il y a un ancêtre à l’instant 0 situé en 0 et il a une durée de
vie qui est une variable aléatoire de loi exponentielle de paramètre 1. À sa mort,
il donne naissance à deux enfants, qui sont situés à la position +1 et qui vivent
chacun indépendamment l’un de l’autre, chacun ayant une durée de vie de loi
exponentielle de paramètre 1. Ainsi de suite, chaque individu a une durée de vie de
loi exponentielle de paramètre 1 et quand il meurt, il donne naissance à deux enfants
situés à une distance +1 de lui-même. La figure 6.8 en donne une représentation.
Le processus d’arbres ainsi produit est noté (τ Yule
t
) t ≥0 , et l’arbre τ Yule
t
s’appelle
arbre de Yule, c’est un arbre binaire complet dont les nœuds internes (qui sont des
mots binaires) sont marqués par leur position sur R, ici par des entiers ; autrement
dit, dans ce processus, chaque nœud de l’arbre est marqué par son numéro de
génération. Une autre représentation est possible, où l’on voit mieux les générations,
comme sur la figure 6.9.
•
0
ε
R
T 1
T 2
T 3
t
1
2
3
•
0
•
1
•
00
•
01
•
010
011
•
Fig. 6.8 Une représentation d’un arbre de Yule