C12 Arbres binaires ¶

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

Cours¶

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));
        assert n!=NULL;
        n->sag = g;
        n->valeur = v;
        n->sad = d;
        return n;
    }

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 &");
    }

Ecrire une fonction est_vide de signature bool est_vide(ab a) permettant de tester si l'arbre donné en paramètre est vide.
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.
Ecrire et tester la fonction hauteur de signature int hauteur(ab a) et qui renvoie la hauteur de l'arbre binaire donné en argument.
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.
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>
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 ;;

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");;

Ecrire une fonction est_vide de signature ab -> bool permettant de tester si l'arbre donné en paramètre est vide.
Ecrire et tester la fonction taille de signature ab -> int et qui renvoie le nombre de noeuds de l'arbre binaire donné en argument.
Ecrire et tester la fonction hauteur de signature ab -> int et qui renvoie la hauteur de l'arbre binaire donné en argument.
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.

Ecrire une fonction qui pour le noeud situé à l'indice i renvoie l'indice du parent (\(-1\) pour la racine)
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)
Ecrire une fonction renvoyant la hauteur de l'arbre.

Exercice 4 : Parcours récursif en C¶

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
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¶

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

Ecrire une fonction insere de signature void insere(abr *t, int v) qui insère la valeur v dans l'arbre binaire t.
Construire et visualiser l'arbre binaire obtenu en insérant successivement les valeurs \(7, 5, 9, 2\) et \(11\).
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;;

Ecrire une fonction insere de signature abr -> int -> abr qui insère une valeur dans un abr et renvoie l'abr obtenu.
Construire et visualiser l'arbre binaire obtenu en insérant successivement les valeurs \(7, 5, 9, 2\) et \(11\).
Ecrire une fonction present de signature abr -> int -> bool qui teste si une valeur appartient ou non à un abr.
Ecrire une fonction min_arb : abr -> int qui renvoie la plus petite clé présente dans un abr non vide.
Ecrire une fonction max_arb : abr -> int qui renvoie la plus grande clé présente dans un abr non vide.
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.

Quelle est la hauteur maximale obtenue ? donner un ordre d'insertion permettant d'atteindre cette valeur
Quelle est la hauteur minimale ?
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
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.
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.

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.
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.
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.
Ecrire la fonction bool insert_heap(int nv, heap *mh) qui modifie le tas donné en argument en y insérant la valeur nv.
Tester ces fonctions sur un exemple simple et afficher le tas binaire crée en utilisant la fonction de visualisation des arbres.
Ecrire et tester la fonction int getmin(heap *mh) qui extrait le minimum du tas binaire donné en argument.
Ecrire une implémentation du tri par tas de signature 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};;

Attention

Les exercices suivant mettent en oeuvre l'utilisation de la structure de données de tas binaire pour la résolution de problèmes, on recommande d'aborder ces exercices uniquement lorsque les deux exercices précédents (implémentation de la structure de données de tas et application au tri) sont réalisés. Dans l'énoncé on a utilisé le langage C pour la médiane d'une flux de données et OCaml dans la fusion de \(k\) liste triées mais chacun des deux exercices peut être réalisé dans l'un ou l'autre des deux langages.

Exercice 13 : Médiane d'un flux de données¶

Dans cet exercice on considère un flux de données de valeurs entières, c'est à dire qu'on ne dispose pas initialement de la totalité des données et on considère qu'elles arrivent au fur et à mesure du déroulement de l'algorithme. A chaque nouvelle valeur lue, on veut mettre à jour une variable contenant la mediane des valeurs déjà lues. On rappelle que la médiane est, lorsque les valeurs sont rangées, la valeur qui sépare la série en deux parties de même effectif. Si on numérote les valeurs à partir de 0, alors lorsque la série contient un nombre impair \(2n+1\) de valeurs (numérotées de \(0\) à \(2n\)) alors c'est la valeur portant le numéro \(n\). Par exemple, pour calculer la médiane de \(2, 7, 3, 1, 10, 8, 4\), on range la série dans l'ordre : \(1, 2, 3, 4, 7, 8, 10\) et donc ici la médiane est 4. Lorsque la série contient un nombre pair \(2n\) de valeur (numérotées de 0 à \(2n-1\)) alors on fait la moyenne arithmétique des termes de rang \(n-1\) et \(n\) après rangement. Par exemple, pour calculer la médiane de \(2, 10, 1, 4, 7, 3\), on range : \(1, 2, 3, 4, 7, 10\) et la médiane est alors \((3+4)/2\) c'est à dire \(3.5\).

Dans toute la suite de l'exercice, on suppose connu la taille du flux de données qu'on note \(N\) et on supposera cette valeur déjà définie en début de programme par une directive de précompilation #define.

Méthode consistant à ranger le flux de données

Dans cette partie, on décide de maintenir à jour une version rangée du flux de données, pour cela à chaque arrivée d'une nouvelle valeur, on l'insère à la bonne position dans la partie déjà rangée.
1. Ecrire une fonction de signature void insere(int tab[], int i,int v) qui prend en argument un tableau de taille \(N\), et un indice \(i\) et qui en supposant ce tableau rangé jusqu'à l'indice \(i\) (exclu) insère la valeur v à la position correcte dans ce tableau.
2. Ecrire une fonction float mediane(int tab[], int s) qui renvoie la médiane des valeurs du tableau tab (de taille \(N\)) d'indice \(0, \dots s-1\) en supposant que ce sous tableau est rangé.
3. Afin de simuler le flux de données, écrire une fonction int lire_flux(int minv, int maxv) qui renvoie un entier au hasard entre min v (inclus) et maxv (exclu). Afin d'initialiser le flux, créer une fonction void init_flux(int graine) qui initialise le générateur de nombre aléatoire avec la valeur graine.
  Aide
  
  On rappelle que :
  - l'initialisation se fait à l'aide de la fonction srand du module stdlib.
  - la fonction rand ne prend par d'argument et renvoie un entier aléatoire entre 0 et une constante RAND_MAX du langage.
4. Initialiser le flux de données avec la graine \(42\), et tirer des valeurs entre 0 (inclus) et \(100\) (exclu), et générer la liste 5 premières médianes, vous devriez trouver : \(66, 53, 66, 53.5, 41\).
5. Toujours en initialisant avec la graine 42, tirer maintenant des valeurs entre 0 (inclus) et \(1\,000\,000\) (exclu). Quelle est la médiane du flux de données après avoir lu \(200\,000\) valeurs ? (entrer la valeur entière sans le séparateur décimal).
6. Donner la complexité de cette méthode en fonction du nombre \(n\) de données lues.
Utilisation de la structure de tas

On considère à présent l'algorithme suivante qui met à profit l'utilisation de la structure de tas :
- On crée un tas binaire max petit initialement vide.
- On crée un tas binaire min grand initialement vide.
- pour chaque donnée \(v\) lue :
  - si les deux tas ont la même taille, alors on insère \(v\) dans grand, on extrait le min de grand et on l'insère dans petit
  - sinon, on insère \(v\) dans petit, on extrait le maximum de petit et l'insère dans grand.
On fera bien attention que petit est un tas binaire max alors que grand est un tas binaire min.
1. Dérouler cet algorithme en considérant le flux de donnée suivant : 10, 6, 11, 12, 14, 9, 3 et en schématisant l'évolution des deux tas.
2. Vérifier que l'invariant suivant est préservé durant le déroulement de l'algorithme : petit contient la moitié inférieure des valeurs du flux et grand la moitié supérieure (la moitié inférieure contenant éventuellement un élément supplémentaire).
3. En déduire comment extraire la médiane du flux de données.
4. Mettre en oeuvre cette nouvelle méthode et retrouver les résultats de la première partie.
5. Donner en fonction de \(n\) la complexité de cette nouvelle méthode.

Exercice 14 : Fusion de k listes triées¶

Dans cet exercice on s'intéresse à la fusion d'un tableau de \(k\) liste déjà triées en une seule liste triée. On supposera par souci de simplicité que chaque liste à la même longueur \(n\). Par exemple si \(k=3\) et \(n=2\) et que le tableau de liste est [| [2; 4]; [1; 5]; [6; 7] |] alors la fusion de ces 3 listes donne [1; 2; 4; 5; 6; 7].

Fusion successives des listes
1. Ecrire une fonction fusion : 'a list -> 'a list -> 'a list qui prend en argument deux listes supposées triées et renvoie leur fusion
2. En utilisant la fonction précédente, écrire une fonction fusion_multiple : 'a list array -> 'a list qui prend en argument un tableau de liste triées et renvoie la liste issue de leur fusion. On procédera par fusion successive de deux listes en utilisant la fonction écrite à la question précédente.
3. Déterminer la complexité de cette méthode en fonction de \(k\) (nombre de listes) et de \(n\) (longueur de chaque liste).
Utilisation d'un tas binaire min
1. Mettre en oeuvre la méthode qui consiste à utiliser un tas binaire min de taille \(k\) dans lequel on insère initialement pour chaque liste le couple (indice dans le tableau de la liste, premier élément de la liste). Ensuite tant que ce tas n'est pas vide, on prélève son minimum et on insère l'élément suivant de la liste dont ce minimum est issu (si la liste n'est pas vide).
2. Déterminer la complexité de cette nouvelle méthode.

Humour d'informaticien¶

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