C12 Arbres binaires

"Trees sprout up just about everywhere in computer science"
D. Knuth

Cours

Support de cours chapitre 12

Attention

Ce diaporama ne vous donne que quelques points de repères lors de vos révisions. Il devrait être complété par la relecture attentive de vos propres notes de cours et par une révision approfondie des exercices.

Travaux dirigés

Fiche de TD12

Travaux pratiques

Exercice 1 : Implémentation des arbres binaires en C

On rappelle la structure de données vue en cours et permettant de représenter une arbre binaire en C :

    struct noeud
    {
        struct noeud *sag;
        int valeur;
        struct noeud *sad;
    };
    typedef struct noeud noeud;
    typedef noeud *ab;

On donne aussi, la fonction permettant de créer un arbre binaire en donnant ses deux sous arbres et son étiquette :

    ab cree_arbre(ab g, int v, ab d)
    {
        noeud *n = malloc(sizeof(noeud));
        {
            n->sag = g;
            n->valeur = v;
            n->sad = d;
            return n;
        }
    }

1. En utilisant cette représentation, créer une variable t de type arbre binaire représentant l'arbre suivant ;
   

       graph TD
       A["14"] --> L["7"]
       A --> G["10"]
       L --> O["5"]
       L --> R["6"]
       G --- V1[" "]
       G --> I["12"]
       style V1 fill:#FFFFFF, stroke:#FFFFFF
       linkStyle 4 stroke:#FFFFFF,stroke-width:0px

   Visualisation de l'arbre

   On donne ci-dessous une fonction permettant de visualiser l'arbre.

       void write_edge(FILE *writer, ab g, int *ninv)
       {
           if (g->sag != NULL)
           {
               fprintf(writer, "%d", g->valeur);
               fprintf(writer, " -> ");
               fprintf(writer, "%d\n", g->sag->valeur);
               write_edge(writer, g->sag, ninv);
           }
           else
           {
               fprintf(writer, "I%d [style=invis]\n", *ninv);
               fprintf(writer, "%d -> I%d [style=invis]\n", g->valeur, *ninv);
               (*ninv)++;
           }
           fprintf(writer, "I%d [style=invis]\n", *ninv);
           fprintf(writer, "%d -> I%d [style=invis]\n", g->valeur, *ninv);
           (*ninv)++;
           if (g->sad != NULL)
           {
               fprintf(writer, "%d", g->valeur);
               fprintf(writer, " -> ");
               fprintf(writer, "%d\n", g->sad->valeur);
               write_edge(writer, g->sad, ninv);
           }
           else
           {
               fprintf(writer, "I%d [style=invis]\n", *ninv);
               fprintf(writer, "%d -> I%d [style=invis]\n", g->valeur, *ninv);
               (*ninv)++;
           }
       }
   
       void view(ab g)
       {
           FILE *writer = fopen("temp.gv", "w");
           int n = 0;
           fprintf(writer, "digraph mygraph {\n");
           write_edge(writer, g, &n);
           fprintf(writer, "}\n");
           fclose(writer);
           system("xdot temp.gv &");
       }
   

2. Ecrire une fonction est_vide de signature bool est_vide(ab a) permettant de tester si l'arbre donné en paramètre est vide.

3. Ecrire et tester la fonction taille de signature int taille(ab a) et qui renvoie le nombre de noeuds de l'arbre binaire donné en argument.

4. Ecrire et tester la fonction hauteur de signature int hauteur(ab a) et qui renvoie la hauteur de l'arbre binaire donné en argument.

5. Ecrire une fonction permettant detruit de signature void detruit(ab *a) qui permet de détruire un arbre binaire en libérant l'espace mémoire occupé par ses noeuds. Après l'appel à cette fonction, a est le pointeur NULL.

6. Ecrire une fonction insere_noeud de signature void insere_noeud(ab *t, int v) qui insère à un emplacement aléatoire un noeud portant l'étiquette v dans l'abre *t.

   Aide

   Pour insérer un noeud de façon aléatoire, on pourra procéder de la façon suivante :

   • Si l'arbre est vide il devient l'arbre (NULL,v,NULL)
   • Sinon on descend aléatoirement à gauche ou à droit pour y faire l'insertion.
   • On rappelle qu'en C, rand() génère un entier aléatoire entre 0 et le plus grand entier représentable
   • Une méthode possible d'initialisation du générateur aléatoire de nombre est d'utiliser le temps : srand(time(NULL)); disponible après #include <time.h>

7. Ecrire une fonction arbre_aleatoire de signature ab arbre_aleatoire(int n) qui génère un arbre binaire aléatoire de n noeuds portant comme étiquette les entiers \(0, \dots, n-1\).

   Aide

   On pourra procéder de la façon suivante :

   • générer une permutation aléatoire de \(\{0,\dots,n-1\}\) en utilisant par exemple le mélange de Fischer-Yates,
   • insérer les entiers dans l'ordre de la permutation en utilisant la fonction insere_noeud de la question précédente.

Exercice 2 : Implémentation des arbres binaires en OCaml

On rappelle l'implémentation des arbres binaires avec des étiquettes entières en OCaml vu en cours :

    type ab = 
      |Vide 
      | Noeud of ab * int * ab ;;

1. En utilisant cette représentation, créer une variable t de type ab représentant l'arbre suivant ;
   

       graph TD
       A["14"] --> L["17"]
       A --> G["9"]
       G --- V1[" "]
       L --> R["6"]
       L --- V2[" "]
       G --> I["8"]
       style V1 fill:#FFFFFF, stroke:#FFFFFF
       style V2 fill:#FFFFFF, stroke:#FFFFFF
       linkStyle 2 stroke:#FFFFFF,stroke-width:0px
       linkStyle 4 stroke:#FFFFFF,stroke-width:0px

   Visualisation de l'arbre

   On donne ci-dessous une fonction permettant de visualiser l'arbre.

       let rec write_edge a writer ninv=
         match a with
         | Vide -> ()
         | Noeud (sag,e,sad) ->
           match sag, sad with
           | Vide, Vide -> ();
           | Noeud (_, eg, _), Vide ->
             Printf.fprintf writer "%d -> %d\n" e eg;
             Printf.fprintf writer  "I%d [style=invis]\n %d -> I%d [style=invis]\n" !ninv e !ninv;
             ninv := !ninv +1;
             Printf.fprintf writer  "I%d [style=invis]\n %d -> I%d [style=invis]\n" !ninv e !ninv;
             ninv := !ninv +1;
             write_edge sag writer ninv;
           | Vide, Noeud(_,ed,_) ->
             Printf.fprintf writer  "I%d [style=invis]\n %d -> I%d [style=invis]\n" !ninv e !ninv;
             ninv := !ninv +1;
             Printf.fprintf writer  "I%d [style=invis]\n %d -> I%d [style=invis]\n" !ninv e !ninv;
             ninv := !ninv +1;
             Printf.fprintf writer "%d -> %d\n" e ed;
             write_edge sad writer ninv;
           | Noeud (_,eg,_), Noeud (_,ed, _ ) ->
             Printf.fprintf writer "%d -> %d\n" e eg;
             Printf.fprintf writer  "I%d [style=invis]\n %d -> I%d [style=invis]\n" !ninv e !ninv;
             ninv := !ninv +1;
             Printf.fprintf writer "%d -> %d\n" e ed;
             write_edge sag writer ninv;
             write_edge sad writer ninv;
       ;;
   
       let view a =
         let ninv = ref 0 in
         let outc = open_out "temp.gv" in
         output_string outc "digraph mygraph {\n";
         write_edge a outc ninv;
         output_string outc "}\n";
         close_out outc;
         ignore (Sys.command "xdot temp.gv");;
   

2. Ecrire une fonction est_vide de signature ab -> bool permettant de tester si l'arbre donné en paramètre est vide.

3. Ecrire et tester la fonction taille de signature ab -> int et qui renvoie le nombre de noeuds de l'arbre binaire donné en argument.

4. Ecrire et tester la fonction hauteur de signature ab -> int et qui renvoie la hauteur de l'arbre binaire donné en argument.

5. En utilisant la méthode de votre choix (deux sont proposées dans l'exercice précédent), écrire en OCaml une fonction arbre_alaetoire de signature int -> ab et qui renvoie un arbre aléatoire de \(n\) noeuds.

Exercice 3 : Arbre complet représenté par un tableau

Cet exercice concerne la représentation d'un arbre binaire complet de taille \(n\) par un tableau de taille \(n\) et est à traiter au choix en OCaml ou en C. Pour chaque question, le tableau tab da taille n est la représentation en machine d'un arbre binaire complet de taille n.

1. Ecrire une fonction qui pour le noeud situé à l'indice i renvoie l'indice du parent (\(-1\) pour la racine)

2. Ecrire une fonction qui pour le noeud situé à l'indice i renvoie les indices des fils gauches et droit (\(-1\) s'il n'existent pas)

3. Ecrire une fonction renvoyant la hauteur de l'arbre.

Exercice 4 : Parcours récursif en C

1. Ecrire en langage C, une fonction qui affiche les noeuds dans l'ordre :

   a. d'un parcours prefixe
   b. d'un parcours infixe
   c. d'un parcours postfixe

2. On souhaite à présent créer une liste chainée contenant les noeuds dans l'ordre du parcours préfixe

   a. Implémenter une structure de liste chainée en C dans laquelle on conservera un pointeur sur la premier élément de la liste et aussi un pointeur sur le dernier élément de la liste. De cette façon, on peut concaténer deux listes en temps constant.

   b. En utilisant cette implémentation, écrire une fonction renvoyant une liste chainée contenant les noeuds de l'arbre dans l'ordre d'un parcours prefixe.

Exercice 5 : Parcours récursif en OCaml

1. Ecrire en OCaml, en utilisant l'opérateur de concaténation @ une fonction prefixe : 'a ab -> 'a list qui renvoie le parcours préfixe de l'arbre binaire donné en argument.

2. Comme cela a été vu en td, on rappelle que le parcours précédent est de compléxité quadratique (car l'opérateur @ est de complexité linéaire par rapport à la longueur de la première liste). On cherche donc maintenant à écrire une version de complexité linéaire du parcours préfixe. d'un arbre binaire. Pour cela on propose d'écrire une fonction auxilaire prefixe_aux : 'a ab -> 'a list -> 'a list qui prend en argument un arbre binaire et une liste acc et renvoie le parcours prefixe de l'arbre suivi du contenu de acc.

   Aide

   Utiliser la fonction auxiliaire pour traduire le fait que le parcours préfixe de l'arbre (g, v, d) est v suivi du parcours préfixe de g suivi du parcours préfixe de d.

3. Réprendre le question précédentes pour le parcours infixe et pour le parcours postfixe.

Exercice 6 : Parcours en largeur en C

Ecrire une fonction de signature void largeur(ab a) qui affiche les noeuds dans l'ordre d'un parcours en largeur. Comme expliqué en cours, on peut utiliser une file qu'on pourra implémenter par exemple par une liste chainée (avec un pointeur de tête et un pointeur de queue).

Exercice 7 : Parcours en largeur en OCaml

Ecrire une fonction de signature ab -> unit qui affiche les noeuds dans l'ordre d'un parcours en largeur. Comme expliqué en cours, on peut utiliser une file qu'on pourra implémenter à l'aide du module Queue de Caml dont on rappelle ci-dessous quelques fonctions :

• Queue.create de signature unit -> 'a Queue.t qui crée une file d'attente vide, par exemple let ma_file = Queue.create ()
• Queue.is_empty de signature ('a Queue.t -> bool) qui teste si la file est vide ou non
• Queue.push de signature ('a -> 'a Queue.t -> unit) qui enfile un élément, par exemple Queue.push 10 ma_file
• Queue.pop de signature ('a Queue.t -> 'a) qui défile un élément, par exemple let elt = Queue.pop ma_file

Exercice 8 : Arbre binaire de recherche en C

Pour l'implémentation des arbres binaires de recherche en C, on reprend la structure utilisée pour les arbres binaires :

    struct noeud
    {
        struct noeud *sag;
        int valeur;
        struct noeud *sad;
    };
    typedef struct noeud noeud;
    typedef noeud *abr;

1. Ecrire une fonction insere de signature void insere(abr *t, int v) qui insère la valeur v dans l'arbre binaire t.

2. Construire et visualiser l'arbre binaire obtenu en insérant successivement les valeurs \(7, 5, 9, 2\) et \(11\).

3. Ecrire une fonction present de signature bool present(abr t, int v) qui teste l'appartenance de la valeur v à l'arbre t.

Note

Pour écrire l'implémentation de la suppression d'une clé dans un abr en C, on recommande de commencer par l’implémentation en OCaml ci-dessous.

Exercice 9 : Arbre binaire de recherche en OCaml

Pour l'implémentation des arbres binaires de recherche en OCaml, on reprend la structure utilisée pour les arbres binaires :

    type abr = 
      |Vide 
      |Noeud of abr *  int * abr;;

1. Ecrire une fonction insere de signature abr -> int -> abr qui insère une valeur dans un abr et renvoie l'abr obtenu.

2. Construire et visualiser l'arbre binaire obtenu en insérant successivement les valeurs \(7, 5, 9, 2\) et \(11\).

3. Ecrire une fonction present de signature abr -> int -> bool qui teste si une valeur appartient ou non à un abr.

4. Ecrire une fonction min_arb : abr -> int qui renvoie la plus petite clé présente dans un abr non vide.

5. Ecrire une fonction max_arb : abr -> int qui renvoie la plus grande clé présente dans un abr non vide.

6. Ecrire une fonction supprime : abr -> int -> abr qui supprime une clé dans un abr.

   Aide

   On rappelle que l'algorithme de suppression distingue plusieurs cas :

   • si l'arbre est vide ou que la clé n'est pas présente alors on renvoie l'arbre.
   • sinon on descend récursivement dans l'arbre jusqu'à trouver la clé \(x\), dans un noeud \((g, x, d)\) si ce noeud est une feuille on le supprime sinon on peut soit remplacer \(x\) par le maximum de \(g\) (si \(g\) est non vide) soit remplacer \(d\) par le minimum de \(d\) (si \(d\) est non vide).

Exercice 10 : Hauteur moyenne d'un ABR aléatoire

Le but de cet exercice est de faire des statistiques sur la hauteur de l'arbre binaire obtenu en insérant aléatoirement dans cet arbre les entiers \(0, \dots, 1023\). Pour l'implémentation, on utilisera au choix le C ou OCaml.

1. Quelle est la hauteur maximale obtenue ? donner un ordre d'insertion permettant d'atteindre cette valeur
2. Quelle est la hauteur minimale ?

3. Ecrire une fonction permettant de générer une permutation aléatoire des entiers \(0,\dots,1023\)

   Aide

   On pourra par exemple, générer le tableau des entiers de 0 à 1023 puis utiliser le melagne de Knuth

4. Créer une fonction prenant en argument un tableau d'entiers, qui insère ces entiers dans un abr puis renvoie la hauteur de l'arbre obtenu.

5. Donner la moyenne, le minimum, le maximum de la série statistique des hauteurs obtenues en utilisant 1000 fois la fonction précédente.

Exercice 11 : Implémentation de la structure de tas en C

On rappelle qu'un tas est un arbre binaire complet et que par conséquent, on peut le représenter à l'aide d'un tableau. En C, on propose la structure de données suivantes :

    struct heap_s
    {
        int size;
        int capacity;
        int *array;
    };
    typedef struct heap_s heap;

• size est la taille courant du tas
• capacity est la capacité maximale du tas
• array est le pointeur vers les éléments du tas, la zone mémoire correspondante est allouée de taille capacity à la création du tas.

Le but de l'exercice est d'écrire les fonctions d'insertion (percolation vers le haut) et de suppression du minimum (percolation vers le bas) d'un élément dans ce tas puis de les utiliser afin d'implémenter l'algorithme du tri par tas.

1. Rappeler les indices des fils éventuels d'un élément dont l'indice dans le tableau est i puis écrire une fonction de signature int son(int i) qui renvoie l'indice du fils gauche du noeud d'indice i.

2. Rappeler l'indices du parent d'un élément dont l'indice dans le tableau est i>0 puis écrire une fonction de signature int father(int i) qui renvoie l'indice du parent du noeud d'indice i.

3. Ecrire la fonction heap make_heap(int cap) qui renvoie un tas binaire de capacité maximale cap, on rappelle qu'il faut allouer le pointeur vers les éléments du tas.

4. Ecrire la fonction bool insert_heap(int nv, heap *mh) qui modifie le tas donné en argument en y insérant la valeur nv.

5. Tester ces fonctions sur un exemple simple et afficher le tas binaire crée en utilisant la fonction de visualisation des arbres.

6. Ecrire et tester la fonction #c int getmin(heap *mh) qui extrait le minimum du tas binaire donné en argument.

7. Ecrire une implémentation du tri par tas de signature #c void heapsort(int *array, int size) qui trie le tableau donné en argument.

Exercice 12 : Implémentation de la structure de tas en Ocaml

Reprendre l'exercice précédent en utilisant OCaml, avec le type suivant pour représenter un tas :

    type 'a heap = {mutable size : int; data : 'a array};;

Humour d'informaticien

Finally after years of search I found a real tree ...