Présentation de la bibliothèque ASDA

Fonctionnalités de la bibliothèque ASDA

• ASDA = Algorithmique des Structures de Données Arborescentes.
  
• ASDA facilite les tests et permet la visualisation d'arbres.
  
• La bibliothèque ASDA se compose de deux sous-modules :
  
  • View, pour afficher les arbres sous forme graphique.
    
  • Rand, pour générer des arbres de différentes sortes.
    

Structure de la bibliothèque

• Pour l'utiliser : open Asda définit les types :
  

  type 'a tree = Empty | Bin of 'a * 'a tree * 'a tree
  type 'a rb = EmptyRB | Red of 'a * 'a rb * 'a rb
                       | Black of 'a * 'a rb * 'a rb
  

• Puis : View.f appelle la fonction f du sous-module View.
  
• Optionnel : open View évite d'avoir à taper «View.».
  

Installation et utilisation

• Installation.
  

  bash <(curl -s http://www.labri.fr/perso/zeitoun/opam_emacs_script)

  
  Ce script installe aussi une configuration pour Emacs.
  Il est donc inutile de le relancer s'il a été utilisé pour installer Emacs.
  
• NOTE : relancer la session CREMI avant la 1ère utilisation.
  

• Après installation et avant utilisation, en début de fichier :
  

  (* accès aux types *)
  open Asda
  (* accès aux fonctions de visualisation sans le préfixe View. *)
  open View
  (* accès aux générateurs sans le préfixe Rand. *)
  open Rand
  

Description des fonctions fournies

Fonctions d'affichage

Le module View fournit 4 fonctions d'affichage :

• view : affiche un arbre d'étiquettes int.
  
• view_mult : affiche un arbre d'étiquettes int*int.
  
  • 2^ème composante = multiplicité (affichée au dessus des nœuds).
    
• view_rb : comme view, pour les arbres bicolores.
  
• view_rb_mult : comme view_mult, pour les arbres bicolores.
  

Fonctions de génération aléatoire

Le module Rand fournit des générateurs d'arbres et d'ABR.

• bintree et bintree' : arbres binaires.
  
  • bintree est uniforme (à taille donnée, arbres équiprobables).
    
• full : arbres binaires pleins.
  
• perfect, quasi-perfect, almost_perfect : arbres parfaits, quasi-parfaits, et "proches" des arbres parfaits.
  
• unbalanced_right : arbres ayant plus de nœuds à droite.
  
• bst : arbres binaires de recherche.
  
• avl : AVL.
  
• rb : arbres rouges et noirs.
  

Exemple d'utilisation

Toute les fonctions de génération d'arbres prennent un argument : ().

open Asda
open View
open Rand

let _ = view (Bin(42, Empty, Empty))

(* la fonction bintree construit un arbre sans multiplicité *)
let t = bintree ()
let _ = view t

(* les fonctions avl et rb construisent un arbre avec multiplicité *)
let t = avl ()
let _ = view_mult t

let t = rb ()
let _ = view_rb_mult t

Paramètres optionnels de génération

• Les fonctions prennent toutes un paramètre () de type unit.
  
• On peut spécifier une taille pour bintree, full, bst, avl, rb.
  
• On peut spécifier une hauteur pour perfect et quasi_perfect.
  

• Syntaxe :
  

  let t = bintree ~size:42 ()
  let _ = view t
  let t = quasi_perfect ~height:5 ()
  let _ = view t
  

Paramètres optionnels d'affichage

• Les fonctions d'affichage ne prennent pas de paramètre ().
  
• On peut spécifier si on affiche les sous-arbres vides, les couleurs…
  

• Exemple :
  

  let myview_mult t = view_mult
                        ~show_empty:true
                        ~node_fillcolor:"e1ffdf" ~node_color:"e1eeca"
                        ~empty_fillcolor:"ffe1df" ~empty_color:"ffbaba"
                        t
  
  let _ = myview_mult (bst ~size:20 ())
  

Restrictions

• La bibliothèque gère les affichages avec moins de 100 nœuds.
  
• La taille des nœuds est fixe.
  
• Pour > 100 nœuds, si l'arbre n'est pas visualisable :
  
  • exporter en format svg (paramètre ~format).
    
  • ouvrir tmp.svg avec Inkscape.