340
8 Arbres m-aires et quadrants
Fig. 8.2 Un arbre m-aire de
recherche (m = 3) avec 7
clés, 4 nœuds dont 2
terminaux en vert, construit
avec la suite de données :
0,8 ; 0,5 ; 0,9 ; 0,4 ; 0,42 ; 0,83 ; 0,94.
L’arbre est complété avec les
8 possibilités d’insertion
– Quand un nœud est plein, c’est-à-dire contient le nombre maximum m−1 de clés
autorisé, m sous-arbres sont créés, réduits chacun à une possibilité d’insertion.
Ainsi, dans l’exemple de la figure 8.2, les clés 0,8 et 0,5 sont mises à la racine,
définissant trois intervalles et donc trois sous-arbres correspondant. Puis la clé 0,9
est mise dans le nœud-enfant de droite, les clés 0,4 et 0,42 dans le nœud de gauche,
la clé 0,83 finit de remplir le nœud de droite, créant trois sous-arbres réduits à une
possibilité d’insertion. Enfin, la clé 0,94 va à droite de la racine, puis à droite de
l’enfant de droite pour aboutir dans un nœud-feuille.
L’intérêt algorithmique des arbres m-aires réside en un partage plus fin des clés
en m parties, les longueurs de cheminement sont plus courtes, et le nombre de nœuds
visités est réduit. Cependant, chaque opération sur un nœud devient plus complexe ;
par exemple la recherche d’une clé dans un nœud peut nécessiter jusqu’à m − 1
comparaisons de clés.
Le modèle probabiliste que nous avons défini sur les arbres binaires de recherche
s’étend naturellement aux autres types d’arbres de recherche, ici aux arbres m-aires
de recherche. L’insertion aux feuilles dans un tel arbre se fait sous le modèle des
permutations uniformes de la définition 2.4.
Aléa sur les arbres m-aires de recherche
Comme pour un arbre binaire de recherche, nous disposons d’une suite (x i ) i≥1 de
clés distinctes, à valeurs dans un domaine D. Quand nous les supposons être des
variables aléatoires (indépendantes et de même loi continue sur l’intervalle [0, 1]
par exemple), nous obtenons un arbre m-aire de recherche aléatoire.
Nous construisons une suite (T n ) d’arbres m-aires marqués, mais nous sommes
souvent intéressés uniquement par la forme de l’arbre, c’est-à-dire la suite d’arbres
m-aires (π(T n )) sans les clés contenues dans les nœuds, ou bien par la suite (C(T n ))
des arbres des rangs obtenus par marquage canonique de T n (voir la définition 1.16).
8 Arbres m-aires et quadrants
Fig. 8.2 Un arbre m-aire de
recherche (m = 3) avec 7
clés, 4 nœuds dont 2
terminaux en vert, construit
avec la suite de données :
0,8 ; 0,5 ; 0,9 ; 0,4 ; 0,42 ; 0,83 ; 0,94.
L’arbre est complété avec les
8 possibilités d’insertion
– Quand un nœud est plein, c’est-à-dire contient le nombre maximum m−1 de clés
autorisé, m sous-arbres sont créés, réduits chacun à une possibilité d’insertion.
Ainsi, dans l’exemple de la figure 8.2, les clés 0,8 et 0,5 sont mises à la racine,
définissant trois intervalles et donc trois sous-arbres correspondant. Puis la clé 0,9
est mise dans le nœud-enfant de droite, les clés 0,4 et 0,42 dans le nœud de gauche,
la clé 0,83 finit de remplir le nœud de droite, créant trois sous-arbres réduits à une
possibilité d’insertion. Enfin, la clé 0,94 va à droite de la racine, puis à droite de
l’enfant de droite pour aboutir dans un nœud-feuille.
L’intérêt algorithmique des arbres m-aires réside en un partage plus fin des clés
en m parties, les longueurs de cheminement sont plus courtes, et le nombre de nœuds
visités est réduit. Cependant, chaque opération sur un nœud devient plus complexe ;
par exemple la recherche d’une clé dans un nœud peut nécessiter jusqu’à m − 1
comparaisons de clés.
Le modèle probabiliste que nous avons défini sur les arbres binaires de recherche
s’étend naturellement aux autres types d’arbres de recherche, ici aux arbres m-aires
de recherche. L’insertion aux feuilles dans un tel arbre se fait sous le modèle des
permutations uniformes de la définition 2.4.
Aléa sur les arbres m-aires de recherche
Comme pour un arbre binaire de recherche, nous disposons d’une suite (x i ) i≥1 de
clés distinctes, à valeurs dans un domaine D. Quand nous les supposons être des
variables aléatoires (indépendantes et de même loi continue sur l’intervalle [0, 1]
par exemple), nous obtenons un arbre m-aire de recherche aléatoire.
Nous construisons une suite (T n ) d’arbres m-aires marqués, mais nous sommes
souvent intéressés uniquement par la forme de l’arbre, c’est-à-dire la suite d’arbres
m-aires (π(T n )) sans les clés contenues dans les nœuds, ou bien par la suite (C(T n ))
des arbres des rangs obtenus par marquage canonique de T n (voir la définition 1.16).