:: Enseignements :: ESIPE :: E3INFO :: 2021-2022 :: Algorithmique ::

Arbres binaires de recherche

Le but de ce TP est de manipuler les arbres binaires de recherche. On implémente la recherche, l'insertion et la suppression.

On se base sur l'implémentation des arbres binaires réalisée la séance précédente. Recopier les fichiers du tp précédent 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. Utiliser la fonction de visualisation write_tree pour voir ce qui se passe dans l'arbre après les différentes opérations.

Exercice 1 - Arbres binaires de recherche

Écrire une fonction récursive ou itérative node *find_bst(node *t, int elt) qui recherche l'élément elt dans l'arbre t. Elle renvoie l'adresse du noeud contenant l'élément s'il est présent, NULL sinon.
Pour tester votre fonction, vous pouvez utiliser la fonction scan_tree de la séance précédente. L'arbre codé par la suite d'entiers suivante est un arbre binaire de recherche :
```
20 13 8 7 0 0 11 0 0 16 0 0 23 21 0 0 27 0 0
```
Ensuite, pour vérifier que la fonction find_bst marche bien dans cet arbre, vous pouvez exécuter la boucle suivante :
```
int i;
for (i = 0; i < 100; i++)
   if (find_bst(t, i))
      printf("%d ", i);
printf("\n");
```

Exercice 2 - Insertion

É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.

Exercice 3 - Menu

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 :

afficher les choix possibles ;
construire un nouvel arbre à partir d'une suite d'entiers (par exemple en tapant `s 7 5 0 0 12 10 0 0 0')
construire un arbre avec un nombre d'entiers aléatoires : (par exemple en tapant `a 500') ;
insérer un élément dans l'arbre (par exemple en tapant `i 18') ;
faire une recherche dans l'arbre (par exemple en tapant `f 42') ;
afficher les entiers de l'arbre triés en ordre croissant (parcours en ordre infixe de l'arbre).
terminer le programme.

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

Utiliser scanf(" %c", &ch) pour lire le caractère d'une commande. L'espace initiale évite un problème courant : si on donne deux commandes à la suite, la deuxième fois, scanf("%c", &ch) (sans espace initiale) va lire le caractère EOL (newline) de la première commande.

Exercice 4 - Chronométrage

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 ?
Répondre à la même question en insérant les entiers 1, 2, ..., N en ordre.

Exercice 5 - Suppression

É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.
Écrire une fonction récursive ou itérative node *remove_bst(node *t, int elt) qui supprime le noeud contenant l'élément elt de l'arbre binaire de recherche t. La fonction renvoie un pointeur sur la racine de l'arbre après la suppression ou NULL si l'arbre est devenu vide. Si elt n'est pas présent, la fonction ne modifie rien.
Ajouter au menu un chiox pour supprimer un entier donné (par exemple en tapant `r 42').
Effectuer des tests pour vous assurer que la fonction est correcte. Par exemple, vous pouvez insérer 500 entiers aléatoires entre 0 et 499 et ensuite supprimer 200 entiers aléatoires entre 0 et 999. L'arbre résultant doit rester un arbre binaire de recherche.

Exercice 6 - Concordance revisitée

Modifier votre structure node pour qu'elle stocke comme clé une chaîne de caractères (char *word) au lieu d'un entier (int data). Modifier la fonction create_node pour quelle recopie la chaîne de caractères passée en argument :

node *create_node(char *word) {
    node *new_node = (node *)malloc(sizeof(node));
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->word = (char *)malloc((strlen(word)+1)*sizeof(char));
    strcpy(new_node->word, word);
    return new_node;
}

Pour comparer deux chaînes de caractères vous pouvez utiliser les fonctions suivantes :

int equal(char *s1, char *s2) {
    return strcmp(s1, s2) == 0;
}

int less(char *s1, char *s2) {
    return strcmp(s1, s2) < 0;
}

Dans la fonction main, lire un fichier de texte et stocker les mots dans l'arbre :

    FILE *f = ...
    node *t = NULL;
    char word[MAX_WORD_LENGTH+1];
    while (fscanf(f, "%s ", word) != -1) {
        t = insert_bst(t, word);
    }
    ...

Écrire une fonction qui affiche tous les mots du texte en ordre lexicographique.
Écrire une fonction qui affiche tous les mots du texte entre deux mots passés en arguments.
[FACULTATIF] Comparer la hauteur de l'arbre créé avec le cas idéal. (Rappelez-vous que la meilleure hauteur possible d'un arbre de n noeuds est de log2(n+1)-1.)
[FACULTATIF] Écrire un programme qui lit deux fichiers de texte et qui affiche tous les mots de l'un qui ne sont pas présents dans l'autre.