8.2 Arbres quadrants de recherche
349
8.2 Arbres quadrants de recherche
Pour faciliter la lecture, la figure 8.5 ci-dessous rappelle la figure 3.10 d’un exemple
d’arbre quadrant complété.
8.2.1 Dénombrement des arbres quadrants
Nous commençons par un résultat relatif au dénombrement des arbres quadrants
complets, i.e., des arbres dont tous les nœuds internes ont exactement 2 d enfants,
(cf. la définition 3.4). Ces arbres non étiquetés jouent envers les arbres quadrants de
recherche le même rôle que les arbres binaires complets envers les arbres binaires
de recherche.
Proposition 8.11 Le nombre d’arbres quadrants complets sur n clés est
2 d n
n
(2 d − 1)n + 1
.
La preuve est simple, nous ne la détaillons pas. Pour d = 1, nous retrouvons bien
les nombres de Catalan :
(
2n
n )
(n+1) .
8.2.2 Aléa sur les arbres quadrants de recherche
Passons à la version étiquetée. Rappelons que, à la différence des autres exemples
d’utilisation de structures arborescentes marquées, nous considérons ici des clés
Fig. 8.5 Un arbre quadrant de paramètre d = 2 et construit sur 6 clés, complété avec les 19
feuilles ou possibilités d’insertion