276
6 Arbres binaires de recherche
Fig. 6.18 L’état d’un tableau T juste avant la fin de la partition suivant le pivot x = T [1]
4
2
1
3
5 6 7
1
2
3
4
5
6
7
j
T[j]
Fig. 6.19 Le nombre d’échanges faits lors de la partition avec pour pivot T [1] = 5, et juste avant
le placement de ce pivot, est égal au nombre de points de la permutation σ = 5271643 à l’intérieur
de la partie hachurée
dernier échange entre T [1] et T [k] permet de placer le pivot à sa place définitive ;
la figure 6.18 donne l’état d’un tableau T juste avant cet échange final.
Établissons maintenant un lien avec un paramètre de la permutation associée au
tableau. Prenons par exemple n = 7 et la permutation σ = 5 2 7 1 6 4 3, stockée
dans le tableau T : T [i] = σ (i). Le pivot est T [1] = 5, et les sous-tableaux
gauche et droit, avant partition, sont respectivement [2, 7, 1, 6] et [4, 3]. Soit ν(T ) le
nombre d’échanges faits par la partition sur un tableau T , hors placement du pivot ;
le nombre total d’échanges fait par la partition est donc ν(T ) + 1. En écrivant ν(T )
sous la forme
ν(T ) =
[1 . . k − 1] ∩ σ
−1 ([k + 1 . . n])
=
[k + 1 . . n] ∩ σ
−1 ([1 . . k − 1])
,
nous pouvons en donner une interprétation graphique : c’est le nombre de points
dans le quart de plan ouvert hachuré de la figure 6.19.
Intéressons-nous maintenant à la valeur moyenne de ν(T ) lorsque le tableau T
suit la loi uniforme sur les permutations. En considérant les possibilités de choix
de j clés supérieures à k dans le sous-tableau de gauche, et de j clés inférieures
à k dans le sous-tableau de droite, nous obtenons aisément la probabilité que ν(T )