Structures de données hiérarchiques

Notions	Commentaires
Définition inductive du type arbre binaire. Vocabulaire : nœud, nœud interne, racine, feuille, fils, père, hauteur d’un arbre, profondeur d’un nœud, étiquette, sous-arbre.	La hauteur de l’arbre vide est−1. On mentionne la représentation d’un arbre complet dans un tableau.
Arbre. Conversion d’un arbre d’arité quelconque en un arbre binaire.	La présentation donne lieu à des illustrations au choix du professeur. Il peut s’agir par exemple d’expressions arithmétiques, d’arbres préfixes ( trie ), d’arbres de décision, de dendrogrammes, d’arbres de classification, etc.
Parcours d’arbre. Ordre préfixe, infixe et postfixe.	On peut évoquer le lien avec l’empilement de blocs d’activation lors de l’appel à une fonction récursive.
Implémentation d’un tableau associatif par un arbre binaire de recherche. Arbre bicolore.	On note l’importance de munir l’ensemble des clés d’un ordre total.
Propriété de tas. Structure de file de priorité implémentée par un arbre binaire ayant la propriété de tas.	Tri par tas.
Structure unir & trouver pour la représentation des classes d’équivalence d’un ensemble. Implémentation par des arbres.	On commence par donner des implémentations naïves de la structure unir trouver qui privilégient soit l’opération unir, soit l’opération trouver, avant de donner une implémentation par des arbres qui permet une mise en œuvre efficace des deux opérations. L’analyse de la complexité de cette structure est admise.

On présente les manipulations usuelles sur les arbres en C et en OCaml. Il n’est pas attendu d’un étudiant une maîtrise technique de l’écriture du code d’une structure de données arborescente mutable à l’aide de pointeurs, mais il est attendu qu’il sache l’utiliser.