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 du tp 7 dans un nouveau répertoire. Vous pouvez implémenter les nouvelles fonctions dans les fichiers tree.h et tree.c ou rajouter des fichiers bst.h et bst.c. Si besoin, changer le Makefile (par exemple pour compiler tp08.c au lieu de tp07.c). Utiliser la fonction de visualisation write_tree 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.

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

1. Écrire une fonction récursive node *find_bst_rec(tree t, int val) qui recherche l'élément val dans l'arbre t. Elle renvoie l'adresse du noeud contenant l'élément s'il est présent, NULL sinon.
2. Écrire la même fonction en itérative.

Écrire une fonction itérative node *insert_bst(tree *t, int val) qui effectue l'insertion de l'élément val dans l'arbre binaire de recherche *t. 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.

Créer un programme principal qui implémente un menu pour que l'utilisateur puisse construire un arbre en donnant des commandes. Pour l'instant ce menu doit contenir des choix pour :

1. afficher les choix possibles ;
2. insérer une valeur dans l'arbre (par exemple en tapant `i 18') ;
3. faire une recherche dans l'arbre (par exemple en tapant `f 42') ;
4. terminer le programme.

Utiliser la fonction write_tree pour redessiner l'arbre après chaque mise à jour.

Un exemple de l'utilisation des fonctions write_tree et insert_bst :

  tree t = NULL;
  write_tree(t);
  system("evince current-tree.pdf &");

  while (1) {
    int x;
    printf("insert a value: ");
    scanf("%d", &x);
    insert_bst(&t, x);
    write_tree(t);
  }

1. Écrire une fonction itérative node *extract_min_bst(tree *t) qui effectue l'extraction du noeud contenant la plus petite étiquette de l'arbre binaire de recherche *t. 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 node *extract_bst(tree *t, int val) 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 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 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 ?