274
6 Arbres binaires de recherche
Fig. 6.17 En haut, l’état du
tableau vers la fin de
l’algorithme de partition,
juste avant le placement du
pivot x ; en bas, les deux
sous-tableaux T 1 et T 2 après
placement du pivot
Pour un tableau T , appelons k la place finale du pivot x. Notons T 1 et T 2 les soustableaux T [1 . . k − 1] et T [k + 1 . . n] après placement du pivot (cf. figure 6.17) :
c(T ) = p(T ) + c(T 1 ) + c(T 2 ).
Définissons la variable aléatoire Y (T ), à valeurs dans {1, 2, . . . , n}, qui est égale à
l’indice k donnant la place finale du pivot ; c’est aussi le rang de la valeur T [1] et,
sous le modèle des permutations uniformes, Y suit une loi uniforme. Le pivot va
donc à la place k avec une probabilité 1/n, et
c n =
T ∈S n
1
n!
p(T ) +
T ∈S n
1
n!
(c(T 1 ) + c(T 2 ))
= p n +
n
k=1
T : le pivot va en T [k]
1
n!
(c(T 1 ) + c(T 2 )).
Les tableaux T 1 et T 2 suivent eux aussi une loi uniforme, respectivement parmi les
permutations sur k −1 éléments, et parmi celles sur n−k éléments, et nous obtenons
donc une relation de récurrence sur les c p , valable a priori pour n ≥ 3 :
c n = p n +
1
n
n
k=1
(c k−1 + c n−k ) = p n +
2
n
n−1
k=0
c k .
Il est aisé de vérifier que cette dernière relation est aussi valide pour n = 2. Nous
obtenons donc n(c n − p n ) = 2
n−1
k=1 c k , qui conduit par soustraction à l’égalité
suivante, valide pour n ≥ 2 :
n(c n − p n ) − (n − 1)(c n−1 − p n−1 ) = 2c n−1 .
En divisant par n(n + 1), nous obtenons
c n
n + 1
=
c n−1
n
+
np n − (n − 1)p n−1
n(n + 1)
.