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.

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(node *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 récursive ou itérative node *insert_bst(node *t, int elt) qui effectue l'insertion de l'élément elt dans l'arbre binaire de recherche t. Si l'élément elt est déjà présent, alors la fonction ne modifie rien. La fonction renvoie un pointeur sur la racine de l'arbre après l'insertion.

Créer un programme principal qui propose 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 :

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

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

1. Écrire une fonction récursive ou itérative node *extract_min_bst(node *t, node **min) qui effectue l'extraction du noeud contenant la plus petite étiquette de l'arbre binaire de recherche t. La fonction met l'adresse du noeud extrait dans *min et renvoie un pointeur sur la racine de l'arbre après la suppression.
2. Écrire une fonction récursive ou itérative node *remove_bst(node *t, int val) qui effectue l'extraction du noeud contenant une étiquette donnée d'un arbre binaire de recherche. Elle renvoie un pointeur sur la racine de l'arbre après la suppression ou NULL si l'arbre est devenu vide.

É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 vide.
   Mesurer le temps utilisé et la hauteur de l'arbre créé.
   Combien d'éléments pouvez-vous insérer en 10 secondes ?
   
2. Répondre à la même question en insérant les entiers 1, 2, ..., N en ordre.