228
6 Arbres binaires de recherche
Fig. 6.4 Un abr de taille 7, τ 7 , construit avec les clés x 1 = 0,3 ; x 2 = 0,1 ; x 3 = 0,4 ; x 4 =
0,15 ; x 5 = 0,9 ; x 6 = 0,02 ; x 7 = 0,2 et l’abr τ 8 obtenu par insertion ultérieure de x 8 = 0,6 sur
la feuille bleue. La profondeur d’insertion de x 8 dans τ 7 est d(x 8 , τ 7 ) = 3. L’insertion supprime
une feuille au niveau 3 et crée deux feuilles au niveau 4
niveau (k − 1) :
U k (τ n+1 ) = U k (τ n ) − 1 {D n+1 =k} + 2 1 {k≥1} 1 {D n+1 =k−1} .
Avec l’équation (6.7), nous avons une relation de récurrence sur le polynôme de
niveau 2 :
E(W τ n+1 (z)
τ n ) = E
+∞
k=0
U k (τ n+1 )z
k
τ n
=
+∞
k=0
z
k E
U k (τ n ) − 1 {D n+1 =k} + 2 1 {k≥1} 1 {D n+1 =k−1}
τ n
=
+∞
k=0
z
k E
U k (τ n ) − P(D n+1 = k
τ n ) + 21 {k≥1} P(D n+1 = k − 1
τ n )
= W τn (z) −
+∞
k=0
U k (τ n )
n + 1
z
k + 2
+∞
k=1
U k−1 (τ n )
n + 1
z
k
= W τn (z) −
1
n + 1
W τn (z) +
2z
n + 1
W τn (z),
ce qui finalement donne
E(W τ n+1 (z)
τ n ) =
n + 2z
n + 1
W τ n (z) .
(6.9)
2 Rappelons que E(1 A |τ n ) = P(A | τ n ).