9.5 Applications algorithmiques
393
Dans l’algorithme prudent, chaque feuille contient entre m − 1 et 2m − 1 clés,
il y a m + 1 types et les vecteurs X n et Y n sont de dimension m + 1. La matrice de
remplacement du processus d’urne (Y n ) est de dimension m + 1 et vaut
r m =
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
−m (m + 1)
−(m + 1) (m + 2)
. . .
. . .
. . . 2m
m (m + 1)
−2m
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠
.
(9.15)
La figure 9.3 illustre la même insertion que dans la figure 3.6 de la section 1.2.6(c),
en tenant compte des différents types (ou couleurs) des feuilles.
Dans l’algorithme optimiste et pour un arbre-B de paramètre m − 1, les feuilles
contiennent entre m − 1 et 2m − 2 clés, il y a m types et les vecteurs X n et Y n sont
de dimension m. La matrice de remplacement de l’urne est de dimension m et vaut
R m =
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
−m (m + 1)
−(m + 1) (m + 2)
. . .
. . .
. . . 2m − 1
2m
−(2m − 1)
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠
.
(9.16)
Il s’agit d’une généralisation de la matrice d’urne des arbres 2–3 de la section
précédente. La figure 9.4 illustre la même insertion que dans la figure 3.7 de la
section 1.2.6(c), en tenant compte des différents types (ou couleurs) des feuilles.
Les arbres-B apparaissent ainsi, à l’instar des arbres m-aires de recherche,
comme un agréable champ d’application de tous les résultats disponibles sur les
urnes de Pólya à plus de 2 couleurs.
Fig. 9.3 Un exemple d’insertion dans un arbre-B pour l’algorithme prudent. Ici m = 2, les nœuds
contiennent entre 1 et 3 clés, il y a trois couleurs de nœuds : blanc, rose et rouge