8.1 Arbres m-aires de recherche
341
Pour des raisons analogues à celles invoquées pour les arbres binaires de
recherche, la suite d’arbres (C(T n )) a la même distribution que celle obtenue en
insérant successivement n entiers d’une permutation de loi uniforme sur S n .
L’évolution dynamique de l’arbre est analogue à celle des arbres binaires de
recherche : par récurrence sur n, il est clair que l’arbre m-aire de recherche T n
(qui contient n clés) définit n + 1 intervalles correspondant aux intervalles vacants
ou possibilités d’insertion sur ses nœuds internes terminaux. L’important dans ce
modèle est que la n + 1-ième clé x n+1 est insérée uniformément, avec probabilité
1
n + 1
pour chacun des intervalles vacants. La suite (T n ) est une chaîne de Markov
à valeurs dans l’ensemble des arbres m-aires complets (analogue de l’ensemble B
des arbres binaires complets mais avec m enfants par nœud interne).
8.1.2 Etude des arbres m-aires de recherche par séries
génératrices
Dans cette section, le raisonnement vient du principe « diviser pour régner » qui a
été posé dans la proposition 2.13 de la section 2.2.3. Il s’énonce ainsi pour les arbres
m-aires.
Proposition 8.6 Soit P n la loi de T n , l’arbre m-aire de recherche à n clés. Si
n ≥ m − 1, appelons (en omettant l’indice n) T (1) , T (2) , . . . , T (m) les m sousarbres de la racine. Soient i 1 , i 2 , . . . , i m entiers positifs 2 tels que i 1 +i 2 +· · ·+i m =
n−(m−1). Alors conditionnellement en T (1) , T (2) , . . . , T (m) de tailles respectives
i 1 , i 2 , . . . , i m , ces sous-arbres sont eux-mêmes des arbres m-aires de recherche
indépendants de loi P i 1 , P i 2 , . . . , P i m . De plus, la probabilité pour que les m sousarbres de la racine soient de taille i 1 , i 2 , . . . , i m avec i 1 +i 2 +· · ·+i m = n−(m−1)
est égale à
P
|T
(1)
| = i 1 , . . . , |T
(m)
| = i m
=
1
n
m − 1
=
(m − 1)!(n − m + 1)!
n!
Cette proposition repose sur le modèle des permutations uniformes ; en outre, il est
utile de disposer du petit lemme combinatoire suivant :
Lemme 8.7 Pour tout n ≥ m − 1, il y a
n
m − 1
m-uplets (i 1 , . . . , i m ) d’entiers
positifs tels que i 1 + i 2 + · · · + i m = n − (m − 1).
2 Nous rappelons la convention française dans laquelle positif signifie positif ou nul.
341
Pour des raisons analogues à celles invoquées pour les arbres binaires de
recherche, la suite d’arbres (C(T n )) a la même distribution que celle obtenue en
insérant successivement n entiers d’une permutation de loi uniforme sur S n .
L’évolution dynamique de l’arbre est analogue à celle des arbres binaires de
recherche : par récurrence sur n, il est clair que l’arbre m-aire de recherche T n
(qui contient n clés) définit n + 1 intervalles correspondant aux intervalles vacants
ou possibilités d’insertion sur ses nœuds internes terminaux. L’important dans ce
modèle est que la n + 1-ième clé x n+1 est insérée uniformément, avec probabilité
1
n + 1
pour chacun des intervalles vacants. La suite (T n ) est une chaîne de Markov
à valeurs dans l’ensemble des arbres m-aires complets (analogue de l’ensemble B
des arbres binaires complets mais avec m enfants par nœud interne).
8.1.2 Etude des arbres m-aires de recherche par séries
génératrices
Dans cette section, le raisonnement vient du principe « diviser pour régner » qui a
été posé dans la proposition 2.13 de la section 2.2.3. Il s’énonce ainsi pour les arbres
m-aires.
Proposition 8.6 Soit P n la loi de T n , l’arbre m-aire de recherche à n clés. Si
n ≥ m − 1, appelons (en omettant l’indice n) T (1) , T (2) , . . . , T (m) les m sousarbres de la racine. Soient i 1 , i 2 , . . . , i m entiers positifs 2 tels que i 1 +i 2 +· · ·+i m =
n−(m−1). Alors conditionnellement en T (1) , T (2) , . . . , T (m) de tailles respectives
i 1 , i 2 , . . . , i m , ces sous-arbres sont eux-mêmes des arbres m-aires de recherche
indépendants de loi P i 1 , P i 2 , . . . , P i m . De plus, la probabilité pour que les m sousarbres de la racine soient de taille i 1 , i 2 , . . . , i m avec i 1 +i 2 +· · ·+i m = n−(m−1)
est égale à
P
|T
(1)
| = i 1 , . . . , |T
(m)
| = i m
=
1
n
m − 1
=
(m − 1)!(n − m + 1)!
n!
Cette proposition repose sur le modèle des permutations uniformes ; en outre, il est
utile de disposer du petit lemme combinatoire suivant :
Lemme 8.7 Pour tout n ≥ m − 1, il y a
n
m − 1
m-uplets (i 1 , . . . , i m ) d’entiers
positifs tels que i 1 + i 2 + · · · + i m = n − (m − 1).
2 Nous rappelons la convention française dans laquelle positif signifie positif ou nul.