244
6 Arbres binaires de recherche
6.2.2 Connexion abr - bisection
Cette connexion est utile pour étudier la hauteur des abr. Les résultats sur la hauteur
des abr (et d’arbres plus généraux) sont essentiellement dus à Devroye [56] et ceux
sur les marches aléatoires branchantes (dont la bisection est un cas particulier) à
Biggins [24]. En outre, l’article de Broutin et al. [31] présente des preuves complètes
de ce qui suit ici. Nous allons d’abord expliquer comment les abr sont proches, en
un sens à préciser, des marches aléatoires branchantes. Nous nous ramènerons à
trouver la hauteur de l’arbre idéal (dans la terminologie de [31]) défini par la marche
aléatoire branchante de la bisection.
La connexion
Rappelons que τ n est l’abr de taille n, ses nœuds u sont canoniquement numérotés
par les mots de l’alphabet {0, 1} ∗ , et τ u
n est le sous-arbre de τ n issu du nœud u.
Pour tout nœud u de τ n , appelons 7 V
(n)
u
= |τ u
n | la taille (c’est-à-dire le nombre
de nœuds) du sous-arbre issu de u. Ainsi, pour la racine, notée ε, V
(n)
ε
= n ; pour
les deux sous-arbres de la racine, V
(n)
0
= |τ 0
n | = |τ
(g)
n | (avec la notation de la
section 2.2.3) est la taille du sous-arbre gauche et V
(n)
1
= |τ 1
n | = n − 1 − V
(n)
0
=
|τ
(d)
n | est la taille du sous-arbre droit. Par la proposition 6.1 qui traduit le modèle
probabiliste choisi et le principe « diviser pour régner », il est clair que V
(n)
0
est
équidistribuée sur {0, 1, . . . , n − 1}.
La loi de V
(n)
u nous intéresse, car la hauteur h(τ n ) de l’arbre est reliée aux V
(n)
u
par la dualité (évidente) suivante entre événements :
{h(τ n ) ≥ k} =
max
|u|=k
V
(n)
u ≥ 1
.
(6.20)
Attention : le calcul de la loi de h(τ n ) ne sera pas simple, car les V
(n)
u
sont très
dépendants les uns des autres.
7 Nous préférons cette notation à V u (τ n ) qui est un peu plus lourde.