356
8 Arbres m-aires et quadrants
– Le péage r(τ ) = 1 {|τ |>b} donne le nombre de nœuds internes d’un arbre paginé,
b ≥ 2 étant le nombre maximal de clés dans une page.
– Le péage r(τ ) = 1 {|τ |=1+2 d } donne le nombre de nœuds internes terminaux (les
nœuds dont les 2 d enfants sont des feuilles).
– Le péage r(τ ) = (|τ \ ∂τ | − 1) 1 {|τ |≥2} donne la longueur de cheminement
interne de l’arbre (où ∂τ désigne l’ensemble des feuilles de τ et τ \ ∂τ est
l’ensemble des nœuds internes).
– Le péage r(τ ) = |∂τ |1 {|τ |≥2} donne la longueur de cheminement externe
Méthode générale L’étude de ces paramètres additifs peut être abordée de manière
unifiée, selon une méthodologie exposée dans des articles de Flajolet et al. [84,
101].
– Nous établissons d’abord une équation de récurrence sur la valeur moyenne
E n [v(τ )] du paramètre, prise sur tous les arbres quadrants de recherche τ de
taille n et suivant la distribution P n ; puis nous transposons cette équation de
récurrence sur la fonction génératrice V (z) =
n E n [v(τ )]z n pour obtenir une
équation différentielle sur V (z).
– Suivant l’expression exacte du péage à la racine r(τ ), nous pouvons dans certains
cas résoudre directement cette équation différentielle et en tirer une forme close
pour V (z) : sinon, nous obtenons du moins l’asymptotique de ses coefficients.
– À partir de l’équation différentielle sur V (z), il est aussi possible de développer
une approche plus générale, basée sur la transformée d’Euler (dont la définition
est rappelée en section B.3.4), qui permet de traiter de manière systématique tout
péage à la racine.
– Pour voir le phénomène de transition de phase sur la dimension d (pour d ≤ 8,
la loi limite du nombre de feuilles est Gaussienne, pour d ≥ 9, le comportement
asymptotique est oscillant), l’on pourra se reporter à l’article de Chern et al. [44].
Dans la suite, nous détaillons ces points, puis les illustrons en les appliquant à
l’exemple de la longueur de cheminement dans les arbres quadrants de recherche.
Equation différentielle sur la série génératrice Soit τ ∈ Q n un arbre quadrant
de recherche aléatoire à n clés, de loi P n . Pour v un paramètre additif, posons v n =
E n [v(τ )]. Le principe « diviser pour régner » montre que la suite (v n ) satisfait la
relation de récurrence
v n = r n + 2
d
n−1
p=0
π n,p v p ,
(n≥ 2)
(8.8)
où r n = E n [r(τ )] est la valeur moyenne du péage à la racine sur les arbres à n clés,
et où les π n,p = P n (|τ (0) | = p) sont les probabilités de partage dont nous avons vu
l’expression dans la proposition 8.15.
8 Arbres m-aires et quadrants
– Le péage r(τ ) = 1 {|τ |>b} donne le nombre de nœuds internes d’un arbre paginé,
b ≥ 2 étant le nombre maximal de clés dans une page.
– Le péage r(τ ) = 1 {|τ |=1+2 d } donne le nombre de nœuds internes terminaux (les
nœuds dont les 2 d enfants sont des feuilles).
– Le péage r(τ ) = (|τ \ ∂τ | − 1) 1 {|τ |≥2} donne la longueur de cheminement
interne de l’arbre (où ∂τ désigne l’ensemble des feuilles de τ et τ \ ∂τ est
l’ensemble des nœuds internes).
– Le péage r(τ ) = |∂τ |1 {|τ |≥2} donne la longueur de cheminement externe
Méthode générale L’étude de ces paramètres additifs peut être abordée de manière
unifiée, selon une méthodologie exposée dans des articles de Flajolet et al. [84,
101].
– Nous établissons d’abord une équation de récurrence sur la valeur moyenne
E n [v(τ )] du paramètre, prise sur tous les arbres quadrants de recherche τ de
taille n et suivant la distribution P n ; puis nous transposons cette équation de
récurrence sur la fonction génératrice V (z) =
n E n [v(τ )]z n pour obtenir une
équation différentielle sur V (z).
– Suivant l’expression exacte du péage à la racine r(τ ), nous pouvons dans certains
cas résoudre directement cette équation différentielle et en tirer une forme close
pour V (z) : sinon, nous obtenons du moins l’asymptotique de ses coefficients.
– À partir de l’équation différentielle sur V (z), il est aussi possible de développer
une approche plus générale, basée sur la transformée d’Euler (dont la définition
est rappelée en section B.3.4), qui permet de traiter de manière systématique tout
péage à la racine.
– Pour voir le phénomène de transition de phase sur la dimension d (pour d ≤ 8,
la loi limite du nombre de feuilles est Gaussienne, pour d ≥ 9, le comportement
asymptotique est oscillant), l’on pourra se reporter à l’article de Chern et al. [44].
Dans la suite, nous détaillons ces points, puis les illustrons en les appliquant à
l’exemple de la longueur de cheminement dans les arbres quadrants de recherche.
Equation différentielle sur la série génératrice Soit τ ∈ Q n un arbre quadrant
de recherche aléatoire à n clés, de loi P n . Pour v un paramètre additif, posons v n =
E n [v(τ )]. Le principe « diviser pour régner » montre que la suite (v n ) satisfait la
relation de récurrence
v n = r n + 2
d
n−1
p=0
π n,p v p ,
(n≥ 2)
(8.8)
où r n = E n [r(τ )] est la valeur moyenne du péage à la racine sur les arbres à n clés,
et où les π n,p = P n (|τ (0) | = p) sont les probabilités de partage dont nous avons vu
l’expression dans la proposition 8.15.