Chapitre 3
Arbres, algorithmes et données
Ce chapitre paraîtra peut-être moins formalisé que d’autres ; cela nous a semblé
nécessaire pour aller vers des préoccupations pratiques algorithmiques. Nous
regardons dans ce chapitre les arbres en tant que modèles de diverses situations
algorithmiques : le premier exemple naturel est la représentation d’expressions de
divers types, que nous abordons en section 3.1. Nous nous tournons ensuite vers
les algorithmes fondamentaux de l’informatique que sont la recherche d’une clé (en
section 3.2) et le tri d’un ensemble de valeurs (en section 3.3). Avec les paramètres
d’arbre, que nous avons présentés en section 1.3, nous avons les outils pour analyser
les performances (ou complexités) de ces algorithmes, qui utilisent directement des
arbres. Nous terminons en présentant dans la section 3.4 des problèmes issus de
différents domaines de l’informatique, et dont la modélisation ou l’analyse font
intervenir des structures arborescentes sous-jacentes.
Rappelons que nous avons choisi de parler de marques ou de clés plutôt que
de données, pour les quantités contenues dans les nœuds d’un arbre. Lorsque des
paramètres d’arbre apparaissent dans ce chapitre, ils peuvent être définis pour un
arbre fixé τ , sans qu’il soit nécessairement question d’aléa. Lorsque l’arbre devient
aléatoire ou bien contient des clés aléatoires, les paramètres d’arbre deviennent eux
aussi des variables aléatoires.
Les définitions des arbres rencontrés dans ce chapitre ont été données dans le
chapitre 1 ; les algorithmes sont rappelés dans l’annexe A.
3.1 Représentation d’expressions
Les arbres apparaissent spontanément dans certaines situations : pensons aux arbres
généalogiques d’ascendants ou de descendants (qui sont parfois des graphes, pour
peu qu’il y ait eu des mariages entre cousins !), ou aux répertoires de fichiers
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_3
61
Arbres, algorithmes et données
Ce chapitre paraîtra peut-être moins formalisé que d’autres ; cela nous a semblé
nécessaire pour aller vers des préoccupations pratiques algorithmiques. Nous
regardons dans ce chapitre les arbres en tant que modèles de diverses situations
algorithmiques : le premier exemple naturel est la représentation d’expressions de
divers types, que nous abordons en section 3.1. Nous nous tournons ensuite vers
les algorithmes fondamentaux de l’informatique que sont la recherche d’une clé (en
section 3.2) et le tri d’un ensemble de valeurs (en section 3.3). Avec les paramètres
d’arbre, que nous avons présentés en section 1.3, nous avons les outils pour analyser
les performances (ou complexités) de ces algorithmes, qui utilisent directement des
arbres. Nous terminons en présentant dans la section 3.4 des problèmes issus de
différents domaines de l’informatique, et dont la modélisation ou l’analyse font
intervenir des structures arborescentes sous-jacentes.
Rappelons que nous avons choisi de parler de marques ou de clés plutôt que
de données, pour les quantités contenues dans les nœuds d’un arbre. Lorsque des
paramètres d’arbre apparaissent dans ce chapitre, ils peuvent être définis pour un
arbre fixé τ , sans qu’il soit nécessairement question d’aléa. Lorsque l’arbre devient
aléatoire ou bien contient des clés aléatoires, les paramètres d’arbre deviennent eux
aussi des variables aléatoires.
Les définitions des arbres rencontrés dans ce chapitre ont été données dans le
chapitre 1 ; les algorithmes sont rappelés dans l’annexe A.
3.1 Représentation d’expressions
Les arbres apparaissent spontanément dans certaines situations : pensons aux arbres
généalogiques d’ascendants ou de descendants (qui sont parfois des graphes, pour
peu qu’il y ait eu des mariages entre cousins !), ou aux répertoires de fichiers
© Springer Nature Switzerland AG 2018
B. Chauvin et al., Arbres pour l’Algorithmique, Mathématiques et Applications 83,
https://doi.org/10.1007/978-3-319-93725-0_3
61