242
6 Arbres binaires de recherche
6.2 Analyse de la hauteur
Tout d’abord, la section 6.2.1 présente une approche élémentaire pour obtenir
l’ordre asymptotique log n, à l’instar du livre de Cormen et al. [50].
Dans la suite, la hauteur est étudiée en même temps que le niveau de saturation,
car ces deux paramètres sont dans une sorte de dualité : la hauteur (respectivement
le niveau de saturation) est liée à la position la plus à droite (respectivement la plus à
gauche) d’une particule dans une marche aléatoire branchante (définie section 5.3).
Cette connexion est établie dans la section 6.2.2. Le théorème principal 6.22 établit
que l’ordre de grandeur de la hauteur h(τ n ) et du niveau de saturation s(τ n ) d’un
abr, lorsque n tend vers +∞, est log n.
Des méthodes analytiques non probabilistes, à base d’équations différentielles
retardées, sont utilisées par Drmota et exposées dans le livre [68], pour obtenir
des résultats sur la concentration autour de l’espérance de la hauteur. Nous ne
les développons pas ici. En revanche, nous développons dans la section 6.2.3 la
méthode de plongement en temps continu qui est efficace pour obtenir des résultats
fins sur la hauteur d’un abr. Cette méthode permet de relier le processus à temps
discret (τ n ) n∈N à un processus de Yule (τ Yule
t
) t ≥0 à temps continu. C’est cette même
méthode, classique en probabilités, qui permet de démontrer le théorème 6.12 sur le
profil d’un abr, démonstration qui n’est pas détaillée ici (voir [39]).
6.2.1 Une approche élémentaire
Posons Z 0 = 0 et pour tout n ≥ 1, Z n := 2 h(τ n ) . Pour un abr réduit à sa racine,
n = 1 et Z 1 = 2 0 = 1. Puisque la hauteur d’un abr vaut 1+ le maximum des
hauteurs de ses sous-arbres gauche et droit, nous avons, selon la taille du sous-arbre
gauche et d’après le principe « diviser pour régner » de la proposition 6.1,
h(τ n )
L
= 1 +
n−1
i=0
1 {|τ
(g)
n |=i}
max(h(τ i ), h(τ n−1−i )),
d’où
Z n
L
= 2
n−1
i=0
1 {|τ
(g)
n |=i}
max(Z i , Z n−1−i ).
Nous allons montrer que E(Z n ) est polynomial en n. En effet,
E(Z n ) = 2
n−1
i=0
1
n
E(max(Z i , Z n−1−i ))
6 Arbres binaires de recherche
6.2 Analyse de la hauteur
Tout d’abord, la section 6.2.1 présente une approche élémentaire pour obtenir
l’ordre asymptotique log n, à l’instar du livre de Cormen et al. [50].
Dans la suite, la hauteur est étudiée en même temps que le niveau de saturation,
car ces deux paramètres sont dans une sorte de dualité : la hauteur (respectivement
le niveau de saturation) est liée à la position la plus à droite (respectivement la plus à
gauche) d’une particule dans une marche aléatoire branchante (définie section 5.3).
Cette connexion est établie dans la section 6.2.2. Le théorème principal 6.22 établit
que l’ordre de grandeur de la hauteur h(τ n ) et du niveau de saturation s(τ n ) d’un
abr, lorsque n tend vers +∞, est log n.
Des méthodes analytiques non probabilistes, à base d’équations différentielles
retardées, sont utilisées par Drmota et exposées dans le livre [68], pour obtenir
des résultats sur la concentration autour de l’espérance de la hauteur. Nous ne
les développons pas ici. En revanche, nous développons dans la section 6.2.3 la
méthode de plongement en temps continu qui est efficace pour obtenir des résultats
fins sur la hauteur d’un abr. Cette méthode permet de relier le processus à temps
discret (τ n ) n∈N à un processus de Yule (τ Yule
t
) t ≥0 à temps continu. C’est cette même
méthode, classique en probabilités, qui permet de démontrer le théorème 6.12 sur le
profil d’un abr, démonstration qui n’est pas détaillée ici (voir [39]).
6.2.1 Une approche élémentaire
Posons Z 0 = 0 et pour tout n ≥ 1, Z n := 2 h(τ n ) . Pour un abr réduit à sa racine,
n = 1 et Z 1 = 2 0 = 1. Puisque la hauteur d’un abr vaut 1+ le maximum des
hauteurs de ses sous-arbres gauche et droit, nous avons, selon la taille du sous-arbre
gauche et d’après le principe « diviser pour régner » de la proposition 6.1,
h(τ n )
L
= 1 +
n−1
i=0
1 {|τ
(g)
n |=i}
max(h(τ i ), h(τ n−1−i )),
d’où
Z n
L
= 2
n−1
i=0
1 {|τ
(g)
n |=i}
max(Z i , Z n−1−i ).
Nous allons montrer que E(Z n ) est polynomial en n. En effet,
E(Z n ) = 2
n−1
i=0
1
n
E(max(Z i , Z n−1−i ))