Arbres binaires de recherche

On se base sur l'implémentation des arbres binaires réalisée la séance précédente. Recopier les fichiers arbre.h et arbre.c dans un nouveau répertoire. Toutes les fonctions implémentées dans ce TP doivent être rajoutées à ces deux fichiers. Utiliser les fonctions de visualisation pour voir ce qui se passe dans l'arbre après les différentes opérations. On suppose pour tout le TP qu'il n'y a pas de doublons dans les arbres.

1. Pour tester vos fonctions, vous pouvez utiliser l'arbre codé comme suit :

   20 13 8 7 0 0 11 0 0 16 0 0 23 21 0 0 27 0 0

2. Écrire une fonction récursive Noeud *rechercherRec(Arbre arb, int elt) qui recherche l'élément elt dans l'arbre arb. Elle renvoie l'adresse du noeud contenant l'élément s'il est présent, NULL sinon.
3. Écrire la même fonction en itérative.

Écrire une fonction itérative Noeud *inserer(Arbre *arb, int elt) qui effectue l'insertion de l'élément elt dans l'arbre binaire de recherche *arb. La fonction renvoie l'adresse du noeud inseré si l'élément n'existe pas déjà dans l'arbre. S'il y a déjà un noeud dans l'arbre contenant l'élément, la fonction renvoie son adresse. En cas d'échec, la fonction renvoie NULL.

1. Écrire une fonction itérative Noeud *extraireMin(Arbre *arb) qui effectue l'extraction du noeud contenant la plus petite étiquette de l'arbre binaire de recherche *arb. Elle renvoie l'adresse du noeud correspondant et NULL en cas d'échec, et l'arbre devra être modifié en conséquence.
   
   Que faut-il changer pour extraire le noeud contenant la plus grande étiquette?
2. Écrire une fonction itérative Noeud *extraire(Arbre *arb, int elt) qui effectue l'extraction du noeud contenant une étiquette donnée d'un arbre binaire de recherche. Elle renvoie l'adresse du noeud et NULL en cas d'échec.

Écrire une fonction récursive qui détermine si un arbre est un arbre binaire de recherche (elle retourne 1 si c'en est un et 0 sinon). On prendra soin de ne pas faire de parcours inutile de l'arbre.

1. Créer une fonction main qui insère N entiers aléatoires (entre 0 et 2*N, par exemple) dans un arbre.
   Mesurer le temps utilisé et la hauteur de l'arbre créé.
   Combien d'éléments pouvez-vous insérer en 10 secondes ?
   Combien de pointeurs faut-il suivre au pire des cas pour faire une recherche ?
2. Répondre à la même question en insérant les entiers 1, 2, ..., N en ordre.
3. Prendre l'implémentation des listes chainées triées du TP 6 (lien) et la changer pour qu'elle stocke des entiers au lieu des mots. (Il suffit de réécrire les définitions de types, l'allocation d'une cellule et l'insertion à place.) Comme pour les arbres, vous ne stockez pas de doublons dans les listes. Créer une fonction main qui insère N entiers aléatoires dans une liste.
   Mesurer le temps utilisé et la longueur de la liste créée.
   Combien d'éléments pouvez-vous insérer en 10 secondes ?
   Combien de pointeurs faut-il suivre au pire des cas pour faire une recherche ?