TP5 Informatique - Deug S4 MIAS

TP5 Arbres Binaires de Recherche

ABR

Informatique - Licence 2.2

Cette feuille d'exercice a pour but de vous faire manipuler la structure de donnée des ABRs. La définition d'un ABR est un arbre binaire tel que la valeur stockée dans chaque sommet est supérieure à celles stockées dans son sous-arbre gauche et inferieure à celles de son sous-arbre droit. Durant tous le td nous nous contanterons de stoquer des entiers dans chaques noeuds.

Exercice 1 - Structure de l'arbre binaire

Déterminez la structure de l'ABR.

Écrire les fonctions : Cellule* alloueCellule(int valeur) qui alloue une cellule de l'arbre et initialise ses champs, int libereCellule(Cellule * cel) qui libére l'espace réservé pour cel.

Exercice 2 - Insertion, recherche dans un ABR

En respectant la définition d'un ABR, écrire la fonction d'insertion d'un entier int insertionABR(ABR* abr, int valeur).
Écrire l'algorithme de recherche d'une valeur dans un ABR, int recherche(ABR abr, int valeur) qui retourne 1 si la valeur est trouvée.
Puis déterminez qu'elle est la compléxité de ces deux algorithmes.

Exercice 3 - Suppression dans un ABR

Réalisez l'algorithme de suppression dans un ABR. Attention l'arbre aprés suppression doit toujours respecter les propriétées des ARB.

Exercice 4 - Parcourt d'ABR.

Réalisez la fonction qui affiche les valeurs contenue dans l'arbre dans l'ordre croissant.

Exercice 5 - Algorithme de tris

Utilisez l'ABR pour réaliser un algorithme de tris. En réfléchisant sur le compléxité de l'algorithme d'insertion et de suppression, déterminé la compléxité de cette algorithme.