Introduction
xix
Fig. 2 Un arbre binaire de
recherche à 7 clés
Un exemple : coût dans les arbres binaires de recherche
Définissons un arbre binaire de recherche, construit à partir d’un ensemble totalement ordonné E de clés distinctes, comme suit 2 :
– si E = ∅, l’arbre est vide ;
– si E = {x}, l’arbre est réduit à un nœud unique contenant la clé x ;
– sinon, choisissons une des clés de E, appelons-la x, qui va dans le nœud racine ;
les autres clés de E servent à construire deux sous-arbres : celui de gauche 3
contient les clés inférieures à x et celui de droite contient les clés supérieures
à x. Ces sous-arbres gauche et droit sont eux-mêmes structurés récursivement en
arbres binaires de recherche.
L’arbre marqué de la figure 1, qui est redessiné figure 2, est en fait un arbre
binaire de recherche construit sur (par exemple) la suite de clés (7, 3, 9, 4, 0, 6, 10) :
la valeur 7 à la racine divise les clés restantes en deux sous-suites ; les clés
de (3, 4, 0, 6) forment le sous-arbre gauche et les clés de (9, 10) forment le
sous-arbre droit ; ces deux sous-arbres sont eux-mêmes des arbres binaires de
recherche.
Regardons ce qui se passe, pour notre arbre exemple, lorsque nous cherchons
la valeur 4. Nous la comparons d’abord à la valeur à la racine, 7 : 4 < 7, et nous
poursuivons la recherche dans le sous-arbre gauche. Sa racine contient la clé 3, à
laquelle nous comparons 4 : 4 > 3, donc nous partons dans le sous-arbre droit
de ce sous-arbre gauche. Une dernière comparaison nous permet de vérifier que
4 est la racine de ce sous-arbre, et est bien présent dans l’arbre. Il nous a fallu 3
comparaisons, ce qui correspond aussi au nombre de niveaux testés : la racine, puis
un enfant et un petit-enfant de la racine.
Supposons maintenant que nous cherchions la valeur 8. Nous allons toujours
comparer cette valeur à la clé à la racine, 7 : 8 > 7, donc nous allons vers le fils
droit. Sa propre racine contient la clé 9, plus grande que 8, donc nous regardons
dans son sous-arbre gauche. . . qui est vide ! Nous savons maintenant que 8 n’est
2 Nous donnons dans la section 1.2.5 une définition plus rigoureuse des arbres binaires de
recherche.
3 Les arbres sont dessinés dans le plan, ordonnés de gauche à droite par ordre croissant.
xix
Fig. 2 Un arbre binaire de
recherche à 7 clés
Un exemple : coût dans les arbres binaires de recherche
Définissons un arbre binaire de recherche, construit à partir d’un ensemble totalement ordonné E de clés distinctes, comme suit 2 :
– si E = ∅, l’arbre est vide ;
– si E = {x}, l’arbre est réduit à un nœud unique contenant la clé x ;
– sinon, choisissons une des clés de E, appelons-la x, qui va dans le nœud racine ;
les autres clés de E servent à construire deux sous-arbres : celui de gauche 3
contient les clés inférieures à x et celui de droite contient les clés supérieures
à x. Ces sous-arbres gauche et droit sont eux-mêmes structurés récursivement en
arbres binaires de recherche.
L’arbre marqué de la figure 1, qui est redessiné figure 2, est en fait un arbre
binaire de recherche construit sur (par exemple) la suite de clés (7, 3, 9, 4, 0, 6, 10) :
la valeur 7 à la racine divise les clés restantes en deux sous-suites ; les clés
de (3, 4, 0, 6) forment le sous-arbre gauche et les clés de (9, 10) forment le
sous-arbre droit ; ces deux sous-arbres sont eux-mêmes des arbres binaires de
recherche.
Regardons ce qui se passe, pour notre arbre exemple, lorsque nous cherchons
la valeur 4. Nous la comparons d’abord à la valeur à la racine, 7 : 4 < 7, et nous
poursuivons la recherche dans le sous-arbre gauche. Sa racine contient la clé 3, à
laquelle nous comparons 4 : 4 > 3, donc nous partons dans le sous-arbre droit
de ce sous-arbre gauche. Une dernière comparaison nous permet de vérifier que
4 est la racine de ce sous-arbre, et est bien présent dans l’arbre. Il nous a fallu 3
comparaisons, ce qui correspond aussi au nombre de niveaux testés : la racine, puis
un enfant et un petit-enfant de la racine.
Supposons maintenant que nous cherchions la valeur 8. Nous allons toujours
comparer cette valeur à la clé à la racine, 7 : 8 > 7, donc nous allons vers le fils
droit. Sa propre racine contient la clé 9, plus grande que 8, donc nous regardons
dans son sous-arbre gauche. . . qui est vide ! Nous savons maintenant que 8 n’est
2 Nous donnons dans la section 1.2.5 une définition plus rigoureuse des arbres binaires de
recherche.
3 Les arbres sont dessinés dans le plan, ordonnés de gauche à droite par ordre croissant.