346
8 Arbres m-aires et quadrants
Fig. 8.4 Un arbre m-aire (m = 3) de recherche de taille n − 1 = 7, avec 8 possibilités d’insertion,
3 nœuds pleins, donc X
(3)
n
= 3, un nœud interne terminal de type 2 contenant une clé, donc
X
(2)
n = 1 et 6 possibilités d’insertion (« gaps » de couleur rose) issues de nœuds pleins, donc
X
(1)
n = 6. Il y a 2 nœuds internes terminaux en vert, l’un de type 3 et l’autre de type 2
Grâce à cette relation, n’importe laquelle des variables X
(i)
n , pour i allant de 1 à m,
s’exprime en fonction des m−1 autres. Nous pouvons donc considérer l’évolution de
seulement m − 1 variables X
(i)
n et non pas m. Nous choisissons de ne pas compter
les nœuds pleins, et donc d’étudier le vecteur de R m−1 (qui peut être vu quand
nécessaire comme un vecteur de C m−1 )
X n =
X
(1)
n , X
(2)
n , . . . , X
(m−1)
n
,
ou plutôt la suite (X n ) n≥1 . Les (m + 1) premiers vecteurs sont déterministes :
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
X 1 = (1, 0, . . . , 0)
X 2 = (0, 1, . . . , 0)
. . .
X m−1 = (0, . . . , 0, 1)
X m = (m, 0, . . . , 0)
X m+1 = (m − 1, 1, 0, . . . )
et les suivants sont aléatoires. Par exemple, X m+2 = (m − 2, 2, 0, . . . ) avec
probabilité
m−1
m+1 , et X m+2 = (m − 1, 0, 1, 0, . . . ) avec probabilité
2
m+1 . À cause du
modèle choisi pour l’aléa (clés indépendantes et de même loi autrement dit modèle
des permutations uniformes), l’arbre pousse de T n−1 à T n par insertion uniforme
d’une clé sur les n intervalles vacants.
Par exemple, sur la figure 8.4, la huitième clé est insérée uniformément sur l’une
des 8 possibilités ; avec probabilité 6/8, elle est insérée sur un nœud de type 1
(« gap » de couleur rose) et avec probabilité 2/8 elle est insérée sur un « gap » de
couleur blanche, de sorte qu’elle remplit le nœud correspondant, qui passe de type
2 à type 3 plein et produit donc deux nœuds de type 1.
8 Arbres m-aires et quadrants
Fig. 8.4 Un arbre m-aire (m = 3) de recherche de taille n − 1 = 7, avec 8 possibilités d’insertion,
3 nœuds pleins, donc X
(3)
n
= 3, un nœud interne terminal de type 2 contenant une clé, donc
X
(2)
n = 1 et 6 possibilités d’insertion (« gaps » de couleur rose) issues de nœuds pleins, donc
X
(1)
n = 6. Il y a 2 nœuds internes terminaux en vert, l’un de type 3 et l’autre de type 2
Grâce à cette relation, n’importe laquelle des variables X
(i)
n , pour i allant de 1 à m,
s’exprime en fonction des m−1 autres. Nous pouvons donc considérer l’évolution de
seulement m − 1 variables X
(i)
n et non pas m. Nous choisissons de ne pas compter
les nœuds pleins, et donc d’étudier le vecteur de R m−1 (qui peut être vu quand
nécessaire comme un vecteur de C m−1 )
X n =
X
(1)
n , X
(2)
n , . . . , X
(m−1)
n
,
ou plutôt la suite (X n ) n≥1 . Les (m + 1) premiers vecteurs sont déterministes :
⎧
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨
⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩
X 1 = (1, 0, . . . , 0)
X 2 = (0, 1, . . . , 0)
. . .
X m−1 = (0, . . . , 0, 1)
X m = (m, 0, . . . , 0)
X m+1 = (m − 1, 1, 0, . . . )
et les suivants sont aléatoires. Par exemple, X m+2 = (m − 2, 2, 0, . . . ) avec
probabilité
m−1
m+1 , et X m+2 = (m − 1, 0, 1, 0, . . . ) avec probabilité
2
m+1 . À cause du
modèle choisi pour l’aléa (clés indépendantes et de même loi autrement dit modèle
des permutations uniformes), l’arbre pousse de T n−1 à T n par insertion uniforme
d’une clé sur les n intervalles vacants.
Par exemple, sur la figure 8.4, la huitième clé est insérée uniformément sur l’une
des 8 possibilités ; avec probabilité 6/8, elle est insérée sur un nœud de type 1
(« gap » de couleur rose) et avec probabilité 2/8 elle est insérée sur un « gap » de
couleur blanche, de sorte qu’elle remplit le nœud correspondant, qui passe de type
2 à type 3 plein et produit donc deux nœuds de type 1.