C21 Complement sur les arbres

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

Cours

Support de cours chapitre 21

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 TD21

Travaux pratiques

Exercice 1 : Sur les arbres rouge-noir

Pour réprésenter un arbre rouge noir en OCaml, on définit un type somme Rouge | Noir pour la couleur puis on ajoute cette information de couleur dans les noeuds :

    type couleur = Rouge | Noir;;
    type arb = Vide | Noeud of arb * (couleur*int) * arb;;

1. Généralités

   1. On rappelle (voir cours) que dans un arbre rouge-noir, le nombre de noeuds noirs le long d'un chemin menant de la racine à une feuille est toujours le même, cette quantité est la hauteur noire. Ecrire une fonction arn -> int qui calcule la hauteur noire d'un arbre rouge noir.

   2. Tester votre fonction sur les deux arbres suivants :

      let t1 = Noeud(Noeud(Vide,(Noir,0),Vide),(Noir,1),Noeud(Noeud(Vide,(Noir,2),Vide),(Rouge,3),Noeud(Vide,(Noir,4),Noeud(Vide,(Rouge,5),Vide))))
      let t2 = Noeud(Noeud(Vide,(Noir,0),Vide),(Noir,1),Noeud(Noeud(Vide,(Noir,2),Vide),(Rouge,3),Noeud(Vide,(Noir,4),Noeud(Vide,(Rouge,5),Noeud(Vide,(Noir,6),Vide)))))
      

      Vous pouvez visualiser ces arbres grâce à la fonction de visualisation :
      Visualisation d'un arbre rouge noir en Caml

      Attention, cette fonction utiliser une variable globale int ninv = 0 que vous devrez déclarer en début de programme.

          let rec write_edge a writer =
            match a with
            | Vide -> ()
            | Noeud (sag,(c,e),sad) ->  Printf.fprintf writer "%d [color = %s]\n" e (string_of_color c);
              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;
              | 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;
              | 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;
                  write_edge sad writer;
              ;;
      
          let view a =
          let outc = open_out "temp.gv" in
          output_string outc "digraph mygraph {\n";
          write_edge a outc;
          output_string outc "}\n";
          close_out outc;
          ignore (Sys.command "dot -Tpng temp.gv -o temp.png");
          ignore (Sys.command "eog temp.png");
          ();;
      

   3. Ecrire une fonction verifie_abr de signature arn -> bool qui vérifie que l'arbre donné en argument est un arbre binaire de recherche.

   4. Ecrire une fonction verifier_couleurs de signature arn->bool qui vérifie que dans un arn, le père d'un noeud rouge est noir

   5. Déduire des questions précédentes une fonction permettant de vérifier qu'un arbre est bien un arbre rouge-noir.

2. Insertion dans un arbre rouge-noir
   On rappelle (voir TD), que pour insérer un nouveau noeud dans un arbre rouge-noir, on commence par insérer comme dans un abr en coloriant le nouveau noeud en rouge. Puis lorsqu'un conflit rouge-rouge intervient, on le résout en coloriant la racine en noire si le conflit se situe à la racine, sinon on effectue une des transformations vues en TD.

   1. Ecrire une fonction noicir_racine de signature arn -> arn qui colorie la racine en noire

   2. Ecrire une fonction correction_rouge qui permet de corriger un conflit rouge-rouge lorsque celui ci ne se trouve pas à la racine. On utilisera un filtrage par motif et on rappelle qu'on se trouve dans l'un des quatre cas ci-dessous :
      qui se ramène tous à :

   3. Ecrire une fonction qui insère une nouvelle valeur dans un arbre rouge-noir

   4. Créer un arbre rouge noir et y insérer tous les entiers compris entre 1 et \(1\,000\,000\). Quelle est la hauteur de l'arbre obtenu ?

Humour d'informaticien

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