Chapitre 8
Arbres m-aires et quadrants
Nous présentons ici les analyses de deux types d’arbres de recherche, chacun étant
une extension des arbres binaires de recherche
– soit avec des nœuds pouvant contenir plusieurs clés, ce sont les arbres m-aires de
recherche ;
– soit avec des clés multi-dimensionnelles, ce sont les arbres quadrants qui ont été
définis dans la section 3.2.2.b.
L’étude des arbres m-aires est entamée dans la section 8.1, en s’intéressant
d’abord au nombre de nœuds internes à l’aide de fonctions génératrices. Puis
nous étudions le vecteur d’occupation des feuilles, grâce à une modélisation par
chaîne de Markov dont l’analyse fait intervenir une urne de Pólya. Cette analyse est
faite dans la section 9.5.1 du chapitre 9, consacré justement aux urnes de Pólya.
Les arbres quadrants sont quant à eux étudiés dans la section 8.2 ; nous nous
intéressons successivement aux paramètres additifs, pour lesquels il est possible de
dégager, sinon des résultats généraux, du moins une méthodologie générale, puis à
la profondeur d’insertion d’une clé, à la hauteur de l’arbre, et finalement à son profil
(via un polynôme des niveaux). Le cas bi-dimensionnel (d = 2) conduit souvent à
des résultats plus détaillés que le cas général, et nous les explicitons dans la mesure
du possible.
8.1 Arbres m-aires de recherche
Après avoir défini ces arbres dans la section 8.1.1, nous proposons deux types
d’analyse de ces arbres : une analyse « historique », par séries génératrices, qui
se trouve dans le livre de Mahmoud [172] et qui est basée sur un raisonnement
(dit en anglais « backward ») de type « diviser pour régner » effectué à la racine
de l’arbre, déjà vu pour les arbres binaires de recherche ; l’autre analyse (dite en
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_8
337
Arbres m-aires et quadrants
Nous présentons ici les analyses de deux types d’arbres de recherche, chacun étant
une extension des arbres binaires de recherche
– soit avec des nœuds pouvant contenir plusieurs clés, ce sont les arbres m-aires de
recherche ;
– soit avec des clés multi-dimensionnelles, ce sont les arbres quadrants qui ont été
définis dans la section 3.2.2.b.
L’étude des arbres m-aires est entamée dans la section 8.1, en s’intéressant
d’abord au nombre de nœuds internes à l’aide de fonctions génératrices. Puis
nous étudions le vecteur d’occupation des feuilles, grâce à une modélisation par
chaîne de Markov dont l’analyse fait intervenir une urne de Pólya. Cette analyse est
faite dans la section 9.5.1 du chapitre 9, consacré justement aux urnes de Pólya.
Les arbres quadrants sont quant à eux étudiés dans la section 8.2 ; nous nous
intéressons successivement aux paramètres additifs, pour lesquels il est possible de
dégager, sinon des résultats généraux, du moins une méthodologie générale, puis à
la profondeur d’insertion d’une clé, à la hauteur de l’arbre, et finalement à son profil
(via un polynôme des niveaux). Le cas bi-dimensionnel (d = 2) conduit souvent à
des résultats plus détaillés que le cas général, et nous les explicitons dans la mesure
du possible.
8.1 Arbres m-aires de recherche
Après avoir défini ces arbres dans la section 8.1.1, nous proposons deux types
d’analyse de ces arbres : une analyse « historique », par séries génératrices, qui
se trouve dans le livre de Mahmoud [172] et qui est basée sur un raisonnement
(dit en anglais « backward ») de type « diviser pour régner » effectué à la racine
de l’arbre, déjà vu pour les arbres binaires de recherche ; l’autre analyse (dite en
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_8
337