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(nom₁:X₁ ... nom_n:X_n)`	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

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.
- Quel est le second menu ? A quel champ de Carte correspond-il ?
- Quel est le plat du second menu ? Quelle est l'entrée du premier menu ? De quel type sont ces valeurs ?
- Supposons qu'un groupe de personnes se rendent dans ce restaurant, que N1 personnes commandent le premier menu, N2 personnes le second et N3 personnes le troisième. Quel prix vont-ils payer au total ?
- Quelle est l'arité de la carte ? Quelle est celle de chacun des menus ?
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.
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>)
- Définissez une fonction Promenade qui réalise un parcours en profondeur d'abord d'un arbre. Dans ce type de parcours, le sous-arbre gauche d'un noeud est parcouru entièrement avant son sous-arbre droit. L'appel {Promenade BT} renvoie la liste des valeurs des noeuds visités dans l'arbre BT. Le noeud racine d'un arbre est toujours visitée avant ses sous-arbres.
```
   %% affiche [42 26 54 18 37 11]
   {Browse {Promenade btree(42
                            left: btree(26
                                        left: btree(54
                                                    left: empty
                                                    right: btree(18
                                                                 left: empty
                                                                 right: empty))
                                        right: empty)
                            right: btree(37
                                         left: btree(11
                                                     left: empty
                                                     right: empty)
                                         right: empty))}}
```
- Utilisez cette fonction pour calculer la somme des valeurs d'un arbre binaire contenant des entiers.
- Définissez une fonction qui calcule la somme des valeurs d'un arbre en effectuant elle-même un parcours de l'arbre.
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.
- Pour construire l'arbre ordonné, définissez une fonction InsertElements qui prend en argument une liste de valeurs et un arbre ordonné, et renvoie l'arbre dans lequel on a inséré les éléments de la liste. Chaque élément de la liste est à la fois clé et valeur dans l'arbre. L'appel
```
   {InsertElements [42 17 23] tree(key:31 value:31 leaf leaf)}
```
  renvoie l'arbre
```
   tree(key:31 value:31
        tree(key:17 value:17
             leaf
             tree(key:23 value:23
                  leaf
                  leaf))
        tree(key:42 value:42
             leaf
             leaf))
```
- Ecrivez une fonction Keys qui prend un arbre ordonné et renvoie la liste de ses clés en ordre croissant. Si T est l'arbre renvoyé ci-dessus, alors {Keys T} renvoie la liste [17 23 31 42].
- Définissez maintenant la fonction OrderedTreeSort, qui prend une liste en argument et renvoie la liste triée. Cette fonction utilise bien sûr les deux précédentes.
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>)
- Ecrivez une fonction Infix qui effectue un parcours infixe d'un tel arbre. Cette fonction prend un <btree> en argument et renvoie une liste contenant les valeurs des feuilles de l'arbre, lues de gauche à droite. Par exemple, l'appel de fonction
```
   {Infix tree(leaf(1)
               tree(tree(tree(leaf(2)
                              tree(leaf(3)
                                   leaf(4)))
                         leaf(5))
                    leaf(6)))}
```
  renvoie la valeur [1 2 3 4 5 6].
- Ecrivez une fonction IsBalanced qui prend un <btree> en argument et renvoie true s'il est équilibré, false sinon. Un arbre tree(L R) est équilibré si ses sous-arbres L et R sont équilibrés, et s'ils ont le même nombre de feuilles, à une unité près. Un arbre constitué d'une seule feuille est équilibré.
  
  Aide: Ecrivez d'abord une fonction qui renvoie le nombre de feuilles d'un <btree>.
- Ecrivez une fonction MakeTree qui construit un <btree> équilibré à partir d'une liste de valeurs donnée en argument. La liste donnée en argument doit correspondre à l'appel de Infix sur l'arbre résultat. Testez votre fonction avec Infix et IsBalanced pour vérifier que le résultat a bien les propriétés voulues.
  
  Par exemple, l'appel {MakeTree [1 2 3 4 5 6]} peut renvoyer l'arbre
```
   tree(tree(leaf(1)
             tree(leaf(2)
                  leaf(3)))
        tree(leaf(4)
             tree(leaf(5)
                  leaf(6))))
```
  Note 1. Ce n'est pas le seul arbre équilibré possible pour cet exemple. Vous devez définir précisément le choix que vous faites pour construire un arbre équilibré.
  
  Note 2. Vous pouvez utiliser le module Drawer pour visualiser l'arbre construit.
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>)
- Ecrivez une fonction AddCount qui convertit un <btree> en le <btreecount> correspondant.
- Ecrivez une fonction MakeTreeCount, similaire à votre fonction MakeTree, mais qui renvoie un <btreecount>.
- Ecrivez une fonction NthLeaf qui prend en argument un <btreecount> BTC, ainsi qu'un entier N et renvoie la valeur se trouvant dans la N-ième feuille de BTC. L'appel {NthLeaf {MakeTreeCount L} N} renvoie la même valeur que {Nth L N}. Quel est l'avantage de NthLeaf par rapport à Nth ? En particulier, quel est la complexité temporelle d'un appel à NthLeaf ?

Notes

Le module Drawer permet de visualiser une valeur Oz comme un arbre. Pour l'utiliser,

   %% charger le module (une fois)
   declare
   [Drawer] = {Module.link ["http://www.info.ucl.ac.be/notes_de_cours/FSAB1402/tools/Drawer.ozf"]}
   Draw = Drawer.draw

   %% afficher une valeur
   {Draw Valeur}

Raphaël Collet - 28 octobre 2005

Séance 6 Enregistrements et arbres

Enoncés des exercices

Notes

Séance 6
Enregistrements et arbres