6.8 Exercices
279
c) Montrer que la famille de lois de s n , n ≥ 1 satisfait un principe de grandes déviations sur [0, ∞[
de vitesse log n et de fonction de taux η z où
η z (x) = x log
x
2z
− x + 2z,
x ≥ 0.
6.7. On regarde ici l’effet des suppressions sur un arbre binaire de recherche. Une insertion
sera notée I et une suppression S. Ainsi, III est une suite de trois insertions, qui crée donc un
arbre binaire de recherche aléatoire avec 3 clés. De même, IIISI est une suite d’opérations où
on crée un arbre avec 3 insertions, puis on supprime une des clés existantes, et enfin on effectue
une nouvelle insertion. On code plus précisément les suites d’opérations, appelées aussi histoires,
comme indiqué sur l’exemple qui suit. Une histoire possible est I2 I4 I3 S I1 dont la signification
est : on insère d’abord 2, ensuite 4 et 3 ; puis on supprime le plus petit élément ; enfin on insère 1.
Calculer la distribution de probabilité sur les arbres binaires de recherche de taille 3 obtenus
par une histoire IIISI, et la comparer à celle obtenue par III ; conclure.
(Cet exercice est tiré de Panny [202].)
6.8. Démontrer la proposition 6.36. On pourra raisonner par récurrence, en supposant un arbre
binaire de recherche τ de taille n construit à partir d’une permutation σ ∈ S n et en considérant les
permutations induites sur les sous-arbres gauche et droit.
279
c) Montrer que la famille de lois de s n , n ≥ 1 satisfait un principe de grandes déviations sur [0, ∞[
de vitesse log n et de fonction de taux η z où
η z (x) = x log
x
2z
− x + 2z,
x ≥ 0.
6.7. On regarde ici l’effet des suppressions sur un arbre binaire de recherche. Une insertion
sera notée I et une suppression S. Ainsi, III est une suite de trois insertions, qui crée donc un
arbre binaire de recherche aléatoire avec 3 clés. De même, IIISI est une suite d’opérations où
on crée un arbre avec 3 insertions, puis on supprime une des clés existantes, et enfin on effectue
une nouvelle insertion. On code plus précisément les suites d’opérations, appelées aussi histoires,
comme indiqué sur l’exemple qui suit. Une histoire possible est I2 I4 I3 S I1 dont la signification
est : on insère d’abord 2, ensuite 4 et 3 ; puis on supprime le plus petit élément ; enfin on insère 1.
Calculer la distribution de probabilité sur les arbres binaires de recherche de taille 3 obtenus
par une histoire IIISI, et la comparer à celle obtenue par III ; conclure.
(Cet exercice est tiré de Panny [202].)
6.8. Démontrer la proposition 6.36. On pourra raisonner par récurrence, en supposant un arbre
binaire de recherche τ de taille n construit à partir d’une permutation σ ∈ S n et en considérant les
permutations induites sur les sous-arbres gauche et droit.