72
3 Arbres, algorithmes et données
Fig. 3.9 L’arbre quadrant de la figure 3.8, complété pour que chaque nœud interne ait exactement
4 enfants : il a maintenant 7 nœuds internes, chacun avec 4 enfants, et 22 feuilles
un ensemble totalement ordonné. 8 Comment pouvons-nous structurer un ensemble
de clés de D, de façon à pouvoir y effectuer des recherches et des mises à jour ?
Il est bien évidemment possible de définir un ordre total sur D, et de construire
un arbre binaire de recherche sur un ensemble de clés, mais nous pouvons aussi
chercher à exploiter la structure multi-dimensionnelle des clés afin d’obtenir des
algorithmes potentiellement plus performants. Ceci conduit par exemple à la notion
d’arbre quadrant de recherche, que nous définissons ci-dessous.
Définition 3.5 Soit un entier d ≥ 2. Un arbre quadrant de recherche de
paramètre d est un arbre de recherche dont les clés sont prises dans un domaine D de
dimension d et dont la forme est un arbre quadrant (cf. définition 3.4). L’ensemble
des arbres quadrants de recherche construits sur des clés d-dimensionnelles est
noté Q.
Chaque nœud de l’arbre contient exactement une clé qui subdivise récursivement le
domaine des clés en 2 d sous-espaces, et a au plus 2 d enfants, associés bijectivement
aux 2 d sous-espaces.
Division de l’espace et numérotation des sous-arbres Tout comme les clés d’un
arbre binaire de recherche structurent le domaine dans lequel sont pris les clés, par
exemple l’intervalle réel [0, 1], en le découpant en intervalles, les clés d’un arbre
quadrant structurent le domaine [0, 1] d : la première clé le partage en 2 d sousensembles, puis chaque nouvelle clé partage récursivement le sous-ensemble dans
lequel elle se trouve en 2 d nouveaux sous-ensembles. Ainsi, l’arbre de la figure 3.10
structure le carré [0, 1] 2 selon la partition de la figure 3.11.
Précisons ici la relation entre les sous-arbres d’un arbre dont la racine contient
une clé X et les sous-espaces définis par X dans [0, 1] d . Les 2 d mots de {0, 1} d
sont les écritures binaires des 2 d entiers 0, . . . , 2 d − 1, et le i-ième quadrant, ou
8 Par souci de simplicité, nous prendrons souvent D = [0, 1] d , en particulier lors des analyses du
chapitre 8.2, mais cela n’est en rien nécessaire.
3 Arbres, algorithmes et données
Fig. 3.9 L’arbre quadrant de la figure 3.8, complété pour que chaque nœud interne ait exactement
4 enfants : il a maintenant 7 nœuds internes, chacun avec 4 enfants, et 22 feuilles
un ensemble totalement ordonné. 8 Comment pouvons-nous structurer un ensemble
de clés de D, de façon à pouvoir y effectuer des recherches et des mises à jour ?
Il est bien évidemment possible de définir un ordre total sur D, et de construire
un arbre binaire de recherche sur un ensemble de clés, mais nous pouvons aussi
chercher à exploiter la structure multi-dimensionnelle des clés afin d’obtenir des
algorithmes potentiellement plus performants. Ceci conduit par exemple à la notion
d’arbre quadrant de recherche, que nous définissons ci-dessous.
Définition 3.5 Soit un entier d ≥ 2. Un arbre quadrant de recherche de
paramètre d est un arbre de recherche dont les clés sont prises dans un domaine D de
dimension d et dont la forme est un arbre quadrant (cf. définition 3.4). L’ensemble
des arbres quadrants de recherche construits sur des clés d-dimensionnelles est
noté Q.
Chaque nœud de l’arbre contient exactement une clé qui subdivise récursivement le
domaine des clés en 2 d sous-espaces, et a au plus 2 d enfants, associés bijectivement
aux 2 d sous-espaces.
Division de l’espace et numérotation des sous-arbres Tout comme les clés d’un
arbre binaire de recherche structurent le domaine dans lequel sont pris les clés, par
exemple l’intervalle réel [0, 1], en le découpant en intervalles, les clés d’un arbre
quadrant structurent le domaine [0, 1] d : la première clé le partage en 2 d sousensembles, puis chaque nouvelle clé partage récursivement le sous-ensemble dans
lequel elle se trouve en 2 d nouveaux sous-ensembles. Ainsi, l’arbre de la figure 3.10
structure le carré [0, 1] 2 selon la partition de la figure 3.11.
Précisons ici la relation entre les sous-arbres d’un arbre dont la racine contient
une clé X et les sous-espaces définis par X dans [0, 1] d . Les 2 d mots de {0, 1} d
sont les écritures binaires des 2 d entiers 0, . . . , 2 d − 1, et le i-ième quadrant, ou
8 Par souci de simplicité, nous prendrons souvent D = [0, 1] d , en particulier lors des analyses du
chapitre 8.2, mais cela n’est en rien nécessaire.