2.2 Aléa sur les arbres marqués
49
Fig. 2.5 Un arbre binaire de recherche de taille 200 (tiré aléatoirement sous le modèle des
permutations uniformes). En bas, le même arbre mais complété (avec donc 200 nœuds internes
correspondant au clés et 201 nœuds externes ‘’
2.2.3 Arbres binaires de recherche aléatoires
Définition 2.6 Un arbre binaire de recherche aléatoire est un arbre binaire de
recherche dans lequel les marques (x i ) i≥1 des nœuds sont des variables aléatoires à
valeurs dans un ensemble totalement ordonné.
Remarque 2.7 Dans cette section, nous traitons essentiellement des arbres binaires
de recherche aléatoires sous le modèle des permutations uniformes (cf. la définition 2.4), c’est-à-dire lorsque les marques (x i ) i≥1 des nœuds sont des variables
aléatoires i.i.d. de même loi continue (voir la figure 2.5 pour un exemple d’arbre
à 200 nœuds).
D’un point de vue algorithmique, le modèle des permutations uniformes est lié de
façon naturelle à la construction d’un arbre binaire de recherche par insertion aux
feuilles. Il existe d’autres algorithmes d’insertion que l’insertion aux feuilles, par
exemple l’insertion à la racine présentée en annexe A.2.4 ou, dans le cas où les clés
ne sont pas toutes distinctes, une méthode d’insertion qui assure que des clés égales
se suivent. De tels algorithmes conduisent à des modèles de probabilité différents.
Nous verrons en section 6.5 comment, pour une loi quelconque sur les clés et pour
des clés non indépendantes, il est possible de se ramener au cas des permutations
uniformes par randomisation.
49
Fig. 2.5 Un arbre binaire de recherche de taille 200 (tiré aléatoirement sous le modèle des
permutations uniformes). En bas, le même arbre mais complété (avec donc 200 nœuds internes
correspondant au clés et 201 nœuds externes ‘’
2.2.3 Arbres binaires de recherche aléatoires
Définition 2.6 Un arbre binaire de recherche aléatoire est un arbre binaire de
recherche dans lequel les marques (x i ) i≥1 des nœuds sont des variables aléatoires à
valeurs dans un ensemble totalement ordonné.
Remarque 2.7 Dans cette section, nous traitons essentiellement des arbres binaires
de recherche aléatoires sous le modèle des permutations uniformes (cf. la définition 2.4), c’est-à-dire lorsque les marques (x i ) i≥1 des nœuds sont des variables
aléatoires i.i.d. de même loi continue (voir la figure 2.5 pour un exemple d’arbre
à 200 nœuds).
D’un point de vue algorithmique, le modèle des permutations uniformes est lié de
façon naturelle à la construction d’un arbre binaire de recherche par insertion aux
feuilles. Il existe d’autres algorithmes d’insertion que l’insertion aux feuilles, par
exemple l’insertion à la racine présentée en annexe A.2.4 ou, dans le cas où les clés
ne sont pas toutes distinctes, une méthode d’insertion qui assure que des clés égales
se suivent. De tels algorithmes conduisent à des modèles de probabilité différents.
Nous verrons en section 6.5 comment, pour une loi quelconque sur les clés et pour
des clés non indépendantes, il est possible de se ramener au cas des permutations
uniformes par randomisation.