394
9 Urnes de Pólya et applications
Fig. 9.4 Un exemple d’insertion dans un arbre-B pour l’algorithme optimiste. Ici m = 3, m−1 =
2 et les nœuds internes contiennent entre 2 et 4 clés
Il y a des points communs entre arbres-B et arbres m-aires de recherche :
l’urne correspond à la dynamique des intervalles d’insertion ou gaps et non pas
à la dynamique des nœuds de l’arbre ; les matrices de remplacement de l’urne et
les polynômes caractéristiques sont proches. Pour un arbre-B, si à l’instant 0, T 0
contient m − 1 clés à la racine, alors à l’instant n, les feuilles de T n possèdent
n + m intervalles d’insertion. Pour un arbre m-aire de recherche, si à l’instant 0, T 0
ne contient aucune clé, alors à l’instant n, T n contient n clés et les feuilles de T n
possèdent n + 1 intervalles d’insertion.
Il y a néanmoins des différences importantes entre arbres-B et arbres m-aires
de recherche : la différence principale est que les feuilles des arbres-B sont toutes
au même niveau. De plus, les nœuds internes non terminaux des arbres m-aires de
recherche sont tous saturés, pas ceux des arbres-B ; l’arité des nœuds internes non
terminaux d’un arbre m-aire de recherche est m, alors qu’elle varie pour un arbre-B.
Nous donnons ci-après quelques résultats simples et spectaculaires pour les
arbres-B, d’autres plus détaillés se trouvent dans [43]. Nous donnons les résultats
pour l’algorithme optimiste, car ils sont un peu plus simples, plutôt que pour
l’algorithme prudent (voir exercices 9.6 et 9.8).
Petits et grands arbres-B
Il y a des coefficients négatifs sur la diagonale de R m :
R m =
⎛
⎜
⎜
⎜
⎜
⎜
⎜
⎝
−m (m + 1)
−(m + 1) (m + 2)
. . .
. . .
. . . 2m − 1
2m
−(2m − 1)
⎞
⎟
⎟
⎟
⎟
⎟
⎟
⎠
.