9.5 Applications algorithmiques
387
arbres 2–3 en section 9.5.2. Ces deux exemples ont l’intérêt de réunir des petites
et des grandes urnes (voir la définition 9.7 pour petite et grande urne), alors que la
littérature algorithmique et combinatoire sur les urnes contient essentiellement des
petites urnes.
9.5.1 Arbres m-aires de recherche
La définition des arbres m-aires de recherche a été donnée dans la section 8.1.1 du
chapitre 8 et le point de vue dynamique, qui nous intéresse ici, est présenté dans la
section 8.1.3.
Comme cela a été remarqué depuis longtemps, par Mahmoud [173] notamment,
le vecteur d’occupation qui décrit les nœuds d’un arbre m-aire de recherche (m est
un entier fixé, m ≥ 2), est une urne de Pólya pourvu que nous considérions que les
boules sont les intervalles vacants disponibles dans chacun des nœuds de l’arbre et
que les couleurs sont les types de nœuds. Cela vient du fait que l’insertion d’une
nouvelle clé se fait uniformément sur les intervalles vacants disponibles. Rappelons
qu’un nœud est dit de type i, i = 1, 2, . . . , m, quand il contient (i − 1) clés, soit i
intervalles vacants ou possibilités d’insertion. Il a été convenu dans la section 8.1.3
de ne pas s’occuper des nœuds saturés de type m.
Nous nous intéressons au vecteur X n de R m−1 dont les coordonnées X
(i)
n
représentent le nombre de nœuds de type i dans l’arbre à (n − 1) clés. 8 Dans la
correspondance avec une urne de Pólya, appelons Y n le vecteur composition de
l’urne ; alors :
Y
(i)
n = iX
(i)
n .
(9.11)
Autrement dit, si P est la matrice 9
P =
⎛
⎜
⎜
⎜
⎝
1
2
. . .
m − 1
⎞
⎟
⎟
⎟
⎠
,
alors la correspondance entre urne et arbres m-aires est donnée par
Y n = X n P .
L’asymptotique de Y n donnera celle de X n . Voyons donc comment se traduisent les
théorèmes 9.8 et 9.10.
8 Et non pas à n clés pour des raisons de notations plus agréables.
9 Quand rien n’est écrit, le coefficient est nul.
387
arbres 2–3 en section 9.5.2. Ces deux exemples ont l’intérêt de réunir des petites
et des grandes urnes (voir la définition 9.7 pour petite et grande urne), alors que la
littérature algorithmique et combinatoire sur les urnes contient essentiellement des
petites urnes.
9.5.1 Arbres m-aires de recherche
La définition des arbres m-aires de recherche a été donnée dans la section 8.1.1 du
chapitre 8 et le point de vue dynamique, qui nous intéresse ici, est présenté dans la
section 8.1.3.
Comme cela a été remarqué depuis longtemps, par Mahmoud [173] notamment,
le vecteur d’occupation qui décrit les nœuds d’un arbre m-aire de recherche (m est
un entier fixé, m ≥ 2), est une urne de Pólya pourvu que nous considérions que les
boules sont les intervalles vacants disponibles dans chacun des nœuds de l’arbre et
que les couleurs sont les types de nœuds. Cela vient du fait que l’insertion d’une
nouvelle clé se fait uniformément sur les intervalles vacants disponibles. Rappelons
qu’un nœud est dit de type i, i = 1, 2, . . . , m, quand il contient (i − 1) clés, soit i
intervalles vacants ou possibilités d’insertion. Il a été convenu dans la section 8.1.3
de ne pas s’occuper des nœuds saturés de type m.
Nous nous intéressons au vecteur X n de R m−1 dont les coordonnées X
(i)
n
représentent le nombre de nœuds de type i dans l’arbre à (n − 1) clés. 8 Dans la
correspondance avec une urne de Pólya, appelons Y n le vecteur composition de
l’urne ; alors :
Y
(i)
n = iX
(i)
n .
(9.11)
Autrement dit, si P est la matrice 9
P =
⎛
⎜
⎜
⎜
⎝
1
2
. . .
m − 1
⎞
⎟
⎟
⎟
⎠
,
alors la correspondance entre urne et arbres m-aires est donnée par
Y n = X n P .
L’asymptotique de Y n donnera celle de X n . Voyons donc comment se traduisent les
théorèmes 9.8 et 9.10.
8 Et non pas à n clés pour des raisons de notations plus agréables.
9 Quand rien n’est écrit, le coefficient est nul.