Aller au contenu

Ces travaux pratiques accompagnent le chapitre sur les arbres.

Arbres en OCaml

Premières fonctions

On va considérer le type des arbres binaires 'a arbre défini par :

type 'a arbre = Nil | Noeud of 'a arbre * 'a * 'a arbre

Question

Écrire des fonctions :

(* Calcule le nombre de noeuds de a *)
let taille (a : 'a arbre) : int
(* Calcule la hauteur de a *)
let hauteur (a : 'a arbre) : int
(* Indique si a est réduit à une feuille *)
let feuille (a : 'a arbre) : bool
Corrigé 
let rec taille a = match a with
    | Nil -> 0
    | Noeud(g,x,d) -> 1 + taille g + taille d

let rec hauteur a = match a with
    | Nil -> -1
    | Noeud(g,x,d) ->
            1 + max (hauteur g) (hauteur d)

let feuille a = match a with
    | Nil -> false
    | Noeud(g, x, d) -> g = Nil && d = Nil

Question

Écrire une fonction sous_arbres qui renvoie la liste des sous-arbres non vides d'un arbre.

En déduire des fonctions noeuds, feuilles et noeuds_internes qui renvoient la liste des étiquettes des nœuds correspondants.

Corrigé 
let rec sous_arbres a = match a with
    | Nil -> []
    | Noeud(g, x, d) ->
       a :: (sous_arbres g @ sous_arbres d)

let rec noeuds a = match a with
    | Nil -> []
    | Noeud(g, x, d) ->
        x :: (noeuds g @ noeuds d)

let rec feuilles a = match a with
    | Nil -> []
    | Noeud(g, x, d) ->
        if feuille a then [x]
        else feuilles g @ feuilles d

let rec noeuds_internes a = match a with
    | Nil -> []
    | Noeud(Nil, _, Nil) -> []
    | Noeud(g, x, d) ->
        x :: (noeuds_internes g @ noeuds_internes d)

On peut aussi déduire directement ces fonctions de sous_arbres, par exemple let noeuds a = List.map (fun t -> match t with Noeud(_, x, _) -> x | Nil -> failwith "impossible") (sous_arbres a), et de même pour les feuilles avec List.filter feuille.

Pour accéder à un nœud de l'arbre, on descend en partant de la racine et en allant à gauche ou à droite. On peut donc représenter un tel chemin par une liste de déplacements :

type deplacement = Gauche | Droite
type chemin = deplacement list

Question

Écrire une fonction chemin_noeud : 'a arbre -> chemin -> 'a option qui renvoie l'étiquette d'un nœud donné par son chemin. On utilise un type option en cas de chemin invalide.

Corrigé 
let rec chemin_noeud a l =
    match a, l with
    | Nil, _ -> None
    | Noeud(g,x,d), Gauche::q -> chemin_noeud g q
    | Noeud(g,x,d), Droite::q -> chemin_noeud d q
    | Noeud(g,x,d), [] -> Some x

Parcours

Sur le même modèle que l'exploration par backtracking, on va réaliser un parcours en profondeur d'un arbre en explorant à gauche puis à droite ses sous-arbres de manière récursive. Chaque nœud est donc vu trois fois :

  • une première fois quand on le découvre avant d'explorer son sous-arbre gauche ;
  • entre les deux explorations ;
  • enfin quand on a fini d'explorer son sous-arbre droit.

Question

Écrire des fonctions affiche_avant, affiche_milieu et affiche_apres qui parcourent et affichent les étiquettes d'un string arbre selon les trois cas précédents. Note : il s'agit essentiellement du même code à une ligne près.

Corrigé 
let rec affiche_avant a = match a with
    | Nil -> ()
    | Noeud(g,x,d) ->
            print_string x;
            affiche_avant g;
            affiche_avant d

let rec affiche_milieu a = match a with
    | Nil -> ()
    | Noeud(g,x,d) ->
            affiche_milieu g;
            print_string x;
            affiche_milieu d

let rec affiche_apres a = match a with
    | Nil -> ()
    | Noeud(g,x,d) ->
            affiche_apres g;
            affiche_apres d;
            print_string x

Question

On peut représenter une expression arithmétique comme \((2+3)\times 4\) en tant qu'arbre avec des opérations pour les nœuds internes et des valeurs pour les feuilles. Quitte à utiliser des string dans les deux cas, qu'obtient-on sur une telle expression avec les trois opérations précédentes ?

Corrigé

L'appel à affiche_avant sur l'expression \((2+3)\times 4\) va afficher *+234.

L'appel à affiche_milieu sur l'expression \((2+3)\times 4\) va afficher 2+3*4.

L'appel à affiche_apres sur l'expression \((2+3)\times 4\) va afficher 23+4*.

On retrouve ainsi les notions préfixes, infixes et postfixes d'une expression arithmétique. Remarquons que l'écriture infixe obtenue a perdu les parenthèses et ne permet plus de retrouver l'expression.

On peut également évaluer une telle expression :

let rec evalue a = match a with
    | Nil -> failwith "Vide"
    | Noeud(Nil,x,Nil) -> int_of_string x
    | Noeud(g, x, d) ->
            let eg = evalue g in
            let ed = evalue d in
            match x with
            | "+" -> eg + ed
            | "*" -> eg * ed
            | _ -> failwith "Ope inconnue"

On redonne ici l'implémentation d'une pile et d'une file en OCaml :

let pile_creer () = ref []
let pile_empile p x = p := x :: !p
let pile_depile p =
    match !p with
    | [] -> failwith "Pile vide"
    | x::q -> p := q; x
let pile_est_vide p = !p = []

let file_creer () = (pile_creer (), pile_creer ())
let file_bascule (pin, pout) = pout := List.rev !pin; pin := []
let file_enfile (pin, pout) x = pile_empile pin x
let file_defile (pin, pout) =
    if pile_est_vide pout
    then file_bascule (pin, pout);
    pile_depile pout
let file_est_vide (pin, pout) = pile_est_vide pin && pile_est_vide pout

Ces deux structures de données ont la même interface mais deux comportements différents. On va utiliser un unique type pour les représenter afin de permettre à une fonction d'utiliser soit une pile soit une file.

type ('a, 'b) taches = {
    creation : unit -> 'a;
    ajouter : 'a -> 'b -> unit;
    retirer : 'a -> 'b;
    est_vide : 'a -> bool
}

let taches_pile = {
    creation = pile_creer;
    ajouter = pile_empile;
    retirer = pile_depile;
    est_vide = pile_est_vide
    }

let taches_file = {
    creation = file_creer;
    ajouter = file_enfile;
    retirer = file_defile;
    est_vide = file_est_vide
    }

Remarque

Ici, on a une limitation du système de types. On aimerait paramétrer taches par ('b t, 'b) où t est lui-même un type paramétré, ainsi on aurait soit ('b pile, 'b) soit ('b file, 'b) dans les deux cas. Cependant, ce n'est pas possible : en OCaml, un paramètre de type ne peut pas lui-même être un type paramétré. C'est pour cela qu'on a un ('a, 'b) sans avoir de lien apparent entre 'a et 'b.

On pourra alors écrire une fonction prenant un gestionnaire de tâches en paramètre :

let f t a =
    let a_traiter = t.creation () in
    for i = 0 to Array.length a - 1 do
        t.ajouter a_traiter a.(i)
    done;
    while not (t.est_vide a_traiter) do
        print_int (t.retirer a_traiter)
    done

Ainsi f taches_pile [|1;2;3|] va afficher 321 et f taches_file [|1;2;3|] va afficher 123.

Question

En déduire une fonction

parcours : ('a, int arbre) taches -> int arbre -> unit

qui effectue un parcours de l'arbre en affichant les étiquettes des nœuds visités dans l'ordre induit par le gestionnaire de tâches passé en paramètre.

Corrigé 
let parcours t a =
    let avisiter = t.creation () in
    t.ajouter avisiter a;
    while not (t.est_vide avisiter) do
        match t.retirer avisiter with
        | Nil -> ()
        | Noeud(g,x,d) ->
                print_int x;
                t.ajouter avisiter g;
                t.ajouter avisiter d
    done

Avec taches_pile on obtient un parcours en profondeur (qui visite le fils droit avant le fils gauche), avec taches_file un parcours en largeur. Sur l'arbre de l'exemple du cours, on obtient respectivement 1365724 et 1234567.

Arbres binaires stricts

Pour représenter des arbres dont les nœuds internes ont tous deux fils non vides, on va utiliser le type

type ('a, 'b) arbre_bin = Feuille of 'a
    | NoeudI of ('a, 'b) arbre_bin * 'b * ('a, 'b) arbre_bin

Ce type permet de représenter naturellement des expressions arithmétiques comme :

NoeudI(NoeudI( Feuille 2, '+', Feuille 3), '*', Feuille 5)

Question

Écrire une fonction evalue : (int, char) arbre_bin -> int qui évalue une telle expression.

Corrigé 
let rec evalue a = match a with
    | Feuille n -> n
    | NoeudI(g, x, d) ->
            let eg = evalue g in
            let ed = evalue d in
            match x with
            | '+' -> eg + ed
            | '*' -> eg * ed
            | _ -> failwith "Ope inconnue"

Si on considère le type

type ('a, 'b) etiquette = F of 'a | N of 'b

On peut passer d'un ('a, 'b) arbre_bin à un ('a, 'b) etiquette arbre et, dans certains cas, d'un ('a, 'b) etiquette arbre à un ('a, 'b) arbre_bin.

Question

Écrire ainsi deux fonctions de conversion :

arbre_bin_vers_arbre : ('a, 'b) arbre_bin -> ('a, 'b) etiquette arbre
arbre_vers_arbre_bin : ('a, 'b) etiquette arbre -> ('a, 'b) arbre_bin option
Corrigé 
let rec arbre_bin_vers_arbre a =
    match a with
    | Feuille n -> Noeud(Nil, F n, Nil)
    | NoeudI(g, x, d) -> Noeud(arbre_bin_vers_arbre g,
                            N x,
                            arbre_bin_vers_arbre d)

let rec arbre_vers_arbre_bin a =
    match a with
    | Noeud(Nil, F f, Nil) -> Some (Feuille f)
    | Noeud(g, N x, d) -> begin
            match arbre_vers_arbre_bin g, arbre_vers_arbre_bin d with
            | Some g', Some d' -> Some (NoeudI(g', x, d'))
            | _ -> None
        end
    | _ -> None

Dessin d'arbres

On va réaliser dans cette partie une fonction de dessin d'arbres avec graphics. L'idée est de placer la racine et de dessiner les sous-arbres gauche et droit en dessous. Pour cela, il va falloir connaître la taille de ces sous-arbres en pixels.

On pourra consulter la documentation de graphics ici : Graphics

Question

Écrire une fonction pixels : int arbre -> int * int qui renvoie un couple (largeur, racine) où largeur est la largeur en pixels d'un arbre dans son affichage et racine l'abscisse de la racine dans cet affichage.

Corrigé 
let rnoeud = 5 (* Le rayon du noeud *)
let marge = 2 (* la marge autour du noeud *)

let rec pixels a = match a with
    | Nil -> 0, 0
    | Noeud(g, _, d) ->
            let lg, _ = pixels g in
            let ld, _ = pixels d in
            lg + ld + 2*(marge + rnoeud), lg + marge + rnoeud

Question

En déduire une fonction dessine : int arbre -> int -> int -> unit telle que dessine a x y dessine l'arbre \(a\) en plaçant la racine en \((x, y)\).

Corrigé 
let rec dessine a x y =
    match a with
    | Nil -> ()
    | Noeud(g, e, d) ->
            (* On précalcule les tailles des sous-arbres *)
            let lg, rg = pixels g in
            let _, rd = pixels d in
            (* position de la racine gauche relativement à (x,y) *)
            let v_rg = x - lg - marge - rnoeud + rg in
            (* position de la racine droite relative (x, y) *)
            let v_rd = x + marge + rnoeud + rd in
            let dec_y = y - 2 * rnoeud - marge in

            moveto x y; lineto v_rg dec_y;
            moveto x y; lineto v_rd dec_y;
            fill_circle x y rnoeud;

            let s = string_of_int e in
            let tw, th = text_size s in
            moveto (x-tw/2) (y-th/2);
            set_color white;
            draw_string s;
            set_color black;

            dessine g v_rg dec_y;
            dessine d v_rd dec_y

Les nœuds sont placés de gauche à droite dans l'ordre infixe, espacés de 2*(marge+rnoeud) pixels. Avec des valeurs aussi petites pour rnoeud, les étiquettes débordent des nœuds : on pourra les augmenter.

Génération aléatoire d'arbres

Dans cette partie, ce qui nous intéresse est de générer aléatoirement des arbres pour en observer la structure. Les étiquettes ne sont pas pertinentes, on pourra donc au choix, soit considérer des unit arbre, soit redéfinir un type d'arbres non étiquetés.

On va réaliser ici deux modèles de génération aléatoire d'arbres. Le premier modèle consiste, pour générer un arbre de \(n \ge 1\) nœuds, à choisir aléatoirement \(k\) dans \(\range{0}{n-1}\), à générer aléatoirement un arbre \(g\) à \(k\) nœuds et un arbre \(d\) à \(n-1-k\) nœuds puis à renvoyer l'arbre Noeud(g, (), d).

Question

Implémenter ce modèle avec une fonction genere_arbre_1 : int -> unit arbre.

Tester votre fonction, notamment avec l'affichage de la partie précédente.

Corrigé 
let rec genere_arbre_1 n =
    if n = 0
    then Nil
    else let k = Random.int n in
        Noeud(genere_arbre_1 k, (),
            genere_arbre_1 (n-1-k))

Pour le deuxième modèle, on va choisir un sous-arbre vide uniformément et le remplacer par un nœud.

Question

Écrire une fonction chemins_vides : 'a arbre -> chemin list qui étant donné un arbre renvoie la liste des chemins permettant d'aboutir à un sous-arbre vide.

Corrigé 
let chemins_vides a =
    let rec aux a l =
        match a with
        | Nil -> [ List.rev l ]
        | Noeud(g, _, d) ->
              aux g (Gauche::l)
            @ aux d (Droite::l)
    in aux a []

Un arbre à \(n\) nœuds a \(n+1\) sous-arbres vides (c'est le théorème sur les arbres stricts appliqué à l'arbre où l'on remplace chaque arbre vide par une feuille) : cette liste est de longueur \(n+1\).

Question

Écrire une fonction remplit : 'a arbre -> chemin -> 'a arbre qui remplace un sous-arbre vide donné par son chemin par un nœud.

Corrigé 
let rec remplit a c =
    match a, c with
    | Nil, [] -> Noeud(Nil, (), Nil)
    | Noeud(g,x,d), Gauche::q ->
            Noeud(remplit g q, x, d)
    | Noeud(g,x,d), Droite::q ->
            Noeud(g, x, remplit d q)
    | _ -> failwith "Chemin invalide"

Question

En déduire une fonction genere_arbre_2 : int -> unit arbre qui prend un entier n et construit un arbre à \(n\) nœuds en partant de l'arbre vide et en réalisant \(n\) remplacements d'un arbre vide par un nœud, le choix de l'arbre vide se faisant uniformément.

Note : on pourra utiliser List.nth et Random.int. Voir par exemple Random.

Corrigé 
let rec genere_arbre_2 n =
    if n = 0 then Nil
    else
        let a = genere_arbre_2 (n-1) in
        let l = chemins_vides a in
        let k = Random.int (List.length l) in
        let ch = List.nth l k in
        remplit a ch

Remarque

Le deuxième modèle correspond exactement à la forme d'un arbre binaire de recherche obtenu en insérant successivement les éléments d'une permutation aléatoire uniforme : à chaque étape, la nouvelle valeur tombe avec la même probabilité dans chacun des intervalles délimités par les valeurs déjà présentes, c'est-à-dire dans chacun des sous-arbres vides. On pourra comparer expérimentalement les hauteurs moyennes des arbres obtenus par les deux modèles.

Arbres non binaires, tries

Arbres non binaires

On va considérer ici les arbres d'arité quelconque avec des listes d'enfants pour les nœuds.

type 'a arbre = { etiquette : 'a; enfants : 'a arbre list }

Afin d'effectuer des tests, on pourra considérer l'arbre suivant :

let t = { etiquette = 1;
    enfants = [
        { etiquette = 2; enfants = [
            { etiquette = 5; enfants = [] }
            ] };
        { etiquette = 3; enfants = [
            { etiquette = 6; enfants = [
                { etiquette = 10 ; enfants = []}
            ]};
            { etiquette = 7; enfants = []}
        ] };
        { etiquette = 4; enfants = [
                { etiquette = 8; enfants = []};
                { etiquette = 9; enfants = []}
        ] }
    ] }

qui correspond à la représentation :

Comme présenté dans le cours, on peut réaliser des fonctions mutuellement récursives pour travailler avec ces arbres et sur la forêt induite par les enfants d'un nœud :

let rec taille_arbre a =
    1 + taille_foret a.enfants
    and taille_foret l = match l with
        | [] -> 0
        | t::q -> taille_arbre t + taille_foret q

Question

Écrire une fonction hauteur_arbre : 'a arbre -> int qui calcule la hauteur d'un arbre sur le modèle de la fonction précédente. On fera attention au fait qu'il n'est pas possible de représenter l'arbre vide mais la forêt vide jouera le même rôle vis-à-vis de \(-1\).

Corrigé 
let rec hauteur_arbre a =
    1 + hauteur_foret a.enfants
    and hauteur_foret l = match l with
    | [] -> -1
    | t::q -> max (hauteur_arbre t) (hauteur_foret q)

Sur l'arbre t, on obtient une taille de \(10\) et une hauteur de \(3\).

Question

À l'aide d'un parcours récursif, écrire une fonction affiche_etiquettes : int arbre -> unit qui affiche toutes les étiquettes d'un int arbre.

Corrigé 
let rec affiche_etiquettes a =
    Printf.printf "%d\n" a.etiquette;
    affiche_foret a.enfants
    and affiche_foret l = match l with
        | [] -> ()
        | t::q -> affiche_etiquettes t; affiche_foret q

Représentation par des arbres binaires

On va maintenant revenir ici sur la représentation d'un 'a arbre en tant qu'arbre binaire. Pour cela, on va avoir besoin d'étiquettes factices pour les nouveaux nœuds qui ne servent qu'à supporter la structure des nœuds d'arité \(>2\). On va ainsi les représenter par des 'a option arbre_bin où l'étiquette None sera celle des nœuds factices.

type 'a arbre_bin = Noeud of 'a arbre_bin * 'a * 'a arbre_bin | Nil

Question

On va commencer par écrire une fonction peigne : 'a option arbre_bin list -> 'a option arbre_bin qui va transformer une forêt d'arbres binaires en sa représentation en peigne à l'aide de nœuds d'étiquettes None.

Note Dans le cas où la liste est vide, on renverra l'arbre vide et si c'est un singleton, on renverra directement l'arbre qu'il contient.

Corrigé 
let rec peigne l =
    match l with
    | [] -> Nil
    | [x] -> x
    | a::q -> Noeud(a, None, peigne q)

Question

Écrire une fonction convert : 'a arbre -> 'a option arbre_bin qui va réaliser la conversion vue en cours.

Corrigé 
let rec convert a =
    match a.enfants with
    | [] -> Noeud (Nil, Some a.etiquette, Nil)
    | a1::q -> Noeud(convert a1, Some a.etiquette,
                        peigne (List.map convert q))

Afin de tester votre fonction, on vous donne une fonction d'affichage textuel d'un tel arbre :

let rec print_arbre_bin pref t =
    match t with
    | Nil -> Printf.printf "%snil\n%!" pref
    | Noeud(g,x,d) -> Printf.printf "%s%s\n%!" pref
                (match x with None -> "*" | Some n -> string_of_int n);
        print_arbre_bin (String.make (String.length pref) ' '
                        ^ "|" ^ String.make 5 '-') g;
        print_arbre_bin (String.make (String.length pref) ' '
                        ^ "|" ^ String.make 5 '-') d

L'affichage de print_arbre_bin "" (convert t) doit correspondre à la représentation suivante :

Arbre binaire obtenu par conversion ; star (violet) est le nœud factice d'étiquette None. Arbre binaire obtenu par conversion ; star (violet) est le nœud factice d'étiquette None.
Arbre binaire obtenu par conversion ; $\star$ (violet) est le nœud factice d'étiquette None.

Tries

On va reprendre les tries vus dans le cours pour représenter un ensemble de mots. Pour cela, on réutilise le type :

type trie = {
    mot : bool;
    enfants : (char * trie) list
    }

Premières manipulations

Question

Écrire une fonction taille : trie -> int qui renvoie le nombre de nœuds d'un trie et une fonction nb_mots : trie -> int qui renvoie le nombre de mots d'un trie. On s'inspirera directement des fonctions de la première partie du TP.

Corrigé 
let rec taille a =
    1 + taille_foret a.enfants
    and taille_foret l = match l with
        | [] -> 0
        | (_, t) :: q -> taille t + taille_foret q

let rec nb_mots a =
    (if a.mot then 1 else 0) + nb_mots_foret a.enfants
    and nb_mots_foret l = match l with
        | [] -> 0
        | (_, t) :: q -> nb_mots t + nb_mots_foret q

Question

Écrire une fonction trie_apres_char telle que l'appel à trie_apres_char l c va renvoyer Some t' s'il y a un couple (c, t') dans la liste l et None sinon. On pourra s'en servir avec trie_apres_char t.enfants c pour trouver le trie potentiel dont l'arête est étiquetée par c.

Corrigé 
let rec trie_apres_char (l:(char * trie) list) (c:char) =
    match l with
    | [] -> None
    | (c',t)::q -> if c = c' then Some t else trie_apres_char q c

Question

En déduire une fonction contient : trie -> string -> bool qui teste si un mot est présent dans le trie.

Corrigé 
let contient (t:trie) (s:string) : bool =
    let rec aux t i =
        if i = String.length s
        then t.mot
        else match trie_apres_char t.enfants s.[i] with
            | None -> false
            | Some t' -> aux t' (i+1)
    in aux t 0

Question

Écrire une fonction enumere : trie -> string list qui renvoie tous les mots contenus dans un trie par un parcours récursif.

Indication : on pourra utiliser :

  • List.concat pour passer d'une liste de listes à la concaténée de ses éléments. Ainsi List.concat [ [1;2]; [3]; [4;5] ] va renvoyer [1;2;3;4;5] ;
  • String.make 1 c transforme le caractère c en chaîne de caractères ;
  • on rappelle que ^ permet de concaténer deux chaînes.
Corrigé 
let enumere (t:trie) =
    let rec aux t acc =
        let l = List.concat (List.map (fun (c,t') ->
                aux t' (acc ^ String.make 1 c)) t.enfants) in
        if t.mot then acc :: l else l
    in aux t ""

Ajout d'un mot à un trie

Pour effectuer l'ajout d'un mot à un trie, on va commencer par écrire une fonction qui étant donné une chaîne de caractères s \(= c_0 \dots c_{n-1}\) et un entier \(i\le n\) va renvoyer le trie t correspondant à la branche

Branche du trie pour le suffixe c_i dots c_n-1 ; star marque la fin du mot. Branche du trie pour le suffixe c_i dots c_n-1 ; star marque la fin du mot.
Branche du trie pour le suffixe $c_i \dots c_{n-1}$ ; $\star$ marque la fin du mot.

Question

Écrire la fonction suffixe : int -> string -> trie.

Corrigé 
let rec suffixe (i:int) (s:string) : trie =
    let n = String.length s in
    if i = n
    then { mot = true; enfants = [] }
    else { mot = false; enfants = [ (s.[i], suffixe (i+1) s) ] }

Question

Écrire une fonction avec_trie_pour_char : (char * trie) list -> char -> trie -> (char * trie) list telle que avec_trie_pour_char l c t va renvoyer la liste obtenue en remplaçant (c,t') par (c,t) dans l si un tel couple est présent, ou en ajoutant le couple (c,t) à la fin sinon.

Corrigé 
let rec avec_trie_pour_char l c t =
    match l with
    | [] -> [ (c, t) ]
    | (c', t') :: q -> if c = c' then (c, t) :: q
                       else (c', t') :: avec_trie_pour_char q c t

Question

Écrire une fonction ajoute : trie -> string -> trie qui renvoie le trie obtenu en ajoutant un nouveau mot.

Corrigé 
let ajoute t s =
    let n = String.length s in
    let rec aux t i =
        if i = n
        then { t with mot = true }
        else let t' = match trie_apres_char t.enfants s.[i] with
                    | None -> suffixe (i+1) s
                    | Some t' -> aux t' (i+1) in
            { t with enfants = avec_trie_pour_char t.enfants s.[i] t' }
    in aux t 0

On va utiliser la fonction précédente pour retrouver le trie donné dans le cours.

let rec trie_of_list l = match l with
    | [] -> { mot = false; enfants = [] }
    | s::q -> ajoute (trie_of_list q) s

Ainsi trie_of_list ["bar"; "barbe"; "art"; "ami"; "abri"; "abricot"; "abonne"] est un trie à \(21\) nœuds contenant \(7\) mots.

On va maintenant récupérer une grande liste de mots dans le fichier wordlist récupérable à l'adresse https://raw.githubusercontent.com/dwyl/english-words/master/words_alpha.txt à raison d'un mot par ligne :

let wordlist = let rec lit_fichier f =
        try
            let s = input_line f in
                s :: lit_fichier f
            with End_of_file -> []
        in
        lit_fichier (open_in "wordlist")

Question

En déduire un trie permettant de représenter cette wordlist et comparez :

  • le nombre de caractères total ;
  • le nombre de nœuds du trie.

Que peut-on en déduire ?

Corrigé 
let taille_totale = List.fold_left (+) 0 (List.map String.length wordlist) in
taille_totale, taille (trie_of_list wordlist)

On constate qu'il y a nettement moins de nœuds que de caractères au total : les préfixes communs ne sont stockés qu'une fois. Attention cependant à ne pas sous-estimer la taille d'un nœud qui dépasse très largement celle d'un caractère. Cependant, le trie apporte la possibilité de chercher un mot \(m\) en \(O(|m|)\) (à alphabet fixé) et donc indépendamment du nombre de mots.

Remarquons que lit_fichier et trie_of_list ne sont pas récursives terminales : sur une très grande liste, on pourra préférer List.fold_left ajoute { mot = false; enfants = [] } wordlist.

Arbres binaires en C, ABR, arbres rouges et noirs

Arbres binaires en C

En C, un nœud d'un arbre binaire va avoir exactement la même structure qu'un maillon d'une liste doublement chaînée : une valeur et deux pointeurs vers d'autres nœuds, ici ce ne sont pas suivant et precedent mais gauche et droite :

struct noeud {
    struct noeud *gauche;
    struct noeud *droite;
    int valeur;
};

typedef struct noeud *arbre;

Comme pour les listes, l'arbre vide sera représenté par le pointeur NULL.

Question

Écrire une fonction arbre cree_feuille(int x) qui alloue et crée une feuille de valeur x.

Corrigé 
arbre cree_feuille(int x)
{
    arbre n = malloc(sizeof(struct noeud));
    n->valeur = x;
    n->gauche = n->droite = NULL;
    return n;
}

Question

En déduire une représentation en C de l'arbre :

Pour cela, on vous suggère de créer autant de feuilles que de nœuds et d'effectuer les liens ensuite avec les pointeurs.

Cet arbre nous servira d'exemple pour vérifier les fonctions suivantes.

Corrigé 
arbre n5 = cree_feuille(5);
arbre n1 = cree_feuille(1);
arbre n4 = cree_feuille(4);
arbre n9 = cree_feuille(9);
arbre n7 = cree_feuille(7);
arbre n20 = cree_feuille(20);
arbre n17 = cree_feuille(17);
n5->gauche = n1;
n1->droite = n4;
n5->droite = n9;
n9->gauche = n7;
n9->droite = n20;
n20->gauche = n17;

arbre a = n5;

Question

Écrire une fonction int taille(arbre a) qui renvoie le nombre de nœuds d'un arbre binaire.

Corrigé 
int taille(arbre a)
{
    if (a == NULL)
        return 0;
    return 1 + taille(a->gauche) + taille(a->droite);
}

Question

Écrire une fonction int hauteur(arbre a) qui renvoie la hauteur d'un arbre binaire.

Corrigé 
int max(int a, int b)
{
    if (a > b) return a;
    else return b;
}

int hauteur(arbre a)
{
    if (a == NULL)
        return -1;
    return 1 + max(hauteur(a->gauche), hauteur(a->droite));
}

Sur l'arbre exemple, on obtient une taille de \(7\) et une hauteur de \(3\).

Question

Écrire des fonctions void affiche_prefixe(arbre a), affiche_infixe et affiche_postfixe qui affichent les valeurs des nœuds de l'arbre a selon le traitement correspondant dans un parcours.

Écrire une fonction void affiche(arbre a) qui, à l'aide des trois traitements, permet d'afficher un arbre avec des triplets comme nœuds. Par exemple, pour l'arbre précédent, on pourra afficher :

((nil,1,(nil,4,nil)),5,((nil,7,nil),9,((nil,17,nil),20,nil)))
Corrigé 
void affiche_prefixe(arbre a)
{
    if (a != NULL)
    {
        printf("%d ", a->valeur);
        affiche_prefixe(a->gauche);
        affiche_prefixe(a->droite);
    }
}

void affiche_infixe(arbre a)
{
    if (a != NULL)
    {
        affiche_infixe(a->gauche);
        printf("%d ", a->valeur);
        affiche_infixe(a->droite);
    }
}

void affiche_postfixe(arbre a)
{
    if (a != NULL)
    {
        affiche_postfixe(a->gauche);
        affiche_postfixe(a->droite);
        printf("%d ", a->valeur);
    }
}

void affiche(arbre a)
{
    if (a != NULL)
    {
        printf("(");
        affiche(a->gauche);
        printf(",%d,", a->valeur);
        affiche(a->droite);
        printf(")");
    } else printf("nil");
}

Sur l'arbre exemple, on obtient 5 1 4 9 7 20 17 dans l'ordre préfixe, 1 4 5 7 9 17 20 dans l'ordre infixe et 4 1 7 17 20 9 5 dans l'ordre postfixe.

Question

(Optionnel en première lecture) À l'aide d'une file dans un tableau de longueur \(|a|\), réaliser une fonction void affiche_largeur(arbre a) qui affiche les valeurs des nœuds de l'arbre a lors d'un parcours en largeur.

Corrigé 
void affiche_largeur(arbre a)
{
    if (a == NULL)
        return;
    arbre *file = malloc(sizeof(arbre) * taille(a));
    file[0] = a;
    int debut = 0;
    int fin = 1;
    while(fin > debut)
    {
        arbre r = file[debut];
        debut++;
        printf("%d ", r->valeur);
        if(r->gauche != NULL)
        {
            file[fin] = r->gauche;
            fin++;
        }
        if(r->droite != NULL)
        {
            file[fin] = r->droite;
            fin++;
        }
    }
    free(file);
}

Chaque nœud étant enfilé exactement une fois, un tableau de longueur \(|a|\) suffit. Sur l'arbre exemple, on obtient 5 1 9 4 7 20 17.

Question

Écrire une fonction void libere(arbre a) qui libère tous les nœuds de l'arbre a. On fera attention à l'ordre des libérations avec free par rapport aux déréférencements de structure (les ->).

Corrigé 
void libere(arbre a)
{
    if (a != NULL)
    {
        libere(a->gauche);
        libere(a->droite);
        free(a);
    }
}

Arbres binaires de recherche

On conserve le type précédent, mais on considère maintenant qu'on a des arbres binaires de recherche.

Question

Écrire une fonction arbre recherche(arbre a, int x) qui renvoie le premier nœud rencontré d'étiquette x dans un ABR ou NULL s'il n'est pas présent.

Corrigé 
arbre recherche(arbre a, int x)
{
    if (a == NULL)
        return NULL;
    if (a->valeur == x)
        return a;
    if (a->valeur < x)
        return recherche(a->droite, x);
    return recherche(a->gauche, x);
}

Question

Écrire une fonction arbre insere(arbre a, int x) qui renvoie la racine de l'ABR obtenu en insérant une nouvelle feuille d'étiquette x.

Corrigé 
arbre insere(arbre a, int x)
{
    if (a == NULL)
        return cree_feuille(x);

    if (a->valeur >= x)
    {
        a->gauche = insere(a->gauche, x);
    }
    else
    {
        a->droite = insere(a->droite, x);
    }

    return a;
}

Contrairement à la version OCaml du cours, cette fonction modifie l'arbre en place : l'ancien arbre n'est plus disponible.

Question

Écrire une fonction arbre minimum(arbre a) qui renvoie le nœud de valeur minimale de a en allant le plus à gauche dans l'arbre a. On supposera a non vide.

Corrigé 
arbre minimum(arbre a)
{
    if (a->gauche == NULL)
        return a;
    return minimum(a->gauche);
}

Question

(Optionnel en première lecture) Écrire une fonction arbre supprime(arbre a, int x) qui renvoie la racine de l'ABR obtenu en supprimant le premier nœud rencontré d'étiquette x.

Corrigé

On suit la méthode du cours : si le nœud a un fils vide, on le remplace par l'autre fils ; sinon on remplace sa valeur par le minimum de son sous-arbre droit, qu'on supprime de ce sous-arbre.

arbre supprime(arbre a, int x)
{
    if (a == NULL)
        return a;
    if (a->valeur == x)
    {
        if (a->gauche == NULL)
        {
            arbre a_p = a->droite;
            free(a);
            return a_p;
        }
        if (a->droite == NULL)
        {
            arbre a_p = a->gauche;
            free(a);
            return a_p;
        }
        int min_valeur = minimum(a->droite)->valeur;
        a->droite = supprime(a->droite, min_valeur);
        a->valeur = min_valeur;
    } else {
        if (a->valeur > x)
            a->gauche = supprime(a->gauche, x);
        else
            a->droite = supprime(a->droite, x);
    }

    return a;
}

Arbres rouges et noirs

On va rajouter un champ au type précédent pour indiquer la couleur d'un nœud (il faut inclure stdbool.h) :

struct noeud {
    struct noeud *gauche;
    struct noeud *droite;
    bool rouge;
    int valeur;
};
typedef struct noeud *arbre;

On vous conseille ici de copier le fichier précédent et de faire un nouveau programme.

Question

Reprendre cree_feuille, en l'appelant cree_noeud, pour que les nouveaux nœuds soient rouges par défaut.

Corrigé 
arbre cree_noeud(int x)
{
    arbre n = malloc(sizeof(struct noeud));
    n->valeur = x;
    n->rouge = true;
    n->gauche = n->droite = NULL;
    return n;
}

Question

Écrire des fonctions arbre rotation_droite(arbre a), arbre rotation_gauche(arbre a) et arbre bascule(arbre a) qui effectuent une des trois opérations en renvoyant la nouvelle racine.

Corrigé 
arbre rotation_droite(arbre x)
{
    arbre y = x->gauche;
    x->gauche = y->droite;
    y->droite = x;
    y->rouge = x->rouge;
    x->rouge = true;
    return y;
}

arbre rotation_gauche(arbre y)
{
    arbre x = y->droite;
    y->droite = x->gauche;
    x->gauche = y;
    x->rouge = y->rouge;
    y->rouge = true;
    return x;
}

arbre bascule(arbre a)
{
    a->rouge = true;
    a->gauche->rouge = false;
    a->droite->rouge = false;
    return a;
}

Question

Écrire des fonctions utilitaires bool rouge(arbre a) et bool noir(arbre a) qui testent la couleur de la racine. On fera attention au fait que l'arbre vide est noir.

Corrigé 
bool rouge(arbre a)
{
    if (a == NULL) return false;
    return a->rouge;
}

bool noir(arbre a)
{
    return !rouge(a);
}

Question

Écrire des fonctions arbre essai_rotgauche(arbre a), essai_rotdroite et essai_bascule qui n'effectuent ces opérations que dans les cas nécessaires pour l'insertion.

Corrigé 
arbre essai_bascule(arbre a)
{
    if(rouge(a->gauche) && rouge(a->droite))
        return bascule(a);
    return a;
}

arbre essai_rotgauche(arbre a)
{
    if(rouge(a->droite) && rouge(a->droite->droite))
        return rotation_gauche(a);
    return a;
}

arbre essai_rotdroite(arbre a)
{
    if(rouge(a->gauche) && noir(a->droite))
        return rotation_droite(a);
    return a;
}

Dans essai_rotgauche, l'évaluation paresseuse de && garantit que a->droite->droite n'est évalué que si a->droite est rouge, donc non vide.

Question

En déduire une fonction arbre insere(arbre a, int x) qui effectue l'insertion dans un arbre rouge et noir. On pourra définir une fonction auxiliaire arbre insere_aux(arbre a, int x) qui effectue l'insertion et qu'on appellera dans insere avant de faire le noircissement final de la racine.

Corrigé 
arbre insere_aux(arbre a, int x)
{
    if (a == NULL)
        return cree_noeud(x);
    if (a->valeur > x)
        a->gauche = insere_aux(a->gauche, x);
    else
        a->droite = insere_aux(a->droite, x);
    return essai_bascule(essai_rotgauche(essai_rotdroite(a)));
}

arbre insere(arbre a, int x)
{
    arbre a2 = insere_aux(a, x);
    a2->rouge = false;
    return a2;
}

Pour tester, on pourra écrire une fonction qui vérifie les invariants (racine noire, pas de fils gauche rouge, pas de nœud rouge de fils droit rouge, même nombre de nœuds noirs sur chaque branche) et l'appeler après chaque insertion, par exemple en insérant \(0, 1, \dots, n-1\) dans cet ordre : la hauteur doit rester logarithmique.