3.2 Recherche de clés
71
Fig. 3.8 Un arbre quadrant de paramètre d = 2, à 7 nœuds. Parmi les quatre enfants possibles
de la racine, le premier est absent de l’arbre ; les trois autres sont présents. L’enfant de la racine
portant le numéro 2 a lui-même deux enfants possibles parmi quatre : le deuxième et le troisième ;
l’enfant de la racine de numéro 3 est une feuille, et celui de numéro 4 a un seul enfant (le premier)
parmi quatre possibles
Cependant la réorganisation de l’arbre, pour assurer que les feuilles restent
toujours au même niveau, a un coût et complique bien évidemment l’analyse fine des
performances des arbres-B. Depuis le travail fondateur de Yao [254], il existe des
résultats partiels mais pas d’analogue aux résultats détaillés obtenus pour les arbres
binaires de recherche par exemple. Nous présentons en section 9.5.3 une approche
récente par urne de Pólya, qui permet d’obtenir des informations sur le remplissage
des nœuds les plus externes, par exemple sur la loi du nombre de nœuds les moins
(ou les plus) remplis ; cf. aussi [43].
Arbres quadrants
En tant que forme d’arbres, les arbres quadrants apparaissent comme une généralisation des arbres binaires et des arbres binaires complets ; l’intérêt algorithmique
est néanmoins dans les arbres quadrants de recherche décrits ensuite (figure 3.8).
Définition 3.4 Un arbre quadrant de paramètre d (d entier ≥ 1) est un arbre
préfixe dans lequel chaque nœud interne a au plus 2 d enfants.
Un arbre quadrant complet de paramètre d (d entier ≥ 1) est un arbre planaire
dans lequel chaque nœud interne a exactement 2 d enfants (figure 3.9).
Un arbre quadrant complet à n nœuds internes a (2 d − 1) n + 1 feuilles ; cela se
montre par récurrence sur n.
Arbres quadrants de recherche
Considérons maintenant des clés multi-dimensionnelles, i.e., des éléments d’un
domaine D de dimension d ≥ 2 fixée, 7 chacune des dimensions correspondant à
7 Nous appelons domaine un ensemble auquel appartiennent des clés. Un domaine est dit de
dimension d quand c’est un produit cartésien de d ensembles.
71
Fig. 3.8 Un arbre quadrant de paramètre d = 2, à 7 nœuds. Parmi les quatre enfants possibles
de la racine, le premier est absent de l’arbre ; les trois autres sont présents. L’enfant de la racine
portant le numéro 2 a lui-même deux enfants possibles parmi quatre : le deuxième et le troisième ;
l’enfant de la racine de numéro 3 est une feuille, et celui de numéro 4 a un seul enfant (le premier)
parmi quatre possibles
Cependant la réorganisation de l’arbre, pour assurer que les feuilles restent
toujours au même niveau, a un coût et complique bien évidemment l’analyse fine des
performances des arbres-B. Depuis le travail fondateur de Yao [254], il existe des
résultats partiels mais pas d’analogue aux résultats détaillés obtenus pour les arbres
binaires de recherche par exemple. Nous présentons en section 9.5.3 une approche
récente par urne de Pólya, qui permet d’obtenir des informations sur le remplissage
des nœuds les plus externes, par exemple sur la loi du nombre de nœuds les moins
(ou les plus) remplis ; cf. aussi [43].
Arbres quadrants
En tant que forme d’arbres, les arbres quadrants apparaissent comme une généralisation des arbres binaires et des arbres binaires complets ; l’intérêt algorithmique
est néanmoins dans les arbres quadrants de recherche décrits ensuite (figure 3.8).
Définition 3.4 Un arbre quadrant de paramètre d (d entier ≥ 1) est un arbre
préfixe dans lequel chaque nœud interne a au plus 2 d enfants.
Un arbre quadrant complet de paramètre d (d entier ≥ 1) est un arbre planaire
dans lequel chaque nœud interne a exactement 2 d enfants (figure 3.9).
Un arbre quadrant complet à n nœuds internes a (2 d − 1) n + 1 feuilles ; cela se
montre par récurrence sur n.
Arbres quadrants de recherche
Considérons maintenant des clés multi-dimensionnelles, i.e., des éléments d’un
domaine D de dimension d ≥ 2 fixée, 7 chacune des dimensions correspondant à
7 Nous appelons domaine un ensemble auquel appartiennent des clés. Un domaine est dit de
dimension d quand c’est un produit cartésien de d ensembles.