1.2 Arbres marqués
27
Fig. 1.26 La partition de l’ensemble des marques, induite par les clés x 1 , . . . , x p d’un nœud
dans un arbre de recherche
1.2.6 Arbres de recherche
Nous venons de voir les arbres binaires de recherche, dont il existe plusieurs généralisations. Il est possible de donner une définition générale, que nous désignons sous
le nom global d’« arbre de recherche », pour exprimer la propriété qu’ont ces arbres
de partitionner dans les sous-arbres les intervalles déterminés sur l’ensemble des
marques par des clés ordonnées ; cf. la figure 1.26.
Définition 1.34 Un arbre de recherche est soit l’arbre vide, soit un arbre planaire
dont chaque nœud est marqué par un sous-ensemble non vide et fini de clés prises
dans un ensemble totalement ordonné . Un nœud « contient » les clés du sousensemble qui le marque. Si la racine contient p clés x 1 , . . . , x p (p ≥ 1), elle a p + 1
sous-arbres, qui peuvent éventuellement être vides ; ces clés induisent une partition
{ 1 , . . . , , p+1 } de , telle que le i-ième sous-arbre de la racine soit marqué par les
clés de i ; enfin ces sous-arbres sont eux-mêmes des arbres de recherche.
Les possibilités d’insertion dans un arbre de recherche peuvent être représentées
en complétant l’arbre par des , comme pour les arbres binaires de recherche, mais
en généralisant : si une feuille contient k clés, il y a k + 1 possibilités d’insertion.
Voir par exemple la figure 1.28.
Remarque 1.35 Il est possible de représenter un arbre de recherche
– soit avec seulement des nœuds (internes et externes) contenant les clés, comme
dans la figure 1.24, c’est le choix que nous avons fait dans la définition 1.34 ;
– soit en le complétant avec les possibilités d’insertion (gaps en anglais), comme
dans les figures 1.23 et 1.28. Les nœuds externes précédents deviennent des
nœuds internes terminaux.
Nous présenterons en section 8.1 les arbres m-aires de recherche, dans lesquels
l’arité d’un nœud interne n’est plus deux ; elle reste cependant bornée et les nœuds
internes terminaux sont d’arité variable. C’est un exemple d’école, qui permet de
récapituler les méthodes vues pour les arbres binaires de recherche. Comme l’intérêt
algorithmique des arbres m-aires de recherche est assez faible, nous reportons leur
présentation et leur étude au chapitre 8.
Dans la suite de cette section, nous présentons les arbres 2-3 de recherche, où
toutes les feuilles sont au même niveau – une telle contrainte requiert d’autoriser un
27
Fig. 1.26 La partition de l’ensemble des marques, induite par les clés x 1 , . . . , x p d’un nœud
dans un arbre de recherche
1.2.6 Arbres de recherche
Nous venons de voir les arbres binaires de recherche, dont il existe plusieurs généralisations. Il est possible de donner une définition générale, que nous désignons sous
le nom global d’« arbre de recherche », pour exprimer la propriété qu’ont ces arbres
de partitionner dans les sous-arbres les intervalles déterminés sur l’ensemble des
marques par des clés ordonnées ; cf. la figure 1.26.
Définition 1.34 Un arbre de recherche est soit l’arbre vide, soit un arbre planaire
dont chaque nœud est marqué par un sous-ensemble non vide et fini de clés prises
dans un ensemble totalement ordonné . Un nœud « contient » les clés du sousensemble qui le marque. Si la racine contient p clés x 1 , . . . , x p (p ≥ 1), elle a p + 1
sous-arbres, qui peuvent éventuellement être vides ; ces clés induisent une partition
{ 1 , . . . , , p+1 } de , telle que le i-ième sous-arbre de la racine soit marqué par les
clés de i ; enfin ces sous-arbres sont eux-mêmes des arbres de recherche.
Les possibilités d’insertion dans un arbre de recherche peuvent être représentées
en complétant l’arbre par des , comme pour les arbres binaires de recherche, mais
en généralisant : si une feuille contient k clés, il y a k + 1 possibilités d’insertion.
Voir par exemple la figure 1.28.
Remarque 1.35 Il est possible de représenter un arbre de recherche
– soit avec seulement des nœuds (internes et externes) contenant les clés, comme
dans la figure 1.24, c’est le choix que nous avons fait dans la définition 1.34 ;
– soit en le complétant avec les possibilités d’insertion (gaps en anglais), comme
dans les figures 1.23 et 1.28. Les nœuds externes précédents deviennent des
nœuds internes terminaux.
Nous présenterons en section 8.1 les arbres m-aires de recherche, dans lesquels
l’arité d’un nœud interne n’est plus deux ; elle reste cependant bornée et les nœuds
internes terminaux sont d’arité variable. C’est un exemple d’école, qui permet de
récapituler les méthodes vues pour les arbres binaires de recherche. Comme l’intérêt
algorithmique des arbres m-aires de recherche est assez faible, nous reportons leur
présentation et leur étude au chapitre 8.
Dans la suite de cette section, nous présentons les arbres 2-3 de recherche, où
toutes les feuilles sont au même niveau – une telle contrainte requiert d’autoriser un