8.1 Arbres m-aires de recherche
339
Fig. 8.1 Un arbre m-aire
(m = 3) complet avec 8
feuilles, 4 nœuds internes
dont 2 terminaux en vert (l’un
d’eux a m enfants, l’autre
m − 1 enfants), et 2 nœuds
internes non terminaux à m
enfants
Considérons un arbre m-aire de recherche, complété pour indiquer les possibilités d’insertion. Lorsqu’un nœud est d’arité p, ce nœud contient (est marqué par)
exactement p − 1 clés. De plus, tout nœud interne non terminal contient exactement
m − 1 clés, qui déterminent m intervalles correspondant à m sous-arbres, et les
clés du j -ième sous-arbre appartiennent au j -ième intervalle ; si un sous-arbre est
vide, c’est qu’aucune clé n’appartient à cet intervalle. De manière analogue, tout
nœud interne terminal contenant p clés a p + 1 sous-arbres qui sont des possibilités
d’insertion et ne contiennent pas de clé. Les sous-arbres de tout nœud interne
(terminal ou non) sont eux-mêmes des arbres m-aires de recherche, et la définition
récursive suivante est équivalente à la définition 8.4.
Définition 8.5 (récursive) Un arbre m-aire de recherche est soit réduit à une racine
contenant entre 0 et m − 2 clés, soit un arbre m-aire marqué dont la racine contient
des clés x 1 , x 2 , . . . , x m−1 et tel que les clés restantes sont réparties dans les m
intervalles définis par le réordonnement de x 1 , x 2 , . . . , x m−1 , de sorte que les m
sous-arbres de la racine sont encore des arbres m-aires de recherche.
Comme pour les arbres binaires de recherche, il existe un marquage canonique
des arbres m-aires de recherche (cf. la définition 1.16).
Construction algorithmique (insertion aux feuilles)
– Les m − 1 premières clés x 1 , . . . , x m−1 sont insérées à la racine de l’arbre.
– Appelons σ le réordonnement de x 1 , . . . , x m−1 . Les m − 1 clés réordonnées
définissent m intervalles de , de gauche à droite en ordre croissant : I 1 =
{x : x ≤ x σ (1) }, I j +1 = {x : x σ (j) < x ≤ x σ (j+1) } pour 1 ≤ j ≤ m − 2,
I m = {x : x > x σ (m−1) }. Le j -ième intervalle correspond au j -ième sous-arbre 1
de la racine.
– Chacune des clés suivantes x m , . . . , est insérée dans le sous-arbre correspondant
à l’unique intervalle I j qui contient cette clé.
1 S’il existe des clés répétées, certains sous-arbres sont vides ; les intervalles correspondants sont
vides.
339
Fig. 8.1 Un arbre m-aire
(m = 3) complet avec 8
feuilles, 4 nœuds internes
dont 2 terminaux en vert (l’un
d’eux a m enfants, l’autre
m − 1 enfants), et 2 nœuds
internes non terminaux à m
enfants
Considérons un arbre m-aire de recherche, complété pour indiquer les possibilités d’insertion. Lorsqu’un nœud est d’arité p, ce nœud contient (est marqué par)
exactement p − 1 clés. De plus, tout nœud interne non terminal contient exactement
m − 1 clés, qui déterminent m intervalles correspondant à m sous-arbres, et les
clés du j -ième sous-arbre appartiennent au j -ième intervalle ; si un sous-arbre est
vide, c’est qu’aucune clé n’appartient à cet intervalle. De manière analogue, tout
nœud interne terminal contenant p clés a p + 1 sous-arbres qui sont des possibilités
d’insertion et ne contiennent pas de clé. Les sous-arbres de tout nœud interne
(terminal ou non) sont eux-mêmes des arbres m-aires de recherche, et la définition
récursive suivante est équivalente à la définition 8.4.
Définition 8.5 (récursive) Un arbre m-aire de recherche est soit réduit à une racine
contenant entre 0 et m − 2 clés, soit un arbre m-aire marqué dont la racine contient
des clés x 1 , x 2 , . . . , x m−1 et tel que les clés restantes sont réparties dans les m
intervalles définis par le réordonnement de x 1 , x 2 , . . . , x m−1 , de sorte que les m
sous-arbres de la racine sont encore des arbres m-aires de recherche.
Comme pour les arbres binaires de recherche, il existe un marquage canonique
des arbres m-aires de recherche (cf. la définition 1.16).
Construction algorithmique (insertion aux feuilles)
– Les m − 1 premières clés x 1 , . . . , x m−1 sont insérées à la racine de l’arbre.
– Appelons σ le réordonnement de x 1 , . . . , x m−1 . Les m − 1 clés réordonnées
définissent m intervalles de , de gauche à droite en ordre croissant : I 1 =
{x : x ≤ x σ (1) }, I j +1 = {x : x σ (j) < x ≤ x σ (j+1) } pour 1 ≤ j ≤ m − 2,
I m = {x : x > x σ (m−1) }. Le j -ième intervalle correspond au j -ième sous-arbre 1
de la racine.
– Chacune des clés suivantes x m , . . . , est insérée dans le sous-arbre correspondant
à l’unique intervalle I j qui contient cette clé.
1 S’il existe des clés répétées, certains sous-arbres sont vides ; les intervalles correspondants sont
vides.