22
1 Botanique
Fig. 1.20 Un arbre récursif
τ et l’arbre des rangs C(τ )
obtenu par marquage
canonique
Nous introduisons maintenant une classe différente d’arbres croissants, les arbres
récursifs.
Définition 1.28 Un arbre récursif est un arbre marqué non planaire croissant.
Les arbres récursifs peuvent être représentés (dans le plan !) en ordonnant les
sous-arbres d’un nœud par marques croissantes de leurs racines ; cf. la figure 1.20.
Cela revient à choisir, parmi tous les arbres planaires correspondant à un arbre
récursif donné, un représentant standard.
Remarque 1.29 Lorsque toutes les marques sont distinctes, un arbre récursif a un
arbre des rangs au sens de la définition 1.16. Le marquage canonique d’un tel arbre
récursif donne alors pour arbre des rangs un arbre de Cayley croissant.
1.2.5 Arbres binaires de recherche
Les arbres binaires de recherche sont des arbres binaires dont les nœuds contiennent
des clés, de telle sorte que ces clés soient faciles à rechercher, à comparer, à
insérer. Voici un tel arbre dans la figure 1.21, pour introduire les deux définitions
équivalentes qui suivent.
Définition 1.30 Un arbre binaire de recherche est soit l’arbre vide, soit un arbre
binaire marqué par des clés prises dans un ensemble totalement ordonné, de sorte
que, pour tout nœud interne u, les clés du sous-arbre gauche (resp. droit) de u,
lorsqu’il n’est pas vide, soient inférieures ou égales (resp. supérieures) à celle de u.
1 Botanique
Fig. 1.20 Un arbre récursif
τ et l’arbre des rangs C(τ )
obtenu par marquage
canonique
Nous introduisons maintenant une classe différente d’arbres croissants, les arbres
récursifs.
Définition 1.28 Un arbre récursif est un arbre marqué non planaire croissant.
Les arbres récursifs peuvent être représentés (dans le plan !) en ordonnant les
sous-arbres d’un nœud par marques croissantes de leurs racines ; cf. la figure 1.20.
Cela revient à choisir, parmi tous les arbres planaires correspondant à un arbre
récursif donné, un représentant standard.
Remarque 1.29 Lorsque toutes les marques sont distinctes, un arbre récursif a un
arbre des rangs au sens de la définition 1.16. Le marquage canonique d’un tel arbre
récursif donne alors pour arbre des rangs un arbre de Cayley croissant.
1.2.5 Arbres binaires de recherche
Les arbres binaires de recherche sont des arbres binaires dont les nœuds contiennent
des clés, de telle sorte que ces clés soient faciles à rechercher, à comparer, à
insérer. Voici un tel arbre dans la figure 1.21, pour introduire les deux définitions
équivalentes qui suivent.
Définition 1.30 Un arbre binaire de recherche est soit l’arbre vide, soit un arbre
binaire marqué par des clés prises dans un ensemble totalement ordonné, de sorte
que, pour tout nœud interne u, les clés du sous-arbre gauche (resp. droit) de u,
lorsqu’il n’est pas vide, soient inférieures ou égales (resp. supérieures) à celle de u.