368
8 Arbres m-aires et quadrants
Il est possible d’étendre le raisonnement fait dans le cas d = 2 aux
valeurs supérieures : après l’établissement d’une équation différentielle, dont
la solution s’exprime à l’aide d’une fonction hypergéométrique, et obtention
pour la fonction bivariée d’une expression analogue à (8.17), une technique de
perturbation de la singularité termine l’analyse. Le théorème suivant montre
que la profondeur d’insertion suit asymptotiquement une loi normale, pour
tout d ≥ 3.
Théorème 8.25 Soient μ n = (2/d) log n et σ 2
n = (2/d 2 ) log n ; la
profondeur d’insertion dans un arbre quadrant de recherche normalisée
(d(X, τ n ) − μ n )/σ n converge en distribution vers une loi normale.
8.2.8 Synthèse des résultats et interprétation algorithmique
Reprenons ci-dessous les principaux résultats que nous avons obtenus, et voyons
quelles conséquences algorithmiques nous pouvons en tirer. Nous avons rappelé
en section 8.2.2 la loi de probabilité sur l’ensemble Q des arbres quadrants de
recherche, puis nous nous sommes intéressés à la loi induite sur les sous-arbres en
section 8.2.3. Nous avons ensuite présenté en section 8.2.4 une approche générale
des paramètres additifs, avant de passer à l’étude de la profondeur d’insertion d’une
clé sous deux angles complémentaires : combinatoire en section 8.2.5 (pour le cas
d = 2), et par les polynômes de niveau en section 8.2.7 ; enfin nous avons donné
des résultats sur la hauteur en section 8.2.6.
Lois des sous-arbres La loi de la taille d’un sous-arbre est donnée, dans le cas
d = 2, par la proposition 8.13, et par la proposition 8.15 dans le cas général. Ces
résultats, explicites dans le cas d = 2 et sous forme de somme finie ou d’intégrale
pour d ≥ 3, servent de base pour les études qui suivent, aussi bien pour les
paramètres additifs que pour la profondeur d’insertion.
Paramètres additifs Comme c’était déjà le cas pour les familles simples d’arbres
présentées en section 4.2, les paramètres additifs sur les arbres quadrants de
recherche se prêtent à une analyse systématique, cf. la section 8.2.4. Parmi ces
paramètres se trouve le nombre de nœuds d’arité donnée, en particulier le nombre
de feuilles. Dans le cas des arbres paginés, leur étude permet d’obtenir le taux de
remplissage des pages (cf. le problème 8.10). Un autre paramètre additif essentiel
est la longueur de cheminement, dont la moyenne est asymptotiquement équivalente
à
2
d n log n, cf. la proposition 8.16.
Profondeur d’insertion Nous avons d’abord étudié le cas d = 2, et obtenu dans un
premier temps (équation (8.12)) une expression pour la probabilité de l’insertion à
8 Arbres m-aires et quadrants
Il est possible d’étendre le raisonnement fait dans le cas d = 2 aux
valeurs supérieures : après l’établissement d’une équation différentielle, dont
la solution s’exprime à l’aide d’une fonction hypergéométrique, et obtention
pour la fonction bivariée d’une expression analogue à (8.17), une technique de
perturbation de la singularité termine l’analyse. Le théorème suivant montre
que la profondeur d’insertion suit asymptotiquement une loi normale, pour
tout d ≥ 3.
Théorème 8.25 Soient μ n = (2/d) log n et σ 2
n = (2/d 2 ) log n ; la
profondeur d’insertion dans un arbre quadrant de recherche normalisée
(d(X, τ n ) − μ n )/σ n converge en distribution vers une loi normale.
8.2.8 Synthèse des résultats et interprétation algorithmique
Reprenons ci-dessous les principaux résultats que nous avons obtenus, et voyons
quelles conséquences algorithmiques nous pouvons en tirer. Nous avons rappelé
en section 8.2.2 la loi de probabilité sur l’ensemble Q des arbres quadrants de
recherche, puis nous nous sommes intéressés à la loi induite sur les sous-arbres en
section 8.2.3. Nous avons ensuite présenté en section 8.2.4 une approche générale
des paramètres additifs, avant de passer à l’étude de la profondeur d’insertion d’une
clé sous deux angles complémentaires : combinatoire en section 8.2.5 (pour le cas
d = 2), et par les polynômes de niveau en section 8.2.7 ; enfin nous avons donné
des résultats sur la hauteur en section 8.2.6.
Lois des sous-arbres La loi de la taille d’un sous-arbre est donnée, dans le cas
d = 2, par la proposition 8.13, et par la proposition 8.15 dans le cas général. Ces
résultats, explicites dans le cas d = 2 et sous forme de somme finie ou d’intégrale
pour d ≥ 3, servent de base pour les études qui suivent, aussi bien pour les
paramètres additifs que pour la profondeur d’insertion.
Paramètres additifs Comme c’était déjà le cas pour les familles simples d’arbres
présentées en section 4.2, les paramètres additifs sur les arbres quadrants de
recherche se prêtent à une analyse systématique, cf. la section 8.2.4. Parmi ces
paramètres se trouve le nombre de nœuds d’arité donnée, en particulier le nombre
de feuilles. Dans le cas des arbres paginés, leur étude permet d’obtenir le taux de
remplissage des pages (cf. le problème 8.10). Un autre paramètre additif essentiel
est la longueur de cheminement, dont la moyenne est asymptotiquement équivalente
à
2
d n log n, cf. la proposition 8.16.
Profondeur d’insertion Nous avons d’abord étudié le cas d = 2, et obtenu dans un
premier temps (équation (8.12)) une expression pour la probabilité de l’insertion à