3.2 Recherche de clés
73
Fig. 3.10 Un arbre quadrant
de paramètre d = 2 et
construit sur 6 clés
X (1) = (0,4 ; 0,3),
X (2) = (numprint0, 2 ; 0,7),
X (3) = (0,9 ; 0,8),
X (4) = (0,5 ; 0,1),
X (5) = (0,24 ; 0,4), et
X (6) = (0,6 ; 0,75). L’arbre
est complété avec les 19
possibilités d’insertion
Fig. 3.11 Structuration de
[0, 1] 2 induite par l’arbre de
la figure 3.10
sous-arbre de la racine, correspond à l’entier i − 1. Nous notons ces sous-arbres
τ (0) , . . . , τ (2 d −1) .
Définissons maintenant, 9 pour chaque clé X = (x 1 , x 2 , . . . , x d ), une fonction
w X : D → {0, 1} d qui associe à une clé Y = (y 1 , y 2 , . . . , y d ) un mot w X (Y ) =
b 1 b 2 . . . b d comme suit : pour i de 1 à n,
b i = 0 ⇔ y i < x i ,
b i = 1 ⇔ y i > x i .
Par exemple, si nous souhaitons insérer la clé Y = (0, 8 ; 0, 4) dans l’arbre de
la figure 3.10, de racine X = (0,4 ; 0,3), alors w X (Y ) = 11 ; si nous prenons
Y = (0,8 ; 0,2), alors w X (Y ) = 10.
Remarquons qu’il n’est possible de définir w X (Y ) que si X = Y . C’est le cas
lorsque nous supposons que les clés d’un arbre quadrant sont toutes distinctes ; nous
9 Par souci de lisibilité, nous notons les clés d-dimensionnelles avec des lettres majuscules, et les
composantes uni-dimensionnelles en minuscules.
73
Fig. 3.10 Un arbre quadrant
de paramètre d = 2 et
construit sur 6 clés
X (1) = (0,4 ; 0,3),
X (2) = (numprint0, 2 ; 0,7),
X (3) = (0,9 ; 0,8),
X (4) = (0,5 ; 0,1),
X (5) = (0,24 ; 0,4), et
X (6) = (0,6 ; 0,75). L’arbre
est complété avec les 19
possibilités d’insertion
Fig. 3.11 Structuration de
[0, 1] 2 induite par l’arbre de
la figure 3.10
sous-arbre de la racine, correspond à l’entier i − 1. Nous notons ces sous-arbres
τ (0) , . . . , τ (2 d −1) .
Définissons maintenant, 9 pour chaque clé X = (x 1 , x 2 , . . . , x d ), une fonction
w X : D → {0, 1} d qui associe à une clé Y = (y 1 , y 2 , . . . , y d ) un mot w X (Y ) =
b 1 b 2 . . . b d comme suit : pour i de 1 à n,
b i = 0 ⇔ y i < x i ,
b i = 1 ⇔ y i > x i .
Par exemple, si nous souhaitons insérer la clé Y = (0, 8 ; 0, 4) dans l’arbre de
la figure 3.10, de racine X = (0,4 ; 0,3), alors w X (Y ) = 11 ; si nous prenons
Y = (0,8 ; 0,2), alors w X (Y ) = 10.
Remarquons qu’il n’est possible de définir w X (Y ) que si X = Y . C’est le cas
lorsque nous supposons que les clés d’un arbre quadrant sont toutes distinctes ; nous
9 Par souci de lisibilité, nous notons les clés d-dimensionnelles avec des lettres majuscules, et les
composantes uni-dimensionnelles en minuscules.