8.2 Arbres quadrants de recherche
357
Passons maintenant à la fonction génératrice V (z) :=
n v n z n . L’équation (8.8)
sur les v n se transpose sur V pour donner une équation différentielle linéaire
d’ordre 2, non homogène :
z(1 − z)y
+ (1 − 2z)y
−
2 d
1 − z
y = R(z),
(8.9)
où R s’exprime à partir de la fonction génératrice des coûts à la racine r(z) =
n r n z n :
R(z) =
d
dz
z(1 − z)
d
dz
r(z)
= z(1 − z)r
(z) + (1 − 2z)r
(z).
Dans certains cas, cette équation peut être résolue directement, ce qui donne
des résultats explicites sur les paramètres additifs considérés. Ainsi, Flajolet et
Hoshi [84] étudient l’occupation moyenne des pages dans un arbre quadrant de
recherche paginé, c’est-à-dire un arbre où la décomposition récursive est arrêtée dès
qu’un sous-arbre est de taille au plus b, b étant le nombre d’éléments (clés) qu’une
page mémoire peut contenir. Le péage à la racine r(τ ) qui apparaît alors conduit à
une fonction génératrice r(z) = 1/(1−z)−
0≤n≤b z n , et il est possible de résoudre
explicitement l’équation différentielle (8.9). Nous donnons plus de détails dans le
problème 8.10.
Transformée d’Euler et étude des v n Lorsque nous ne pouvons pas obtenir
directement d’information sur la fonction génératrice V (z) à partir de l’équation
différentielle (8.9), une méthode alternative consiste à passer par sa transformée
d’Euler. La transformée d’Euler d’une fonction f (z) =
n≥0 f n z n est définie (cf.
section B.3.4) par
f
∗ (z) =
1
1 − z
f
z
z − 1
.
(8.10)
Ses coefficients f ∗
n dans son développement en série formelle sont liés aux
coefficients initiaux f n par
f
∗
p =
0≤n≤p
(−1)
n
p
n
f n .
Dans notre contexte, la transformation d’Euler appliquée à l’équation différentielle (8.9) fournit une équation différentielle linéaire du second ordre (comme
l’équation différentielle initiale) sur la transformée d’Euler V ∗ (z), équation qui fait
aussi intervenir r ∗ (z) :
z
d
dz
2
(1 − z) (V
∗ (z) − r
∗ (z))
+ 2
d zV
∗ (z) = 0.
357
Passons maintenant à la fonction génératrice V (z) :=
n v n z n . L’équation (8.8)
sur les v n se transpose sur V pour donner une équation différentielle linéaire
d’ordre 2, non homogène :
z(1 − z)y
+ (1 − 2z)y
−
2 d
1 − z
y = R(z),
(8.9)
où R s’exprime à partir de la fonction génératrice des coûts à la racine r(z) =
n r n z n :
R(z) =
d
dz
z(1 − z)
d
dz
r(z)
= z(1 − z)r
(z) + (1 − 2z)r
(z).
Dans certains cas, cette équation peut être résolue directement, ce qui donne
des résultats explicites sur les paramètres additifs considérés. Ainsi, Flajolet et
Hoshi [84] étudient l’occupation moyenne des pages dans un arbre quadrant de
recherche paginé, c’est-à-dire un arbre où la décomposition récursive est arrêtée dès
qu’un sous-arbre est de taille au plus b, b étant le nombre d’éléments (clés) qu’une
page mémoire peut contenir. Le péage à la racine r(τ ) qui apparaît alors conduit à
une fonction génératrice r(z) = 1/(1−z)−
0≤n≤b z n , et il est possible de résoudre
explicitement l’équation différentielle (8.9). Nous donnons plus de détails dans le
problème 8.10.
Transformée d’Euler et étude des v n Lorsque nous ne pouvons pas obtenir
directement d’information sur la fonction génératrice V (z) à partir de l’équation
différentielle (8.9), une méthode alternative consiste à passer par sa transformée
d’Euler. La transformée d’Euler d’une fonction f (z) =
n≥0 f n z n est définie (cf.
section B.3.4) par
f
∗ (z) =
1
1 − z
f
z
z − 1
.
(8.10)
Ses coefficients f ∗
n dans son développement en série formelle sont liés aux
coefficients initiaux f n par
f
∗
p =
0≤n≤p
(−1)
n
p
n
f n .
Dans notre contexte, la transformation d’Euler appliquée à l’équation différentielle (8.9) fournit une équation différentielle linéaire du second ordre (comme
l’équation différentielle initiale) sur la transformée d’Euler V ∗ (z), équation qui fait
aussi intervenir r ∗ (z) :
z
d
dz
2
(1 − z) (V
∗ (z) − r
∗ (z))
+ 2
d zV
∗ (z) = 0.