3.2 Recherche de clés
63
Fig. 3.2 Arbres d’expressions pour l’expression (3 ∗ (1 − 4)) + x construite sur les opérateurs
arithmétiques binaires usuels {+, −, ∗, /} , et pour l’expression exp(x∗x)+(x∗(x+x)) représentée
par un arbre non binaire, l’opérateur EXP étant d’arité 1
La représentation d’une expression par un arbre est utilisée, entre autres, pour
les expressions arithmétiques utilisées dans un système de calcul formel, et permet
d’effectuer facilement des opérations telles que l’addition et la multiplication, ou la
différentiation, le résultat étant représenté par un autre arbre ; nous revenons sur ce
point dans la section 4.2.5.
3.2 Recherche de clés
Dans nombre de situations couramment rencontrées en informatique, les informations à traiter sont représentées par des éléments structurés en plusieurs champs : par
exemple, les informations correspondant à une personne donnée seront regroupées
dans un seul élément (dit aussi enregistrement ou article) et comprendront ses nom,
prénom, adresse, date de naissance, et un identificateur unique tel que, en France,
le numéro d’inscription au répertoire des personnes physiques (couramment appelé
« numéro de sécurité sociale »). Selon les cas, c’est l’un ou l’autre des champs qui
sera pertinent : parfois le nom, si nous cherchons toutes les personnes portant le
nom de Dupont ; parfois l’identificateur, lorsque nous connaissons celui associé à
une personne et cherchons à retrouver toutes les informations la concernant. Nous
faisons alors une recherche sur un champ donné, qui est la clé, et les autres champs
n’interviennent pas dans cette recherche.
Pour les besoins de la présentation qui suit, nous réduisons donc un élément
à sa clé que nous supposons appartenir à un ensemble totalement ordonné. Ceci
s’applique aux arbres binaires de recherche, que nous présentons en section 3.2.1, et
qui sont sans doute la structure arborescente la plus classique permettant de stocker
des clés et de les retrouver, lorsque les opérations permises sont les comparaisons
de clés ; on parle alors de recherche par valeur, par opposition à d’autres types
de recherche comme la recherche par rang, où il s’agit de trouver une clé de rang
donné, par exemple la plus petite, ou la sixième en ordre décroissant.
Ceci s’applique aussi à d’autres structures arborescentes qui étendent les arbres
binaires de recherche, soit en tirant parti d’une structure multi-dimensionnelle des
63
Fig. 3.2 Arbres d’expressions pour l’expression (3 ∗ (1 − 4)) + x construite sur les opérateurs
arithmétiques binaires usuels {+, −, ∗, /} , et pour l’expression exp(x∗x)+(x∗(x+x)) représentée
par un arbre non binaire, l’opérateur EXP étant d’arité 1
La représentation d’une expression par un arbre est utilisée, entre autres, pour
les expressions arithmétiques utilisées dans un système de calcul formel, et permet
d’effectuer facilement des opérations telles que l’addition et la multiplication, ou la
différentiation, le résultat étant représenté par un autre arbre ; nous revenons sur ce
point dans la section 4.2.5.
3.2 Recherche de clés
Dans nombre de situations couramment rencontrées en informatique, les informations à traiter sont représentées par des éléments structurés en plusieurs champs : par
exemple, les informations correspondant à une personne donnée seront regroupées
dans un seul élément (dit aussi enregistrement ou article) et comprendront ses nom,
prénom, adresse, date de naissance, et un identificateur unique tel que, en France,
le numéro d’inscription au répertoire des personnes physiques (couramment appelé
« numéro de sécurité sociale »). Selon les cas, c’est l’un ou l’autre des champs qui
sera pertinent : parfois le nom, si nous cherchons toutes les personnes portant le
nom de Dupont ; parfois l’identificateur, lorsque nous connaissons celui associé à
une personne et cherchons à retrouver toutes les informations la concernant. Nous
faisons alors une recherche sur un champ donné, qui est la clé, et les autres champs
n’interviennent pas dans cette recherche.
Pour les besoins de la présentation qui suit, nous réduisons donc un élément
à sa clé que nous supposons appartenir à un ensemble totalement ordonné. Ceci
s’applique aux arbres binaires de recherche, que nous présentons en section 3.2.1, et
qui sont sans doute la structure arborescente la plus classique permettant de stocker
des clés et de les retrouver, lorsque les opérations permises sont les comparaisons
de clés ; on parle alors de recherche par valeur, par opposition à d’autres types
de recherche comme la recherche par rang, où il s’agit de trouver une clé de rang
donné, par exemple la plus petite, ou la sixième en ordre décroissant.
Ceci s’applique aussi à d’autres structures arborescentes qui étendent les arbres
binaires de recherche, soit en tirant parti d’une structure multi-dimensionnelle des