6.2 Analyse de la hauteur
245
Définition 6.19 (Arbre idéal) Attachons à tous les nœuds u d’un arbre binaire
des variables aléatoires U u , de loi uniforme sur [0, 1], de sorte que pour tout u,
U u0 + U u1 = 1 et dès que deux nœuds v et w ne sont pas sœurs, 8 alors U v et U w
sont indépendantes. L’arbre binaire (infini) marqué par les U u s’appelle l’arbre idéal
ou arbre de la bisection (cf. le problème 5.5).
Un calcul immédiat conduit au
Lemme 6.20
(i) La taille du sous-arbre gauche de la racine, V
(n)
0 , a même loi que nU 0 ;
la taille du sous-arbre droit de la racine, n − 1 − V
(n)
0
= V
(n)
1 a même loi
que n(1 − U 0 ) = =nU 1
(ii)
V
(n)
0
n
D
−→
n→∞
U 0
et
V
(n)
1
n
D
−→
n→∞
U 1 .
De la même façon, pour n’importe quel nœud u de l’arbre, le sous-arbre gauche
est de taille V
(n)
u0 qui a même loi que
(n)
u U u0 et le sous-arbre droit est de taille
V
(n)
u1 qui a même loi que
(n)
u (1 −U u0 ) = =V
(n)
u U u1 . Le lemme ci-dessus valable
pour la racine de l’arbre s’écrit de manière analogue pour un nœud u, ce qui conduit
à la proposition 6.21 ci-dessous, du moins sa version en loi.
Par récurrence sur k, il est facile de voir que pour un nœud u à distance k de la
racine, c’est-à-dire à profondeur k, u s’écrit sous la forme u = u 1 u 2 . . . u k et V
(n)
u a
même loi qu’un produit du type . . . nU u 1 u 1 u 2 . . . U u 1 ...u k
Pour résumer, la proposition suivante admet une version en loi (que l’on peut
aussi trouver dans la section 4.1 de Broutin et al. [31]) et une version presque sûre
dont la démonstration se trouve dans [39]. Elle exprime qu’à tout endroit de l’arbre
binaire de recherche, les proportions de nœuds dans les sous-arbres gauche et droit
sont asymptotiquement de loi U et 1 − U , où U est une loi uniforme sur l’intervalle
[0, 1].
Proposition 6.21 Pour tout u ∈ {0, 1} ∗ , soit V
(n)
u la taille du sous-arbre issu du
nœud u d’un abr τ n de taille n sous la loi Ord. Les enfants gauche et droit de u sont
désignés comme d’habitude par u0 et u1 respectivement. Alors presque sûrement
quand n → +∞,
V
(n)
u0
V
(n)
u
−→ U u0
et
V
(n)
u1
V
(n)
u
−→ U u1 ,
8 Nous disons que deux nœuds v et w sont sœurs lorsqu’il existe u ∈ {0, 1} ∗ et j, k ∈ {0, 1}, j = k
tels que v = uj et w = uk.
245
Définition 6.19 (Arbre idéal) Attachons à tous les nœuds u d’un arbre binaire
des variables aléatoires U u , de loi uniforme sur [0, 1], de sorte que pour tout u,
U u0 + U u1 = 1 et dès que deux nœuds v et w ne sont pas sœurs, 8 alors U v et U w
sont indépendantes. L’arbre binaire (infini) marqué par les U u s’appelle l’arbre idéal
ou arbre de la bisection (cf. le problème 5.5).
Un calcul immédiat conduit au
Lemme 6.20
(i) La taille du sous-arbre gauche de la racine, V
(n)
0 , a même loi que nU 0 ;
la taille du sous-arbre droit de la racine, n − 1 − V
(n)
0
= V
(n)
1 a même loi
que n(1 − U 0 ) = =nU 1
(ii)
V
(n)
0
n
D
−→
n→∞
U 0
et
V
(n)
1
n
D
−→
n→∞
U 1 .
De la même façon, pour n’importe quel nœud u de l’arbre, le sous-arbre gauche
est de taille V
(n)
u0 qui a même loi que
(n)
u U u0 et le sous-arbre droit est de taille
V
(n)
u1 qui a même loi que
(n)
u (1 −U u0 ) = =V
(n)
u U u1 . Le lemme ci-dessus valable
pour la racine de l’arbre s’écrit de manière analogue pour un nœud u, ce qui conduit
à la proposition 6.21 ci-dessous, du moins sa version en loi.
Par récurrence sur k, il est facile de voir que pour un nœud u à distance k de la
racine, c’est-à-dire à profondeur k, u s’écrit sous la forme u = u 1 u 2 . . . u k et V
(n)
u a
même loi qu’un produit du type . . . nU u 1 u 1 u 2 . . . U u 1 ...u k
Pour résumer, la proposition suivante admet une version en loi (que l’on peut
aussi trouver dans la section 4.1 de Broutin et al. [31]) et une version presque sûre
dont la démonstration se trouve dans [39]. Elle exprime qu’à tout endroit de l’arbre
binaire de recherche, les proportions de nœuds dans les sous-arbres gauche et droit
sont asymptotiquement de loi U et 1 − U , où U est une loi uniforme sur l’intervalle
[0, 1].
Proposition 6.21 Pour tout u ∈ {0, 1} ∗ , soit V
(n)
u la taille du sous-arbre issu du
nœud u d’un abr τ n de taille n sous la loi Ord. Les enfants gauche et droit de u sont
désignés comme d’habitude par u0 et u1 respectivement. Alors presque sûrement
quand n → +∞,
V
(n)
u0
V
(n)
u
−→ U u0
et
V
(n)
u1
V
(n)
u
−→ U u1 ,
8 Nous disons que deux nœuds v et w sont sœurs lorsqu’il existe u ∈ {0, 1} ∗ et j, k ∈ {0, 1}, j = k
tels que v = uj et w = uk.