338
8 Arbres m-aires et quadrants
anglais « forward ») est dynamique, consistant à observer comment l’arbre pousse
entre deux instants successifs.
8.1.1 Définitions des arbres m-aires de recherche
Afin de mieux distinguer ce qui relève des contraintes de forme et ce qui est relatif
aux clés contenues dans les nœuds, il nous a semblé pertinent de définir les arbres
m-aires d’abord en tant que formes d’arbres, indépendamment des marques, et de
donner dans un deuxième temps seulement la définition usuelle en tant qu’arbres de
recherche marqués.
Définition 8.1 Soit m ≥ 2 un entier. La classe combinatoire M des arbres m-aires
complets (en anglais extended) est construite à partir de deux classes combinatoires
atomiques • et (nœuds internes et externes) et vérifie l’équation récursive
M = +
m−1
p=2
• ×
p
+
• × M
m
.
La classe combinatoire M des arbres m-aires est construite à partir d’une classe
neutre notée E contenant un objet de taille 0, l’arbre vide, et d’une classe
combinatoire atomique contenant un objet de taille 1, noté ◦ et appelé « nœud »
de l’arbre, et vérifie l’équation récursive
M = E +
◦ × M
m
.
Dans un arbre m-aire complet, qui est un arbre planaire, les nœuds internes ont entre
2 et m enfants, tout nœud interne non terminal a exactement m enfants, et il y a m−1
types de nœuds internes terminaux, selon leur nombre d’enfants, qui varie de 2 à m.
Rappelons (cf. la définition 1.3) qu’un nœud interne terminal est un nœud interne
n’ayant que des feuilles comme enfants (figure 8.1).
Remarque 8.2 Un arbre m-aire pour m = 2 est un arbre binaire. Un arbre m-aire
complet pour m = 2 est un arbre binaire complet (cf. la section 1.1.2).
Remarque 8.3 Un arbre m-aire pour m = 3 n’est en général pas un arbre 2–3 :
d’une part, les nœuds internes non terminaux d’un arbre m-aire sont d’arité 3, ceux
d’un arbre 2–3 peuvent être d’arité 2 ou 3 ; d’autre part les feuilles d’un arbre 2–3
sont toutes au même niveau, alors que celles d’un arbre m-aire peuvent avoir des
niveaux différents.
Définition 8.4 Soit m un entier, m ≥ 2. Un arbre m-aire de recherche est un arbre
de recherche (cf. la définition 1.34) dont la forme est un arbre m-aire complet (cf. la
définition 8.1).
8 Arbres m-aires et quadrants
anglais « forward ») est dynamique, consistant à observer comment l’arbre pousse
entre deux instants successifs.
8.1.1 Définitions des arbres m-aires de recherche
Afin de mieux distinguer ce qui relève des contraintes de forme et ce qui est relatif
aux clés contenues dans les nœuds, il nous a semblé pertinent de définir les arbres
m-aires d’abord en tant que formes d’arbres, indépendamment des marques, et de
donner dans un deuxième temps seulement la définition usuelle en tant qu’arbres de
recherche marqués.
Définition 8.1 Soit m ≥ 2 un entier. La classe combinatoire M des arbres m-aires
complets (en anglais extended) est construite à partir de deux classes combinatoires
atomiques • et (nœuds internes et externes) et vérifie l’équation récursive
M = +
m−1
p=2
• ×
p
+
• × M
m
.
La classe combinatoire M des arbres m-aires est construite à partir d’une classe
neutre notée E contenant un objet de taille 0, l’arbre vide, et d’une classe
combinatoire atomique contenant un objet de taille 1, noté ◦ et appelé « nœud »
de l’arbre, et vérifie l’équation récursive
M = E +
◦ × M
m
.
Dans un arbre m-aire complet, qui est un arbre planaire, les nœuds internes ont entre
2 et m enfants, tout nœud interne non terminal a exactement m enfants, et il y a m−1
types de nœuds internes terminaux, selon leur nombre d’enfants, qui varie de 2 à m.
Rappelons (cf. la définition 1.3) qu’un nœud interne terminal est un nœud interne
n’ayant que des feuilles comme enfants (figure 8.1).
Remarque 8.2 Un arbre m-aire pour m = 2 est un arbre binaire. Un arbre m-aire
complet pour m = 2 est un arbre binaire complet (cf. la section 1.1.2).
Remarque 8.3 Un arbre m-aire pour m = 3 n’est en général pas un arbre 2–3 :
d’une part, les nœuds internes non terminaux d’un arbre m-aire sont d’arité 3, ceux
d’un arbre 2–3 peuvent être d’arité 2 ou 3 ; d’autre part les feuilles d’un arbre 2–3
sont toutes au même niveau, alors que celles d’un arbre m-aire peuvent avoir des
niveaux différents.
Définition 8.4 Soit m un entier, m ≥ 2. Un arbre m-aire de recherche est un arbre
de recherche (cf. la définition 1.34) dont la forme est un arbre m-aire complet (cf. la
définition 8.1).