8.1 Arbres m-aires de recherche
345
Des calculs plus lourds conduisent à l’asymptotique de la variance, et ils peuvent
être trouvés dans Mahmoud [172]. En outre, il apparaît une transition de phase
à m = 26 : il existe une loi limite gaussienne pour S n pour m ≤ 26 mais pas
pour m ≥ 27. Ce phénomène peut paraître mystérieux. Nous donnerons quelques
éclaircissements dans la section suivante.
La longueur de cheminement lci(T n ) d’un arbre m-aire de recherche est aussi un
paramètre additif, et la méthode précédente s’applique pour obtenir
E (lci(T n )) ∼
1
H m − 1
n log n.
Pour d’autres péages, par exemple pour le nombre de nœuds de type donné, les
détails sont plus lourds à exposer mais la même méthode permet d’obtenir un
équivalent de l’espérance, résultat du théorème 8.10 que nous montrerons par des
méthodes d’urnes de Pólya.
8.1.3 Etude dynamique des arbres m-aires de recherche
Nous établissons dans cette section comment l’étude de l’occupation des feuilles
d’un arbre m-aire de recherche se déduit de la dynamique de l’arbre entre les instants
n − 1 et n. Les résultats asymptotiques énoncés à la fin de cette section dans le
théorème 8.10 seront démontrés dans la section 9.5.1 du chapitre sur les urnes de
Pólya.
Dans un arbre m-aire de recherche, nous étudions le vecteur X n dit d’occupation
des feuilles défini ci-après, qui décrit les différents types de feuilles.
Définition 8.9 Pour tout entier i tel que 2 ≤ i ≤ m, un nœud interne d’un arbre
m-aire de recherche est dit de type i quand il contient exactement (i − 1) clés. Un
tel nœud détermine i intervalles. En particulier un nœud de type m contient (m − 1)
clés et il est plein. Celles des possibilités d’insertion qui correspondent à des enfants
de nœuds pleins sont appelées nœuds de type 1, ils ne contiennent pas de clé. Voir
la figure 8.4.
Pour i = 1, 2, . . . , m, posons 3
X
(i)
n = nombre de nœuds de type i dans T n−1 .
En comptant combien il y a de clés dans l’arbre T n−1 , nous obtenons une
première relation entre les X
(i)
n :
n − 1 =
m
i=1
(i − 1)X
(i)
n .
(8.6)
3 Nous regardons l’arbre à l’instant n − 1, et nous y insérons la n-ième clé.
345
Des calculs plus lourds conduisent à l’asymptotique de la variance, et ils peuvent
être trouvés dans Mahmoud [172]. En outre, il apparaît une transition de phase
à m = 26 : il existe une loi limite gaussienne pour S n pour m ≤ 26 mais pas
pour m ≥ 27. Ce phénomène peut paraître mystérieux. Nous donnerons quelques
éclaircissements dans la section suivante.
La longueur de cheminement lci(T n ) d’un arbre m-aire de recherche est aussi un
paramètre additif, et la méthode précédente s’applique pour obtenir
E (lci(T n )) ∼
1
H m − 1
n log n.
Pour d’autres péages, par exemple pour le nombre de nœuds de type donné, les
détails sont plus lourds à exposer mais la même méthode permet d’obtenir un
équivalent de l’espérance, résultat du théorème 8.10 que nous montrerons par des
méthodes d’urnes de Pólya.
8.1.3 Etude dynamique des arbres m-aires de recherche
Nous établissons dans cette section comment l’étude de l’occupation des feuilles
d’un arbre m-aire de recherche se déduit de la dynamique de l’arbre entre les instants
n − 1 et n. Les résultats asymptotiques énoncés à la fin de cette section dans le
théorème 8.10 seront démontrés dans la section 9.5.1 du chapitre sur les urnes de
Pólya.
Dans un arbre m-aire de recherche, nous étudions le vecteur X n dit d’occupation
des feuilles défini ci-après, qui décrit les différents types de feuilles.
Définition 8.9 Pour tout entier i tel que 2 ≤ i ≤ m, un nœud interne d’un arbre
m-aire de recherche est dit de type i quand il contient exactement (i − 1) clés. Un
tel nœud détermine i intervalles. En particulier un nœud de type m contient (m − 1)
clés et il est plein. Celles des possibilités d’insertion qui correspondent à des enfants
de nœuds pleins sont appelées nœuds de type 1, ils ne contiennent pas de clé. Voir
la figure 8.4.
Pour i = 1, 2, . . . , m, posons 3
X
(i)
n = nombre de nœuds de type i dans T n−1 .
En comptant combien il y a de clés dans l’arbre T n−1 , nous obtenons une
première relation entre les X
(i)
n :
n − 1 =
m
i=1
(i − 1)X
(i)
n .
(8.6)
3 Nous regardons l’arbre à l’instant n − 1, et nous y insérons la n-ième clé.