6.2 Analyse de la hauteur
243
≤
2
n
n−1
i=0
E(Z i + Z n−1−i )
=
4
n
n−1
i=0
E(Z i ),
où nous avons utilisé l’inégalité max(a, b) ≤ a + b. Ceci permet de montrer par
récurrence sur n que
E(Z n ) ≤
1
4
n + 3
3
,
en utilisant l’identité combinatoire suivante :
n−1
i=0
i + 3
3
=
n + 3
4
.
Cette identité peut se montrer par récurrence sur n et aussi par le raisonnement
combinatoire suivant : pour choisir 4 éléments parmi n + 3, faisons une partition des
cas, suivant le numéro du plus grand, de 4 à n + 3 ; les 3 autres sont donc choisis
parmi 3 + i pour i allant de 0 à n − 1. Ainsi
E(Z n ) ≤
(n + 3)(n + 2)(n + 1)
24
.
Puis l’inégalité de Jensen (voir section C.4) donne
E(Z n ) = E
2
h(τ n )
≥ 2
E(h(τ n )) ,
ce qui conduit à E(h(τ n )) ≤ log 2 (E(Z n )), puis à E(h(τ n )) ≤
3
log 2 log n ≤
4,33 log n. Comme par ailleurs la hauteur d’un arbre binaire de taille n est au moins
égale à celle de l’arbre parfait de même taille, et que celle-ci vaut log 2 (n + 1) − 1
(cf. l’équation (1.7)), nous obtenons finalement
E(h(τ n )) = (log n).
Remarquons que la constante 4,33 obtenue devant log n n’est pas si grossière (nous
verrons dans la section suivante le vrai équivalent c log n avec c = 4,31107 . . . ).