64
3 Arbres, algorithmes et données
Fig. 3.3 La structuration des
clés induite par la marque de
la racine dans un arbre binaire
de recherche
clés, soit en allant au-delà de la forme d’arbre binaire, mais en restant toujours dans
le cas où les opérations permises sont les comparaisons de clés. C’est ainsi que la
définition des arbres binaires de recherche s’étend à des arbres non binaires, ce sont
les diverses variétés d’arbres de recherche définies à la section 1.2.6 et que nous
reprenons dans la section 3.2.2. Enfin nous nous intéressons dans la section 3.2.3
aux arbres digitaux, qui peuvent eux aussi être utilisés pour organiser des clés du
type adéquat, en vue de recherches.
3.2.1 Arbres binaires de recherche
Les arbres binaires de recherche ont été définis à la section 1.2.5 ; nous en rappelons
le principe ci-dessous (cf. la figure 3.3).
Un arbre binaire de recherche τ est soit vide, soit tel que, si x est la marque de sa racine,
toutes les clés du sous-arbre gauche de τ sont inférieures ou égales à x, toutes les clés du
sous-arbre droit sont strictement supérieures à x, et ces deux sous-arbres sont eux-mêmes
des arbres binaires de recherche.
Ceci correspond à une structuration de l’ensemble des clés par rapport à l’une
d’entre elles : la clé x marquant la racine, qui divise cet ensemble en deux sousensembles eux-mêmes structurés récursivement de la même manière.
Les opérations de base du point de vue algorithmique sont
– l’insertion d’une nouvelle clé α dans τ ;
– la recherche d’une clé α dans τ ; cette recherche est réussie (ou avec succès)
quand α est présente dans τ ; elle est vaine (ou sans succès) quand α n’est
pas présente et elle se termine alors sur une feuille du complété ˜
τ de τ (cf. la
figure 3.4) ;
– la suppression d’une clé α présente dans l’arbre.
Nous avons donné dans le chapitre d’introduction une idée des algorithmes
standard de recherche et d’insertion ; les algorithmes détaillés sont donnés respectivement dans les annexes A.2.1 et A.2.2. 3 Chacune de ces opérations s’effectue
3 Nous considérons dans le reste de cette partie que l’insertion d’une nouvelle clé se fait toujours
en créant de nouvelles feuilles. Il existe des variantes, notamment celle qui consiste à insérer
une nouvelle clé à la racine, et qui est en particulier utilisée pour obtenir les arbres binaires de
3 Arbres, algorithmes et données
Fig. 3.3 La structuration des
clés induite par la marque de
la racine dans un arbre binaire
de recherche
clés, soit en allant au-delà de la forme d’arbre binaire, mais en restant toujours dans
le cas où les opérations permises sont les comparaisons de clés. C’est ainsi que la
définition des arbres binaires de recherche s’étend à des arbres non binaires, ce sont
les diverses variétés d’arbres de recherche définies à la section 1.2.6 et que nous
reprenons dans la section 3.2.2. Enfin nous nous intéressons dans la section 3.2.3
aux arbres digitaux, qui peuvent eux aussi être utilisés pour organiser des clés du
type adéquat, en vue de recherches.
3.2.1 Arbres binaires de recherche
Les arbres binaires de recherche ont été définis à la section 1.2.5 ; nous en rappelons
le principe ci-dessous (cf. la figure 3.3).
Un arbre binaire de recherche τ est soit vide, soit tel que, si x est la marque de sa racine,
toutes les clés du sous-arbre gauche de τ sont inférieures ou égales à x, toutes les clés du
sous-arbre droit sont strictement supérieures à x, et ces deux sous-arbres sont eux-mêmes
des arbres binaires de recherche.
Ceci correspond à une structuration de l’ensemble des clés par rapport à l’une
d’entre elles : la clé x marquant la racine, qui divise cet ensemble en deux sousensembles eux-mêmes structurés récursivement de la même manière.
Les opérations de base du point de vue algorithmique sont
– l’insertion d’une nouvelle clé α dans τ ;
– la recherche d’une clé α dans τ ; cette recherche est réussie (ou avec succès)
quand α est présente dans τ ; elle est vaine (ou sans succès) quand α n’est
pas présente et elle se termine alors sur une feuille du complété ˜
τ de τ (cf. la
figure 3.4) ;
– la suppression d’une clé α présente dans l’arbre.
Nous avons donné dans le chapitre d’introduction une idée des algorithmes
standard de recherche et d’insertion ; les algorithmes détaillés sont donnés respectivement dans les annexes A.2.1 et A.2.2. 3 Chacune de ces opérations s’effectue
3 Nous considérons dans le reste de cette partie que l’insertion d’une nouvelle clé se fait toujours
en créant de nouvelles feuilles. Il existe des variantes, notamment celle qui consiste à insérer
une nouvelle clé à la racine, et qui est en particulier utilisée pour obtenir les arbres binaires de