344
8 Arbres m-aires et quadrants
Fig. 8.3 Racines de l’équation caractéristique (8.5) pour m = 22
La solution générale G 1 s’écrit finalement
G 1 (x) = sol particulière +
m−1
i=1
α i
(1 − x) 1+λ i
où les α i sont des coefficients que nous déterminons en connaissant les premiers
termes de la série.
Application à la taille d’un arbre m-aire de recherche
Prenons comme variable additive S n le nombre de nœuds internes d’un arbre maire de recherche de taille n. Dans ce cas, le péage à la racine est c = 1. Alors les
α j se calculent en notant que S n = 1 pour tout n ≤ m − 1. La fonction G 1 (x) =
−
1
(m − 1)(1 − x)
est solution particulière de l’équation
∂ m−1 y
∂x m−1 −
m!
(1 − x) m−1 y =
(m − 1)!
(1 − x) m ,
de sorte qu’après quelques calculs (détaillés dans Mahmoud [172, pp. 120–121]),
nous obtenons la proposition suivante.
Proposition 8.8 Sous le modèle des permutations uniformes, le nombre S n de
nœuds internes d’un arbre m-aire de recherche de taille n a pour moyenne
E(S n ) =
1
2(H m − 1)
n −
1
m − 1
+ O(n
σ ),
où σ est la plus grande partie réelle des racines différentes de 1 de l’équation
caractéristique (8.5), et H m est le nombre harmonique.