Cette feuille d'exercice a pour but de rappeler le principe, la structure et le fonctionnement des arbres binaires de recherche.
Un arbre binaire de recherche est organisé comme un arbre binaire classique, avec une clé à chaque noeud ainsi qu'un fils gauche et un fils droit (pour certaines opérations, il est nécessaire de disposer d'un accès au père de chaque noeud), mais qui possède la particularité intéressante suivante: toutes les valeurs des clés situées dans le sous-arbre gauche sont inférieures ou égales à la valeur de la clé de la racine, et toutes les valeurs des clés situées dans le sous-arbre droit sont supérieures ou égales à la valeur de la clé de la racine. Cette propriété est valable pour tous les noeuds de l'arbre.
Cette propriété permet d'obtenir aisément (par un parcours infixe de l'arbre) les valeurs de toutes les clés stockées dans l'ordre croissant.
Exercice 1 - Intuition
Dessiner des arbres binaires de recherche de hauteur 2,3,4,5 et 6 pour le même ensemble de valeurs de clés {1,4,5,10,16,17,21}.
Exercice 2 - Ordre de grandeur
Quel est l'ordre de grandeur de la complexité des opérations suivantes:
Exercice 3 - Recherche
Écrire une fonction de recherche d'une clé particulière dans un arbre binaire de recherche après avoir défini la structure de données Abr. Cette fonction retournera un pointeur sur le noeud contenant la valeur recherchée, ou NULL si aucun noeude ne contient cette valeur. Donnez une version récurisve et une version itérative de la fonction de recherche.
Exercice 4 - Minimum et maximum
Écrire les fonctions permettant d'atteindre les noeuds contenant la plus petite et la plus grande des clés.
Exercice 5 - Successeur et prédecesseur
On peut vouloir connaître la clé présente dans l'arbre immédiatement
supérieure (successeur) ou immédiatement inférieure (prédecesseur) à
la clé d'un noeud donné. Écrire une fonction successeur
qui accepte en argument un pointeur sur un noeud n
et qui
retourne le pointeur sur le noeud contenant la clé immédiatement
supérieure (dans l'arbre) à celle de n
. La fonction
predecesseur
est symétrique.
Remarque: aucune comparaison entre les clés n'est réalisée par
ces fonctions.
Exercice 6 - Insertion et suppression
Écrire une fonction permettant d'insérer une nouvelle valeur dans un arbre binaire de recherche.
Que pensez vous de l'affirmation suivante?
Si un noeud d'un arbre bianire de recherche possède deux fils,
alors son successeur n'a pas de fils gauche et son prédecesseur n'a
pas de fils droit.
Réfléchir aux problèmes qui peuvent être posés par la suppression d'un noeud dans un arbre binaire de recherche et déduire de l'affirmation précédente une fonction réalisant une telle suppression.