xx
Introduction
pas présent dans l’arbre (s’il se trouvait ailleurs, ce ne serait plus un arbre binaire de
recherche) ; de plus nous avons trouvé la place où devrait aller 8, si nous souhaitions
l’ajouter à l’ensemble des clés : ce serait comme fils gauche de 9.
Nous avons vu sur cet exemple qu’un arbre binaire de recherche permet de
structurer un ensemble E de clés, de telle sorte qu’il soit facile de retrouver une clé
de valeur donnée ; il est également aisé d’ajouter ou de supprimer une clé dans E.
Plus formellement, pour chercher une clé x dans un arbre binaire de recherche τ ,
nous comparons d’abord x à la clé contenue y dans la racine de l’arbre ; si x = y,
la recherche est finie ; dans le cas contraire, nous poursuivons récursivement la
recherche dans le sous-arbre gauche, si x < y, et dans le sous-arbre droit sinon.
La recherche s’arrête, soit lorsque nous avons trouvé la clé cherchée, soit lorsque
nous arrivons à un sous-arbre vide – dans ce cas, nous avons d’ailleurs trouvé la
place où x doit être inséré dans l’arbre, si nous souhaitons l’ajouter tout en gardant
la structure d’arbre binaire de recherche.
Quel est le coût d’une recherche avec succès d’une clé x dans un arbre binaire
de recherche τ construit sur un ensemble E de clés que nous supposons toutes
distinctes ? Une unité de mesure possible est le nombre de nœuds visités pour
trouver x ; c’est aussi le nombre de comparaisons de x à des clés présentes
dans l’arbre. Ce nombre est un paramètre classique : c’est 1+ la profondeur 4 (ou
niveau) du nœud contenant x dans l’arbre τ ; notons-le 1 + Prof (x, τ ). Regardons
maintenant le coût « moyen » d’une recherche avec succès d’une clé x dans un
arbre τ , en supposant que chacune des clés présentes dans l’arbre a la même
probabilité d’être la clé cherchée : ce coût est alors 1/|τ |
x∈τ (1 + Prof (x, τ )),
où |τ | est le nombre de nœud de τ soit encore la taille de l’arbre τ . Or la somme
x∈τ Prof (x, τ ) est un autre paramètre classique, la longueur de cheminement
de l’arbre, notée lc(τ ) ; le coût moyen d’une recherche avec succès est donc
1 + lc(τ )/|τ |.
Quant au maximum du coût d’une recherche avec succès, il est obtenu pour les
clés les plus éloignées de la racine, et le paramètre associé est le maximum des
profondeurs des nœuds de l’arbre : c’est sa hauteur.
Ajoutons un niveau d’aléa ; supposons que n clés (leur nombre est supposé
fixé) sont choisies selon une certaine distribution de probabilité dans un ensemble. 5
L’arbre, noté τ n , devient aléatoire, ainsi que sa longueur de cheminement lc(τ n ),
et l’objectif est de caractériser la loi de lc(τ n ), obtenant ainsi la loi du coût d’une
recherche avec succès d’une clé dans un arbre binaire de recherche de taille n. Pour
la moyenne lc n := E (lc(τ n )) de la longueur de cheminement, il est intéressant
d’utiliser les outils de la combinatoire analytique afin d’établir une équation de
récurrence sur lc n . En la résolvant (soit directement, soit par l’intermédiaire d’une
fonction génératrice), il est possible d’obtenir une formule close sur lc n , ainsi que
son comportement asymptotique lorsque le nombre n de clés devient grand. Pour
4 Il est convenu que la racine est à profondeur 0.
5 Il n’est pas question ici de la manière de construire l’arbre, qui peut dépendre de l’ordre dans
lequel les clés sont entrées ; voir pour cela le chapitre 2 et l’annexe A.
Introduction
pas présent dans l’arbre (s’il se trouvait ailleurs, ce ne serait plus un arbre binaire de
recherche) ; de plus nous avons trouvé la place où devrait aller 8, si nous souhaitions
l’ajouter à l’ensemble des clés : ce serait comme fils gauche de 9.
Nous avons vu sur cet exemple qu’un arbre binaire de recherche permet de
structurer un ensemble E de clés, de telle sorte qu’il soit facile de retrouver une clé
de valeur donnée ; il est également aisé d’ajouter ou de supprimer une clé dans E.
Plus formellement, pour chercher une clé x dans un arbre binaire de recherche τ ,
nous comparons d’abord x à la clé contenue y dans la racine de l’arbre ; si x = y,
la recherche est finie ; dans le cas contraire, nous poursuivons récursivement la
recherche dans le sous-arbre gauche, si x < y, et dans le sous-arbre droit sinon.
La recherche s’arrête, soit lorsque nous avons trouvé la clé cherchée, soit lorsque
nous arrivons à un sous-arbre vide – dans ce cas, nous avons d’ailleurs trouvé la
place où x doit être inséré dans l’arbre, si nous souhaitons l’ajouter tout en gardant
la structure d’arbre binaire de recherche.
Quel est le coût d’une recherche avec succès d’une clé x dans un arbre binaire
de recherche τ construit sur un ensemble E de clés que nous supposons toutes
distinctes ? Une unité de mesure possible est le nombre de nœuds visités pour
trouver x ; c’est aussi le nombre de comparaisons de x à des clés présentes
dans l’arbre. Ce nombre est un paramètre classique : c’est 1+ la profondeur 4 (ou
niveau) du nœud contenant x dans l’arbre τ ; notons-le 1 + Prof (x, τ ). Regardons
maintenant le coût « moyen » d’une recherche avec succès d’une clé x dans un
arbre τ , en supposant que chacune des clés présentes dans l’arbre a la même
probabilité d’être la clé cherchée : ce coût est alors 1/|τ |
x∈τ (1 + Prof (x, τ )),
où |τ | est le nombre de nœud de τ soit encore la taille de l’arbre τ . Or la somme
x∈τ Prof (x, τ ) est un autre paramètre classique, la longueur de cheminement
de l’arbre, notée lc(τ ) ; le coût moyen d’une recherche avec succès est donc
1 + lc(τ )/|τ |.
Quant au maximum du coût d’une recherche avec succès, il est obtenu pour les
clés les plus éloignées de la racine, et le paramètre associé est le maximum des
profondeurs des nœuds de l’arbre : c’est sa hauteur.
Ajoutons un niveau d’aléa ; supposons que n clés (leur nombre est supposé
fixé) sont choisies selon une certaine distribution de probabilité dans un ensemble. 5
L’arbre, noté τ n , devient aléatoire, ainsi que sa longueur de cheminement lc(τ n ),
et l’objectif est de caractériser la loi de lc(τ n ), obtenant ainsi la loi du coût d’une
recherche avec succès d’une clé dans un arbre binaire de recherche de taille n. Pour
la moyenne lc n := E (lc(τ n )) de la longueur de cheminement, il est intéressant
d’utiliser les outils de la combinatoire analytique afin d’établir une équation de
récurrence sur lc n . En la résolvant (soit directement, soit par l’intermédiaire d’une
fonction génératrice), il est possible d’obtenir une formule close sur lc n , ainsi que
son comportement asymptotique lorsque le nombre n de clés devient grand. Pour
4 Il est convenu que la racine est à profondeur 0.
5 Il n’est pas question ici de la manière de construire l’arbre, qui peut dépendre de l’ordre dans
lequel les clés sont entrées ; voir pour cela le chapitre 2 et l’annexe A.