8.2 Arbres quadrants de recherche
369
profondeur , puis dans le théorème 8.20 la moyenne et la variance de la profondeur
d’insertion d(X, τ n ) d’une clé X dans un arbre quadrant à n clés τ n , toutes deux
d’ordre asymptotique en log n, et enfin, dans le corollaire 8.21, la convergence en
probabilité de la profondeur normalisée d(X, τ n )/ log n.
Nous avons ensuite considéré les polynômes de niveaux, qui décrivent le profil
de l’arbre, i.e., le nombre de feuilles à chaque niveau, toutes ces quantités étant
des variables aléatoires. Nous avons obtenu l’espérance de ce polynôme dans le
lemme 8.24, pour une valeur quelconque de d. Cela nous a permis d’en tirer une
expression de la fonction génératrice de probabilité de la profondeur d’insertion
(dans l’exercice 8.11), puis d’obtenir la convergence en distribution de la variable
normalisée (d(X, τ n ) − μ n )/ log n vers une loi Gaussienne dans le théorème 8.25.
Hauteur Nous avons d’abord donné un encadrement grossier, avec une borne
inférieure d’ordre logarithmique, puis montré (théorème 8.22) que cette borne
inférieure donne effectivement le bon ordre de grandeur, à défaut de la constante
exacte, et que la hauteur normalisée h(τ n )/ log n converge en probabilité.
Coûts des opérations sur les arbres quadrants de recherche Comme pour les
arbres binaires de recherche, nous pouvons distinguer les opérations d’insertion, de
recherche avec succès, et de recherche sans succès.
Le coût d’une recherche avec succès, lorsque nous supposons que nous accédons
avec équiprobabilité à chaque clé présente dans un arbre quadrant de recherche
construit sur n clés, est lié à sa longueur de cheminement : il est en moyenne
asymptotiquement équivalent à
2
d log n.
Le coût d’une recherche sans succès est le même que celui d’une insertion ; tous
deux sont déterminés par la profondeur d’insertion et suivent asymptotiquement une
loi Gaussienne dont la moyenne et la variance sont d’ordre asymptotique log n.
Le coût d’une opération dans un arbre quadrant de recherche est donc très
comparable à celui de la même opération dans un arbre binaire de recherche (qui ne
sont autres, rappelons-le, que des arbres quadrants pour d = 1) ; cf. la section 6.6.
À première vue, si les ordres sont les mêmes, les constantes sont divisées par d ;
nous pourrions donc penser que l’utilisation d’un arbre quadrant de recherche
divise par d le nombre de comparaisons lors de la recherche d’une clé. . . mais
une comparaison entre deux clés de dimension d requiert en fait d comparaisons
élémentaires sur les coordonnées. Si nous prenons en compte, non pas les seuls
nombres de comparaisons entre clés dans les arbres binaires de recherche et dans les
arbres quadrants de recherche, mais les coûts réels des comparaisons, nous voyons
que les coûts de recherche sont similaires.
Revenons enfin sur cette vision des arbres binaires de recherche comme cas
particulier des arbres quadrants de recherche : si les coûts algorithmiques sont très
semblables, il y a cependant des différences notables de comportement qui ne nous
ont pas permis de transposer les analyses mathématiques. Cela se voit par exemple
sur la loi de la taille du premier sous-arbre, qui est uniforme sur {0, 1, . . . , n − 1}
pour les arbres binaires de recherche, et cesse de l’être pour les arbres quadrants de
recherche dès que d ≥ 2.
369
profondeur , puis dans le théorème 8.20 la moyenne et la variance de la profondeur
d’insertion d(X, τ n ) d’une clé X dans un arbre quadrant à n clés τ n , toutes deux
d’ordre asymptotique en log n, et enfin, dans le corollaire 8.21, la convergence en
probabilité de la profondeur normalisée d(X, τ n )/ log n.
Nous avons ensuite considéré les polynômes de niveaux, qui décrivent le profil
de l’arbre, i.e., le nombre de feuilles à chaque niveau, toutes ces quantités étant
des variables aléatoires. Nous avons obtenu l’espérance de ce polynôme dans le
lemme 8.24, pour une valeur quelconque de d. Cela nous a permis d’en tirer une
expression de la fonction génératrice de probabilité de la profondeur d’insertion
(dans l’exercice 8.11), puis d’obtenir la convergence en distribution de la variable
normalisée (d(X, τ n ) − μ n )/ log n vers une loi Gaussienne dans le théorème 8.25.
Hauteur Nous avons d’abord donné un encadrement grossier, avec une borne
inférieure d’ordre logarithmique, puis montré (théorème 8.22) que cette borne
inférieure donne effectivement le bon ordre de grandeur, à défaut de la constante
exacte, et que la hauteur normalisée h(τ n )/ log n converge en probabilité.
Coûts des opérations sur les arbres quadrants de recherche Comme pour les
arbres binaires de recherche, nous pouvons distinguer les opérations d’insertion, de
recherche avec succès, et de recherche sans succès.
Le coût d’une recherche avec succès, lorsque nous supposons que nous accédons
avec équiprobabilité à chaque clé présente dans un arbre quadrant de recherche
construit sur n clés, est lié à sa longueur de cheminement : il est en moyenne
asymptotiquement équivalent à
2
d log n.
Le coût d’une recherche sans succès est le même que celui d’une insertion ; tous
deux sont déterminés par la profondeur d’insertion et suivent asymptotiquement une
loi Gaussienne dont la moyenne et la variance sont d’ordre asymptotique log n.
Le coût d’une opération dans un arbre quadrant de recherche est donc très
comparable à celui de la même opération dans un arbre binaire de recherche (qui ne
sont autres, rappelons-le, que des arbres quadrants pour d = 1) ; cf. la section 6.6.
À première vue, si les ordres sont les mêmes, les constantes sont divisées par d ;
nous pourrions donc penser que l’utilisation d’un arbre quadrant de recherche
divise par d le nombre de comparaisons lors de la recherche d’une clé. . . mais
une comparaison entre deux clés de dimension d requiert en fait d comparaisons
élémentaires sur les coordonnées. Si nous prenons en compte, non pas les seuls
nombres de comparaisons entre clés dans les arbres binaires de recherche et dans les
arbres quadrants de recherche, mais les coûts réels des comparaisons, nous voyons
que les coûts de recherche sont similaires.
Revenons enfin sur cette vision des arbres binaires de recherche comme cas
particulier des arbres quadrants de recherche : si les coûts algorithmiques sont très
semblables, il y a cependant des différences notables de comportement qui ne nous
ont pas permis de transposer les analyses mathématiques. Cela se voit par exemple
sur la loi de la taille du premier sous-arbre, qui est uniforme sur {0, 1, . . . , n − 1}
pour les arbres binaires de recherche, et cesse de l’être pour les arbres quadrants de
recherche dès que d ≥ 2.