74
3 Arbres, algorithmes et données
Fig. 3.12 Numérotation des
quarts de plan dans le cas
d = 2
verrons en section 8.2 un modèle probabiliste où les clés sont prises dans [0, 1] d , et
pour lequel les clés sont presque sûrement toutes distinctes.
La recherche, ou l’insertion, de la clé Y dans un arbre quadrant dont la racine
contient une clé X = Y se fera donc récursivement dans le sous-arbre τ (w) , où w
est l’entier dont l’écriture binaire est w X (Y ).
Par exemple, le cas d = 2 conduit à la numérotation des quarts de plan (et des
sous-arbres qui leur correspondent) donnée dans la figure 3.12.
Construction algorithmique : insertion aux feuilles Nous pouvons maintenant
comprendre la construction d’un arbre quadrant par une suite d’insertions aux
feuilles dans un arbre initialement vide : la première clé X est mise à la racine,
et chaque clé ultérieure Y est assignée à celui des 2 d sous-arbres de la racine qui
correspond à w X (Y ). Ces sous-arbres sont construits récursivement par insertions
successives.
Ainsi, l’arbre quadrant de notre exemple a été construit par les insertions
successives des clés X (1) = (0,4; 0,3), X (2) = (0,2; 0,7), X (3) = (0,9; 0,8),
X (4) = (0,5; 0,1), X (5) = (0,25; 0,4), X (6) = (0,6; 0,75). Ceci se reflète aussi
dans le découpage du domaine [0, 1] 2 , tel que donné dans la figure 3.11. D’autres
ordres d’insertion auraient conduit à la même structuration du domaine, par exemple
X (1) , X (3) , X (4) , X (2) , X (5) , X (6) ; par contre l’ordre X (3) , X (1) , X (4) , X (2) , X (5) ,
X (6) , par exemple, conduit à une structuration différente.
Recherche d’une clé Regardons sur l’arbre de la figure 3.10 comment se fait une
recherche multidimensionnelle, par exemple celle de la clé X = (0,6 ; 0,75). La
racine de l’arbre quadrant contient la clé X (1) = (0,4 ; 0,3) ; nous voyons que 10
X 1 > X
(1)
1 et X 2 > X
(1)
2 ; nous poursuivons donc la recherche dans le quatrième
enfant de la racine. Ce sous-arbre a pour racine la clé X (3) = (0,9 ; 0,8), et nous
voyons que X 1 < X
(3)
1 et X 2 < X
(3)
2 ; nous allons donc dans le premier enfant du
quatrième sous-arbre, où nous trouvons à la racine la clé cherchée.
Si nous cherchons maintenant la clé (0,5 ; 0,4), le même raisonnement nous
conduit à visiter le quatrième sous-arbre de l’arbre global, puis à poursuivre
la recherche dans le premier sous-arbre de celui-ci. Mais nous devons ensuite
poursuivre la recherche dans le premier sous-arbre de l’arbre de racine X (6) , qui
est vide : nous savons maintenant que la clé (0,5 ; 0,4) ne se trouve pas dans l’arbre,
10 Pour un vecteur X de dimension d, nous notons X 1 , X 2 , . . . , X d ses coordonnées.
3 Arbres, algorithmes et données
Fig. 3.12 Numérotation des
quarts de plan dans le cas
d = 2
verrons en section 8.2 un modèle probabiliste où les clés sont prises dans [0, 1] d , et
pour lequel les clés sont presque sûrement toutes distinctes.
La recherche, ou l’insertion, de la clé Y dans un arbre quadrant dont la racine
contient une clé X = Y se fera donc récursivement dans le sous-arbre τ (w) , où w
est l’entier dont l’écriture binaire est w X (Y ).
Par exemple, le cas d = 2 conduit à la numérotation des quarts de plan (et des
sous-arbres qui leur correspondent) donnée dans la figure 3.12.
Construction algorithmique : insertion aux feuilles Nous pouvons maintenant
comprendre la construction d’un arbre quadrant par une suite d’insertions aux
feuilles dans un arbre initialement vide : la première clé X est mise à la racine,
et chaque clé ultérieure Y est assignée à celui des 2 d sous-arbres de la racine qui
correspond à w X (Y ). Ces sous-arbres sont construits récursivement par insertions
successives.
Ainsi, l’arbre quadrant de notre exemple a été construit par les insertions
successives des clés X (1) = (0,4; 0,3), X (2) = (0,2; 0,7), X (3) = (0,9; 0,8),
X (4) = (0,5; 0,1), X (5) = (0,25; 0,4), X (6) = (0,6; 0,75). Ceci se reflète aussi
dans le découpage du domaine [0, 1] 2 , tel que donné dans la figure 3.11. D’autres
ordres d’insertion auraient conduit à la même structuration du domaine, par exemple
X (1) , X (3) , X (4) , X (2) , X (5) , X (6) ; par contre l’ordre X (3) , X (1) , X (4) , X (2) , X (5) ,
X (6) , par exemple, conduit à une structuration différente.
Recherche d’une clé Regardons sur l’arbre de la figure 3.10 comment se fait une
recherche multidimensionnelle, par exemple celle de la clé X = (0,6 ; 0,75). La
racine de l’arbre quadrant contient la clé X (1) = (0,4 ; 0,3) ; nous voyons que 10
X 1 > X
(1)
1 et X 2 > X
(1)
2 ; nous poursuivons donc la recherche dans le quatrième
enfant de la racine. Ce sous-arbre a pour racine la clé X (3) = (0,9 ; 0,8), et nous
voyons que X 1 < X
(3)
1 et X 2 < X
(3)
2 ; nous allons donc dans le premier enfant du
quatrième sous-arbre, où nous trouvons à la racine la clé cherchée.
Si nous cherchons maintenant la clé (0,5 ; 0,4), le même raisonnement nous
conduit à visiter le quatrième sous-arbre de l’arbre global, puis à poursuivre
la recherche dans le premier sous-arbre de celui-ci. Mais nous devons ensuite
poursuivre la recherche dans le premier sous-arbre de l’arbre de racine X (6) , qui
est vide : nous savons maintenant que la clé (0,5 ; 0,4) ne se trouve pas dans l’arbre,
10 Pour un vecteur X de dimension d, nous notons X 1 , X 2 , . . . , X d ses coordonnées.