Séance 6
Enregistrements et arbres

Cette séance est consacrée aux enregistrements et aux structures de données qu'ils permettent de construire, notamment les arbres. Rappelons qu'un enregistrement est composé d'une étiquette (atome) et d'un certain nombre de champs. Chaque champ est identifié par un nom (atome ou nombre).

Opération Description Complexité temporelle
etiquette(nom1:X1 ... nomn:Xn) crée un enregistrement Θ(n)
R.N renvoie le champ N de l'enregistrement R Θ(1)
{Label R} renvoie l'étiquette de l'enregistrement R Θ(1)
{Width T} renvoie le nombre de champs de l'enregistrement R Θ(1)
{Arity R} renvoie la liste des noms de champs de l'enregistrement R Θ(1)

Enoncés des exercices

  1. Enregistrements. Considérez l'enregistrement suivant. Il représente la carte des menus d'un restaurant.

       Carte = carte(menu(entree: 'salade verte aux lardons'
                          plat: 'steak frites'
                          prix: 10)
                     menu(entree: 'salade de crevettes grises'
                          plat: 'saumon fume et pommes de terre'
                          prix: 12)
                     menu(plat: 'choucroute garnie'
                          prix: 9))
    
    En utilisant la variable Carte, répondez aux questions suivantes.

  2. Listes, tuples, enregistrements. Voici un ensemble d'enregistrements. Pour chacune, indiquez s'il s'agit d'une liste, d'un tuple ou d'un enregistrement. Etant donné qu'une liste est un cas particulier de tuple, et qu'un tuple est un cas particulier d'enregistrement, donnez le type le plus précis.

    '|'(a b)     '|'(a '|'(b nil))     '|'(2:nil a)     state(1 a 2)     state(1 3:2 2:a)     tree(v:a T1 T2)

    Vous pouvez vérifier vos réponses avec les fonctions IsList et IsTuple. {IsList X} renvoie true si X est une liste, false sinon. IsTuple fonctionne de manière similaire avec les tuples.

  3. Promenade arboricole. Considérez la grammaire suivante. Elle définit un type pour des arbres binaires dont les noeuds contiennent une valeur de type T. Un arbre binaire est soit un arbre vide, soit un noeud contenant une valeur et deux sous-arbres.

    <btree T> ::= empty | btree(T left:<btree T> right:<btree T>)

  4. Trier une liste avec des arbres. Dans cet exercice, vous allez implémenter une méthode de tri qui utilise des arbres ordonnés. Nous avons vu au cours une implémentation d'arbres ordonnés : orderedtree.oz. Pour trier une liste, on construit un arbre ordonné qui contient toutes les valeurs de la liste, puis les valeurs sont lues dans l'arbre dans l'ordre croissant. On fait l'hypothèse que les éléments de la liste sont distincts.

  5. Construction d'un arbre équilibré. Considérez des arbres binaires <btree> définis par la grammaire ci-dessous. Dans ces arbres, seules les feuilles contiennent une information.

    <btree> ::= leaf(<value>) | tree(<btree> <btree>)

    Nous allons maintenant enrichir la structure de données. Dans les arbres binaires <btreecount> définis ci-dessous, chaque sous-arbre contient en plus un entier. Si T est un <btreecount>, alors T.count donne le nombre de feuilles dans cet arbre.

    <btreecount> ::= leaf(<value> count:1) | tree(<btreecount> <btreecount> count:<int>)

Notes


Raphaël Collet - 28 octobre 2005