392
9 Urnes de Pólya et applications
où N(0, , 2 ) est un vecteur gaussien de moyenne nulle et de matrice de covariance
2 , avec
2
=
432
637
1 −1
−1 1
.
9.5.3 Arbres-B
Arbres-B et urnes de Pólya
Soit m ≥ 2 un entier. Rappelons qu’un arbre-B de paramètre m est un arbre de
recherche, avec clés distinctes, dans lequel toutes les feuilles sont au même niveau.
Les nœuds internes ont une capacité : la racine contient entre 1 et C(m) clés,
les autres nœuds internes contiennent entre c(m) et C(m) clés. Deux algorithmes
d’insertion sont décrits dans la section 3.2.2(b). Dans l’algorithme prudent, c(m) =
m − 1 et C(m) = 2m − 1 ; dans l’algorithme optimiste, c(m) = m et C(m) = 2m.
Pour chacun des deux algorithmes, nous définissons différents types de feuilles :
nous disons qu’une feuille est de type k lorsqu’elle contient m + k − 2 clés et a donc
m + k − 1 possibilités d’insertion. Pour l’algorithme prudent, k varie de 1 à m + 1 ;
pour l’algorithme optimiste et pour un arbre de paramètre m − 1, alors k varie de 1
à m. De la sorte, l’insertion sur une feuille non saturée de type k produit une feuille
de type k + 1. L’insertion sur une feuille saturée produit respectivement
– un nœud de type 1 et un nœud de type 2 pour l’algorithme prudent ;
– deux nœuds de type 1 pour l’algorithme optimiste.
Nous analysons un arbre-B à travers le vecteur composition X n qui compte le
nombre de feuilles de chaque type à l’instant n, c’est-à-dire quand l’arbre contient
n clés. Ainsi X
(k)
n , la k-ième coordonnée de X n , est le nombre de feuilles de
type k. Pour l’algorithme prudent, X n est un vecteur de dimension m + 1 et pour
l’algorithme optimiste d’un arbre-B de paramètre m − 1, alors X n est un vecteur de
dimension m.
Pour les deux algorithmes, nous définissons Y n comme le vecteur composition
des possibilités d’insertion (ou intervalles vacants ou gaps) à l’instant n. Nous disons
qu’un gap est de type k quand il est attaché à une feuille de type k. Ainsi, Y
(k)
n , la
k-ième coordonnée de Y n est le nombre de gaps de type k. En d’autres termes :
(m + k − 1)X
(k)
n = Y
(k)
n .
Pour les deux algorithmes, le processus (Y n ) est un processus d’urne de Pólya
: convenons que les boules sont les intervalles d’insertion ou gaps possibles dans
les feuilles, et que les couleurs des boules sont les types de gaps. L’important est
que l’insertion a lieu uniformément sur les gaps et donc que le tirage des boules est
uniforme. De plus, nous ajoutons une clé à chaque étape, donc un gap, ce qui va
produire une urne de balance 1.
9 Urnes de Pólya et applications
où N(0, , 2 ) est un vecteur gaussien de moyenne nulle et de matrice de covariance
2 , avec
2
=
432
637
1 −1
−1 1
.
9.5.3 Arbres-B
Arbres-B et urnes de Pólya
Soit m ≥ 2 un entier. Rappelons qu’un arbre-B de paramètre m est un arbre de
recherche, avec clés distinctes, dans lequel toutes les feuilles sont au même niveau.
Les nœuds internes ont une capacité : la racine contient entre 1 et C(m) clés,
les autres nœuds internes contiennent entre c(m) et C(m) clés. Deux algorithmes
d’insertion sont décrits dans la section 3.2.2(b). Dans l’algorithme prudent, c(m) =
m − 1 et C(m) = 2m − 1 ; dans l’algorithme optimiste, c(m) = m et C(m) = 2m.
Pour chacun des deux algorithmes, nous définissons différents types de feuilles :
nous disons qu’une feuille est de type k lorsqu’elle contient m + k − 2 clés et a donc
m + k − 1 possibilités d’insertion. Pour l’algorithme prudent, k varie de 1 à m + 1 ;
pour l’algorithme optimiste et pour un arbre de paramètre m − 1, alors k varie de 1
à m. De la sorte, l’insertion sur une feuille non saturée de type k produit une feuille
de type k + 1. L’insertion sur une feuille saturée produit respectivement
– un nœud de type 1 et un nœud de type 2 pour l’algorithme prudent ;
– deux nœuds de type 1 pour l’algorithme optimiste.
Nous analysons un arbre-B à travers le vecteur composition X n qui compte le
nombre de feuilles de chaque type à l’instant n, c’est-à-dire quand l’arbre contient
n clés. Ainsi X
(k)
n , la k-ième coordonnée de X n , est le nombre de feuilles de
type k. Pour l’algorithme prudent, X n est un vecteur de dimension m + 1 et pour
l’algorithme optimiste d’un arbre-B de paramètre m − 1, alors X n est un vecteur de
dimension m.
Pour les deux algorithmes, nous définissons Y n comme le vecteur composition
des possibilités d’insertion (ou intervalles vacants ou gaps) à l’instant n. Nous disons
qu’un gap est de type k quand il est attaché à une feuille de type k. Ainsi, Y
(k)
n , la
k-ième coordonnée de Y n est le nombre de gaps de type k. En d’autres termes :
(m + k − 1)X
(k)
n = Y
(k)
n .
Pour les deux algorithmes, le processus (Y n ) est un processus d’urne de Pólya
: convenons que les boules sont les intervalles d’insertion ou gaps possibles dans
les feuilles, et que les couleurs des boules sont les types de gaps. L’important est
que l’insertion a lieu uniformément sur les gaps et donc que le tirage des boules est
uniforme. De plus, nous ajoutons une clé à chaque étape, donc un gap, ce qui va
produire une urne de balance 1.