256
6 Arbres binaires de recherche
6.3.2 Hauteur des arbres récursifs
Dans la section 6.3.1 qui précède est décrite la transformation qui fait passer d’un
arbre récursif à un arbre binaire associé. Dans cette transformation, la hauteur de
l’arbre récursif devient la profondeur à gauche de l’arbre binaire associé.
Dans le théorème suivant (dont la preuve dépasse le niveau de cet
ouvrage), le premier item dans sa version convergence en probabilité est dû à
Devroye [56, th. 10] pour les arbres Union-Find, qui, on l’a vu plus haut, ont
même loi que les arbres récursifs ; la convergence presque sûre a été obtenue
par Pittel [209] par plongement en temps continu. Les items suivants sont
dus à Drmota et se trouvent dans son livre [68], section 6.4. Les résultats de
Drmota sont obtenus par des méthodes analytiques non probabilistes, à base
d’équations différentielles retardées.
Théorème 6.31 La hauteur H n d’un arbre récursif à n nœuds se comporte
lorsque n tend vers l’infini de la façon suivante.
(i)
H n
log n
−→
n→∞
e
p.s.
(ii)
E(H n ) ∼ e log n ;
Var(H n ) = O(1).
(iii) Il existe une constante C > 0 tel que pour tout η > 0,
P (|H n − E(H n )| ≥ η) = O
e
−Cη
.
6.4 Formes d’arbres binaires de recherche biaisées
L’idée est la même que pour l’arbre de Galton-Watson biaisé de la section 5.1.2 :
une branche pousse à une vitesse différente, c’est l’épine dorsale (en anglais spine),
et les sous-arbres qui en partent sont de même loi que l’arbre générique.
Rappelons que les arbres binaires de recherche aléatoires sous la loi Ord poussent
par insertion uniforme sur les feuilles. Autrement dit, les formes d’arbres binaires