1.2 Arbres marqués
23
Fig. 1.21 Un arbre binaire
de recherche construit sur
l’ensemble des clés
{0,3 ; 0,1 ; 0,4 ; 0,15 ; 0,9 ; 0,02 ; 0,2}
Fig. 1.22 L’arbre de la
figure 1.21, complété par les
possibilités d’insertion
Par conséquent, les deux sous-arbres de tout nœud de l’arbre sont eux-mêmes des
arbres binaires de recherche et la définition récursive suivante est équivalente.
Définition 1.31 (récursive) Un arbre binaire de recherche est soit l’arbre vide, soit
un arbre binaire non vide dont les marques sont prises dans un ensemble totalement
ordonné ; dans ce cas, il est marqué avec une clé X à la racine, les clés du sous-arbre
gauche sont toutes inférieures ou égales à X, les clés du sous-arbre droit sont toutes
strictement supérieures à X, et les deux sous-arbres de la racine sont eux-mêmes
des arbres binaires de recherche.
Comme conséquence immédiate de cette définition, nous avons la
Proposition 1.32 Le parcours symétrique 10 d’un arbre binaire de recherche fournit
les clés en ordre croissant.
Si nous complétons canoniquement l’arbre binaire (cf. section 1.1.2), nous
remarquons que les feuilles de l’arbre complété (qui ne contiennent pas de clés)
correspondent aux possibilités d’insertion d’une clé dans l’arbre. Le complété de
l’arbre de la figure 1.21 est donné dans la figure 1.22.
10 Les parcours d’arbres, et notamment le parcours symétrique, sont définis en section A.1.2.