268
6 Arbres binaires de recherche
Fig. 6.14 Un arbre binaire de recherche de taille 1 000, tiré selon la loi des permutations
uniformes (correspondant donc à une permutation de taille 1 000). Pour plus de clarté les nœuds
externes n’ont pas été représentés
Fig. 6.15 Représentation du profil d’un abr aléatoire à 1 000 nœuds de la figure 6.14 (donc une
fois complété, à 1 000 nœuds internes et 1 001 nœuds externes). Cet abr est de hauteur 22 et de
niveau de saturation 2. 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 à 20 nœuds
6 Arbres binaires de recherche
Fig. 6.14 Un arbre binaire de recherche de taille 1 000, tiré selon la loi des permutations
uniformes (correspondant donc à une permutation de taille 1 000). Pour plus de clarté les nœuds
externes n’ont pas été représentés
Fig. 6.15 Représentation du profil d’un abr aléatoire à 1 000 nœuds de la figure 6.14 (donc une
fois complété, à 1 000 nœuds internes et 1 001 nœuds externes). Cet abr est de hauteur 22 et de
niveau de saturation 2. 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 à 20 nœuds