246
6 Arbres binaires de recherche
où U u0 et U u1 sont des variables aléatoires de loi uniforme sur l’intervalle [0, 1] et
U u0 + U u1 = 1. De plus, pour tous v et w de τ n tels que v et w ne sont pas sœurs,
alors les variables U v et U w sont indépendantes.
Par conséquent p.s. quand n → +∞
V
(n)
u
n
−→
v≤u
U v ,
où le produit porte sur les v préfixes de u, v = ε et où les U v , v ≤ u, sont des
variables aléatoires i.i.d. de loi uniforme sur [0, 1] et pour tout v ∈ {0, 1} ∗ , U v0 +
U v1 = 1.
Cette proposition permet de relier des variables définies sur l’abr (les V
(n)
u ) à des
variables uniformes vérifiant la propriété U u0 + U u1 = 1, correspondant à la
bisection étudiée en problème 5.5. Autrement dit, elle permet de faire le lien entre
l’abr et l’arbre idéal.
Conséquence pour la hauteur des abr
Grâce à l’égalité (6.20) et à la proposition 6.21, la loi de la hauteur h(τ n ) est
asymptotiquement (quand n → +∞) donnée par max
u,|u|=k
v≤u
U v . Dans la bisection
(cf. problème 5.5), la position X u de u est donnée par
X u = − log
v≤u
U v
.
En prenant le logarithme, il est clair que le maximum ci-dessus est donné par le
minimum pour |u| = k des positions X u dans la bisection. Or le comportement
du minimum des positions dans une marche aléatoire branchante a été élucidé par
Biggins [24] ; c’est le cas aussi pour le comportement du maximum qui est de
manière duale associé au niveau de saturation s(τ n ) d’un abr τ n (nous ne détaillons
pas, mais c’est analogue à ce qui vient d’être fait pour la hauteur). Le théorème
suivant en est une conséquence.
Théorème 6.22 (hauteur d’un abr) Soit h(τ n ) la hauteur d’un abr τ n et soit s(τ n )
son niveau de saturation. Quand n → +∞,
h(τ n )
log n
−→ c p.s. ;
s(τ n )
log n
−→ c
p.s.,
où c = 4,31107 . . . et c = 0,3733 . . . sont les deux solutions réelles positives de
l’équation
x log 2 + x − x log x = 1.
6 Arbres binaires de recherche
où U u0 et U u1 sont des variables aléatoires de loi uniforme sur l’intervalle [0, 1] et
U u0 + U u1 = 1. De plus, pour tous v et w de τ n tels que v et w ne sont pas sœurs,
alors les variables U v et U w sont indépendantes.
Par conséquent p.s. quand n → +∞
V
(n)
u
n
−→
v≤u
U v ,
où le produit porte sur les v préfixes de u, v = ε et où les U v , v ≤ u, sont des
variables aléatoires i.i.d. de loi uniforme sur [0, 1] et pour tout v ∈ {0, 1} ∗ , U v0 +
U v1 = 1.
Cette proposition permet de relier des variables définies sur l’abr (les V
(n)
u ) à des
variables uniformes vérifiant la propriété U u0 + U u1 = 1, correspondant à la
bisection étudiée en problème 5.5. Autrement dit, elle permet de faire le lien entre
l’abr et l’arbre idéal.
Conséquence pour la hauteur des abr
Grâce à l’égalité (6.20) et à la proposition 6.21, la loi de la hauteur h(τ n ) est
asymptotiquement (quand n → +∞) donnée par max
u,|u|=k
v≤u
U v . Dans la bisection
(cf. problème 5.5), la position X u de u est donnée par
X u = − log
v≤u
U v
.
En prenant le logarithme, il est clair que le maximum ci-dessus est donné par le
minimum pour |u| = k des positions X u dans la bisection. Or le comportement
du minimum des positions dans une marche aléatoire branchante a été élucidé par
Biggins [24] ; c’est le cas aussi pour le comportement du maximum qui est de
manière duale associé au niveau de saturation s(τ n ) d’un abr τ n (nous ne détaillons
pas, mais c’est analogue à ce qui vient d’être fait pour la hauteur). Le théorème
suivant en est une conséquence.
Théorème 6.22 (hauteur d’un abr) Soit h(τ n ) la hauteur d’un abr τ n et soit s(τ n )
son niveau de saturation. Quand n → +∞,
h(τ n )
log n
−→ c p.s. ;
s(τ n )
log n
−→ c
p.s.,
où c = 4,31107 . . . et c = 0,3733 . . . sont les deux solutions réelles positives de
l’équation
x log 2 + x − x log x = 1.