224
6 Arbres binaires de recherche
6.1.2 Longueur de cheminement, profil et martingales
Les méthodes probabilistes vont ici fournir le comportement asymptotique presque
sûr de la longueur de cheminement. Plus précisément, nous allons mettre en
évidence une martingale 1 relative au profil de l’abr, et les théorèmes généraux
de convergence des martingales nous fourniront une limite presque sûre pour
la longueur de cheminement (théorème 6.11) ainsi que pour le profil de l’abr
(théorème 6.12).
La martingale de l’abr
La martingale de l’abr est construite à partir du profil de l’arbre. Si τ n est un abr de
taille n, la répartition des noeuds par niveau est décrite par
U k (τ n ) := nombre de feuilles au niveau k dans l’arbre τ n .
(6.5)
La suite (U k (τ n ), k ≥ 0) s’appelle le profil de l’arbre, nous l’avons déjà rencontrée
dans la section 1.3, et elle contient l’information sur la forme de l’arbre.
Remarque 6.4 Nous pouvons travailler avec les nœuds internes de façon analogue
à ce que nous allons présenter pour les feuilles, et introduire
V k (τ n ) := le nombre de noeuds internes au niveau k dans l’arbre τ n
ainsi que Z k (τ n ) := le nombre total de noeuds au niveau k dans l’arbre τ n , de sorte
que Z k (τ n ) = U k (τ n ) + V k (τ n ). L’étude serait analogue. Nous avons fait ce
choix de définition du profil par les feuilles, parce que la croissance de l’arbre
est plus explicite sur les feuilles. La figure 6.3 représente visuellement le profil
(U k , V k , Z k ) k≥0 d’un abr aléatoire.
Comme il y a n + 1 feuilles dans un arbre τ n de taille n, la quantité
U k (τ n )
n + 1
représente la proportion de feuilles au niveau k, et la mesure définie par
μ τ n :=
+∞
k=0
U k (τ n )
n + 1
δ {k}
(6.6)
(où δ {k} désigne la mesure de Dirac au point k) est une mesure de probabilité qui
indique la répartition des feuilles par niveau et contient toute l’information sur le
profil de l’arbre τ n . Remarquons que la somme est finie, puisqu’il y a au plus n
termes (et même h(τ n ) termes, où h(τ n ) est la hauteur de l’arbre τ n ).
1 Voir la section C.8 pour des rappels sur les martingales et les filtrations.
6 Arbres binaires de recherche
6.1.2 Longueur de cheminement, profil et martingales
Les méthodes probabilistes vont ici fournir le comportement asymptotique presque
sûr de la longueur de cheminement. Plus précisément, nous allons mettre en
évidence une martingale 1 relative au profil de l’abr, et les théorèmes généraux
de convergence des martingales nous fourniront une limite presque sûre pour
la longueur de cheminement (théorème 6.11) ainsi que pour le profil de l’abr
(théorème 6.12).
La martingale de l’abr
La martingale de l’abr est construite à partir du profil de l’arbre. Si τ n est un abr de
taille n, la répartition des noeuds par niveau est décrite par
U k (τ n ) := nombre de feuilles au niveau k dans l’arbre τ n .
(6.5)
La suite (U k (τ n ), k ≥ 0) s’appelle le profil de l’arbre, nous l’avons déjà rencontrée
dans la section 1.3, et elle contient l’information sur la forme de l’arbre.
Remarque 6.4 Nous pouvons travailler avec les nœuds internes de façon analogue
à ce que nous allons présenter pour les feuilles, et introduire
V k (τ n ) := le nombre de noeuds internes au niveau k dans l’arbre τ n
ainsi que Z k (τ n ) := le nombre total de noeuds au niveau k dans l’arbre τ n , de sorte
que Z k (τ n ) = U k (τ n ) + V k (τ n ). L’étude serait analogue. Nous avons fait ce
choix de définition du profil par les feuilles, parce que la croissance de l’arbre
est plus explicite sur les feuilles. La figure 6.3 représente visuellement le profil
(U k , V k , Z k ) k≥0 d’un abr aléatoire.
Comme il y a n + 1 feuilles dans un arbre τ n de taille n, la quantité
U k (τ n )
n + 1
représente la proportion de feuilles au niveau k, et la mesure définie par
μ τ n :=
+∞
k=0
U k (τ n )
n + 1
δ {k}
(6.6)
(où δ {k} désigne la mesure de Dirac au point k) est une mesure de probabilité qui
indique la répartition des feuilles par niveau et contient toute l’information sur le
profil de l’arbre τ n . Remarquons que la somme est finie, puisqu’il y a au plus n
termes (et même h(τ n ) termes, où h(τ n ) est la hauteur de l’arbre τ n ).
1 Voir la section C.8 pour des rappels sur les martingales et les filtrations.