Arbres binaires de recherche

Informatique - Deug S4 MIAS

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.