6.1 Analyses de la longueur de cheminement et du profil
225
Fig. 6.3 Représentation du profil d’un abr aléatoire à 10 000 nœuds (donc une fois complété,
à 10 000 nœuds internes et 10 001 nœuds externes). Cet abr est de hauteur 29 et de niveau de
saturation 5. Sur cette figure sont respectivement représentés : le nombre de nœuds internes par
niveau U k , le nombre de nœuds externes (du complété) V k et enfin le nombre total de nœuds par
niveau Z k = U k + V k . Chaque graduation en abscisse correspond à 100 nœuds. La forme typique
est celle d’un « radis »
Rappelons que la n + 1-ième insertion se fait uniformément sur l’une des n + 1
feuilles de l’arbre τ n . Par conséquent, la profondeur d’insertion d’une nouvelle clé
dans τ n (nous rappelons qu’elle est notée D n+1 ) a pour loi conditionnelle sachant
τ n :
P
D n+1 = k
τn
=
U k (τ n )
n + 1
= μ τ n (k),
(6.7)
225
Fig. 6.3 Représentation du profil d’un abr aléatoire à 10 000 nœuds (donc une fois complété,
à 10 000 nœuds internes et 10 001 nœuds externes). Cet abr est de hauteur 29 et de niveau de
saturation 5. Sur cette figure sont respectivement représentés : le nombre de nœuds internes par
niveau U k , le nombre de nœuds externes (du complété) V k et enfin le nombre total de nœuds par
niveau Z k = U k + V k . Chaque graduation en abscisse correspond à 100 nœuds. La forme typique
est celle d’un « radis »
Rappelons que la n + 1-ième insertion se fait uniformément sur l’une des n + 1
feuilles de l’arbre τ n . Par conséquent, la profondeur d’insertion d’une nouvelle clé
dans τ n (nous rappelons qu’elle est notée D n+1 ) a pour loi conditionnelle sachant
τ n :
P
D n+1 = k
τn
=
U k (τ n )
n + 1
= μ τ n (k),
(6.7)