Programmation Fonctionnelle, TP

Version & licenses
Creative Commons License

TP : Dessin d'arbres binaires, algorithme de Reingold et Tilford

Guyslain Naves

Dans ce TP, nous allons utiliser les types algébriques, d'abord pour définir des arbres binaires génériques, puis pour coder un algorithme de placement des nœuds d'un arbre binaire en vue de le dessiner.

Options

Rappellons le type des options (prédéfini dans Pervasive), qui permettent d'encoder la présence ou l'absence d'une valeur :

  1. type 'value option =
  2. | None
  3. | Some of 'value

Les fonctions suivantes pourront peut-être vous être utiles (mais ne sont pas obligatoires) :

  1. (* À recopier *)
  2. module OptionMonad = struct

  3. let (>>=) opt fct = match opt with
  4. | Some elt -> fct elt
  5. | None -> None

  6. let return value = Some value

  7. let lift_or_id (++) opt1 opt2 =
  8. match opt1, opt2 with
  9. | None, None -> None
  10. | Some elt1, Some elt2 -> Some (elt1 ++ elt2)
  11. | Some elt, None
  12. | None, Some elt -> Some elt

  13. end

Arbres binaires.

Types des arbres binaires.

Proposer un type union pour encoder les arbres binaires, paramêtré par le type des nœuds.

  1. type 'node bintree

Quelques arbres binaires particuliers.

Écrire plusieurs fonctions, qui étant donné un entier $n$, construisent les arbres suivants. Tous les nœuds contiendront une valeur de type unit.

  • l'arbre complet de hauteur $n$,
  • le chemin gauche et le chemin droit de hauteur $n$,
  • la chenille gauche et la chenille droite de hauteur $n$.

Arbre complet de hauteur 3 Chemin gauche de hauteur 6 Chemin droit de hauteur 6 chenille gauche de hauteur 7 chenille droite de hauteur 7

  1. val complete : int -> unit bintree
  2. val left_path : int -> unit bintree
  3. val right_path : int -> unit bintree
  4. val left_caterpillar : int -> unit bintree
  5. val right_caterpillar : int -> unit bintree

Image miroir d'un arbre.

Écrire une fonction calculant l'image miroir d'un arbre, comme illustré par le dessin ci-dessous.

Un arbre quelconque euqnocleuq erbra nU
  1. val mirror : 'node bintree -> 'node bintree

Hauteur d'un arbre.

Écrire la fonction calculant la hauteur d'un arbre binaire.

  1. val height : 'node bintree -> int

Map.

Écrire la fonction map des arbres binaires. map ~f construit une image de l'arbre en remplaçant chaque nœud par son image par la fonction f.

  1. val map : f:('node -> 'im) -> 'node bintree -> 'im bintree

Fold.

Écrire une fonction fold des arbres binaires. Elle doit correspondre à faire un List.fold_left sur une liste des nœuds de l'arbre.

  1. val fold : f:('accu -> 'node -> 'accu) -> 'accu -> 'node bintree -> 'accu

Lister les nœuds.

Écrire une fonction retournant une liste de nœuds d'un arbre binaire, en ordre préfixe. Pour cela, on utilisera une fonction annexe insert_nodes_of tree accu, ajoutant tous les nœuds de tree dans l'accumulateur accu.

  1. val insert_nodes_of : 'node bintree -> 'node list -> 'node list
  2. val nodes_of_tree : 'node bintree -> 'node list

Lister les arêtes.

Écrire une fonction retournant la liste des paires (parent,enfant) d'un arbre binaire. Utiliser une fonction annexe insert_edges_of tree ?father accu, prenant aussi un arbre et un accumulateur en argument, ainsi qu'un argument optionnel précisant le père du nœud racine de tree, s'il existe.

  1. val insert_edges_of :
  2. 'node bintree
  3. -> ?father:'node
  4. -> ('node * 'node) list -> ('node * 'node) list
  5. val edges_of_tree : 'node bintree -> ('node * 'node) list

Intervalles.

Pour l'algorithme de placement des nœuds, il va être capital de représenter l'espace horizontal pris par un arbre, sous la forme d'un intervalle de la ligne des nombres réels. Un intervalle $[\mathit{lower},\mathit{upper}]$, avec $\mathit{lower} \leq \mathit{upper}$, est codé par la donnée de ses deux extrémités $\mathit{lower}$ et $\mathit{upper}$, qui sont des flottants.

Type des intervalles.

Proposer un type produit pour les intervalles.

  1. type interval

Nous continuons avec plusieurs fonctions pour manipuler des intervalles.

Décaler un intervalle

Le décalage de l'intervalle $[\mathit{lower},\mathit{upper}]$ par un flottant $\delta$ est l'intervalle $[\mathit{lower}+\delta, \mathit{upper}+\delta]$. Proposer une fonction pour calculer un décalage.

  1. val shift : float -> interval -> interval

Fusion de deux intervalles

La fusion de deux intervalles $\mathit{inter}_1$ et $\mathit{inter}_2$est le plus petit intervalle contenant $\mathit{inter}_1$ et $\mathit{inter}_2$. Sa borne inférieure est le minimum des deux bornes inférieures, et sa borne supérieure est le maximum des deux bornes supérieures. Écrire une fonction pour la fusion.

  1. val merge : interval -> interval -> interval

Écart de deux intervalles

L'écart des intervalles $[\mathit{lower}_1, \mathit{upper}_1]$ et $[\mathit{lower}_1, \mathit{upper}_1]$ est $\mathit{lower}_2 - \mathit{upper}_1$. Écrire la fonction calculant l'écart de deux intervalles.

  1. val gap : interval -> interval -> float

Niveaux d'un arbre.

Les dessins d'arbres que nous allons faire respecterons la règle : tous les nœuds d'une même profondeur dans l'arbre sont placés avec la même ordonnée (c'est-à-dire sur une ligne horizontale). Pour encoder l'espace pris par le dessin d'un arbre dans le plan, il suffit donc de garder pour chaque niveau de profondeur, l'intervalle entre le nœud le plus à gauche et le nœud le plus à droite.

Un arbre quelconque

Par exemple, pour l'arbre ci-contre, l'encodage est donné par :

profondeurintervalle
0 $[0,0]$
1 $[-1,1]$
2 $[-3,1]$
3 $[-2,2]$

En première approche, nous pourrions donc poser le type des niveaux d'un arbre, donnant un intervalle pour chaque niveau de profondeur, par :

  1. (* Ne pas recopier ! *)
  2. type levels = interval list

Les principales opérations que nous devrons faire sont :

  • décaler tous les intervalles de la listes,
  • fusionner tous les intervalles de deux listes un-à-un,

Or, pour des raisons d'efficacité, nous ne voulons pas calculer ces opérations, sauf si nécessaire. Du coup nous allons utiliser une astuce, consistant à introduire dans le type des niveaux un constructeur pour le décalage (Shift) et un constructeur pour la fusion (Merge) (en plus des constructeurs de listes (Nothing et Interval), soit 4 constructeurs en tout), qui permettent de coder explicitement un décalage des niveaux ou une fusion de deux listes de niveaux, sans les calculer.

Type des niveaux.

Proposer un type inductif à 4 constructeurs pour les listes de niveaux.

  1. type levels

Observer une liste de niveaux.

Un des avantages est que le décalage d'une liste de niveaux, ou la fusion de deux listes de niveaux, sont des opérations en temps constant. En revanche, observer la liste, c'est-à-dire récupérer la tête et la queue de la liste, va devenir une opération plus complexe.

Pour cela, la fonction principale va être :

  1. val observe_levels : levels -> (interval * levels) option

Ainsi, en utilisant match observe_levels levels with, nous retomberons sur un filtrage par motif qui ressemblera à celui d'une liste. Il y a plusieurs cas.

Cas 1 . La liste de niveaux commence par une fusion. Dans ce cas, il suffit d'observer chacun des deux termes de la fusion, et si nécessaire fusionner les têtes avec merge et les queues avec le constructeur adéquat. Coder la fonction correspondante :

  1. val merge_levels :
  2. (interval * levels) option
  3. -> (interval * levels) option
  4. -> (interval * levels) option

Cas 2 . La liste de niveaux commence par deux décalages successifs. Nous les remplaçons par un seul décalage d'une valeur égale à la somme des deux. Puis nous observons cette nouvelle liste de niveaux.

Cas 3 . La liste de niveaux commence par un décalage. Dans ce cas, on observe le terme du décalage, puis on décale la tête avec shift, et la queue avec le constructeur de décalage. Coder la fonction correspondante :

  1. val shift_levels :
  2. delta:float
  3. -> (interval * levels) option
  4. -> (interval * levels) option

Cas 4 . La liste de niveaux commence par un constructeur de liste, il n'y a alors rien à faire pour l'observation.

Finalement, coder la fonction observe_levels.

Algorithme de Reingold et Tilford.

Calcul de l'écart nécessaire entre deux listes de niveaux (I).

L'algorithme de Reingold et Tilford de placement des nœuds procède de façon récursive, du bas vers le haut de l'arbre. Étant donné un placement pour les deux sous-arbres d'un nœud $n$, les deux sous-arbres sont placés côte-à-cote avec leurs racines à la même ordonnée. Ils sont placés le plus proche possible, de sorte que tout nœud du sous-arbre gauche est une abscisse au moins inférieur de 2 à tout nœud du même niveau dans le sous-arbre droit. Enfin, $n$ est placé une ordonnée au dessus et à mi-chemin horizontalement des deux racines.

Le cœur de l'algorithme est de calculer à quelle distance doivent être les deux racines des sous-arbres l'une de l'autre. Si nous utilisions des listes, l'algorithme se décrirait approximativement par :

  1. (* first line slightly incorrect: lengths may be distinct. *)
  2. List.combine left_levels right_levels
  3. |> List.map (fun (interval1,interval2) -> 2 - gap interval1 interval2)
  4. |> List.fold_left max 2

Autrement dit, on calcule niveau par niveau l'écart nécessaire, et on garde le maximum (mais au moins 2).

Puisque nous n'avons pas utilisé les listes, il nous faut réécrire cet algorithme via une récursion. Une version simplifiée aurait pour type :

  1. val compute_necessary_gap : levels -> levels -> float

et calculerait récursivement l'écart entre les queues de deux listes, l'écart nécessaire entre les têtes, et retournerait le maximum des deux. Dans un premier temps, coder cette fonction.

Calcul de l'écart nécessaire entre deux listes de niveaux (II).

Dans cette première version, pour combiner les deux listes, de nombreux appels à observe_levels ont été fait, qui ont potentiellement considérablement simplifié les deux listes de niveaux, en repoussant les Shift et Merge vers la fin des deux listes. Or, nous n'en avons gardé aucune trace, et donc tout le calcul devra être refait par la suite si nécessaire. Modifier compute_necessary_gap pour qu'elle retourne aussi les deux listes de niveaux simplifiées. Son type sera alors :

  1. val compute_necessary_gap : levels -> levels -> (float * levels * levels)

Annoter l'arbre avec les décalages nécessaires.

D'après la description de l'algorithme, l'information nécessaire est de connaître pour chaque nœud, la distance horizontale entre ses deux fils. Une fois connue cette information, il sera possible de construire l'arbre en partant de la racine. Dans un premier temps, nous devons donc calculer pour chaque nœud, cette distance horizontale : le décalage de ce nœud. Nous le faisons par un algorithme récursif (de type bottom-up).

Pour calculer le décalage d'un nœud, il faut commencer par construire la liste des niveaux de ces deux fils, et par la même occasion leurs décalages. Ceci s'effectue par récursion. Ensuite, compute_necessary_gap nous donne le décalage pour la racine. Enfin, pour la récursion, il faut aussi construire la liste de niveau du nœud, en décalant (avec Shift) les deux listes des sous-arbres par la moitié du décalage de la racine, et en les fusionnant (avec Merge), et en ajoutant devant l'intervalle pour le niveau de la racine : $[0,0]$.

Écrire la fonction correspondante, qui retourne l'arbre annoté des décalages de chaque nœuds, et la liste des niveaux de l'arbre :

  1. val annotate_with_offset : 'node bintree -> ('node * float) bintree * levels

Annoter l'arbre avec les positions des nœuds.

Le plus dur est fait. Nous plaçons maintenant la racine en position $(0,0)$, puis par une récursion, descendons dans l'arbre annoté pour placer les nœuds des sous-arbres.

Écrire la fonction de placement des nœuds depuis un arbre annoté :

  1. val annotate_with_position :
  2. ~root_pos:(float * float)
  3. -> ('node * float) bintree
  4. -> ('node * (float * float)) bintree

La racine d'un sous-arbre d'un nœud $n$ a son ordonnée inférieur de 1 par rapport à celle de $n$, et son abscisse à distance $\mathit{gap}/2$ de celle de $n$, avec $\mathit{gap}$ le décalage encodé dans l'arbre annoté.

Finaliser l'algorithme.

Combiner les éléments pour obtenir une fonction :

  1. val layout : 'node bintree -> ('node * (float * float)) bintree

Affichage graphique d'un arbre binaire.

Il devrait maintenant être facile de créer une image d'un arbre binaire. Nous proposons d'utiliser au choix la librairie Graphics, ou si vous l'avez sur votre machine la librairie Vg (utilisée pour réaliser les figures de cette page).

Avec Graphics.

Ouvrir la fenêtre graphique.

Dans le toplevel, charger la librairie et ouvrir une fenêtre avec les dimensions souhaitées.

  1. (* #load "graphics.cma";; (* Dans le toplevel *) *)
  2. open Graphics

  3. let () = open_graph ""
  4. let () = Graphics.resize_window 400 400
Dessiner un nœud.

Utiliser Graphics.fill_circle pour écrire une fonction dessinant un nœud draw_node pixel_of_position position. pixel_of_position sera définie plus tard.

  1. val draw_node : (float * float -> int * int) -> float * float -> unit
Dessiner une arête.

Utiliser Graphics.moveto et Graphics.lineto pour écrire une fonction dessinant une arête, avec le même format que draw_node.

  1. val draw_edge :
  2. (float * float -> int * int)
  3. -> (float * float) * (float * float)
  4. -> unit
Calculer les dimensions du dessin.

Utiliser la fonction fold des arbres binaires pour calculer les abscisses minimum et maximum, les ordonnées minimum et maximum, d'un arbre binaire dont les nœuds sont des positions.

  1. val minimum_abscissa : (float * float) bintree -> float
  2. val maximum_abscissa : (float * float) bintree -> float
  3. val minimum_ordinate : (float * float) bintree -> float
  4. val maximum_ordinate : (float * float) bintree -> float
Combiner les ingrédients.

Compléter la fonction de dessin, en utilisant List.iter sur les listes de nœuds et d'arêtes :

  1. let draw_tree tree =
  2. let layout_tree = (* TODO *) in
  3. let x_min = min_abscissa layout_tree -. 1. in
  4. let x_max = max_abscissa layout_tree +. 1. in
  5. let y_min = min_ordinate layout_tree -. 1. in
  6. let y_max = max_ordinate layout_tree +. 1. in
  7. let width = float (Graphics.size_x ()) in
  8. let height = float (Graphics.size_y ()) in
  9. let pixel_of_position (x,y) =
  10. ( int_of_float ( (x -. x_min) /. (x_max -. x_min) *. width,
  11. int_of_float ( (y_max -. y) /. (y_max -. y_min) *. height
  12. )
  13. in
  14. Graphics.clear_graph ();
  15. (* TODO *)

Avec Vg.

Charger Vg.

Créer un fichier .merlin dans le répertoire courant, contenant :

  1. PKG vg gg vg.svg

Sous emacs, dans le menu Merlin, sélectionner Restart merlin.

Sous emacs, fermer le toplevel en tapant exit 0;;dedans. Relancer le toplevel en ré-évaluant le buffer, mais cette fois utiliser l'exécutable utop.

Dans le toplevel, exécuter :

  1. (* uniquement sous utop : *)
  2. #require "unix";;
  3. #require "vg";;
  4. #require "vg.svg";;
Dessiner un nœud.

Vg est basé sur le principe du découper-coller : on découpe des formes dans des feuilles de papier colorées, puis on les colle sur une image. Il y a donc un module pour le découpage Vg.P qui se fait en définissant le chemin (P pour path) par lequel passe la paire de ciseaux. Et il y a un module pour le collage Vg.I (I pour image).

Vg s'appuie sur Gg pour les calculs vectoriels et les couleurs. Nous utiliserons principalement Gg.V2 pour les vecteurs à deux dimensions, et Gg.Color pour les couleurs.

Pour dessiner un nœud, on part d'un chemin vide, puis on crée une forme de cercle, que l'on colle à l'image. On utilise les fonctions suivantes :

  1. (* Créer un vecteur *)
  2. val Gg.V2.v : float -> float -> Gg.V2.t

  3. (* le chemin circulaire : *)

  4. (* le chemin vide *)
  5. val Vg.P.empty : Vg.path
  6. (* [circle center radius] ajoute un cercle au chemin *)
  7. val Vg.P.circle : Gg.V2.t -> float -> Vg.path -> Vg.path

  8. (* Couper le chemin dans une feuille *)

  9. (* une image unie *)
  10. val Vg.I.const : Gg.color -> Vg.image

  11. (* découper une forme dans une image selon un chemin *)
  12. val Vg.I.cut : Vg.path -> Vg.image -> Vg.image

  13. (* [blend forme image] est le collage de la [forme] sur l'[image]. *)
  14. val Vg.I.blend : Vg.image -> Vg.image-> Vg.image

Créer un chemin circulaire, le couper dans une feuille noire, puis le coller sur une image donnée en argument :

  1. val draw_node : Vg.image -> (float * float) -> Vg.image
Dessiner une arête.

Utiliser les mêmes principes pour le dessin d'une arête. Dans ce cas, notons que nous ne voulons pas découper l'intérieur d'une forme, mais juste son contour. Pour cela, il faut donner un argument supplémentaire à Vg.I.cut.

  1. (* Pour faire la forme d'un segment : *)

  2. (* Déplacer les ciseaux vers un point, sans découper. *)
  3. val Vg.P.sub : Gg.V2.t -> Vg.path -> Vg.path

  4. (* Couper jusqu'à un point : *)
  5. val Vg.P.line : Gg.V2.t -> Vg.path -> Vg.path

  6. (* Pour couper le contour d'un chemin, exemple : *)
  7. let cut_contour path =
  8. let outline = { Vg.P.o with Vg.P.width = 0.05 } in
  9. Vg.I.const Gg.color.black
  10. |> Vg.I.cut ~area:(`O outline) path

Écrire la fonction :

  1. val draw_edge : Vg.image -> ((float*float) * (float*float)) -> Vg.image
Construire le rectangle contenant l'arbre.

Comme avec Graphics, donner des fonctions pour récupérer les coordonnées minimum et maximum des nœuds de l'arbre.

  1. val minimum_abscissa : (float * float) bintree -> float
  2. val maximum_abscissa : (float * float) bintree -> float
  3. val minimum_ordinate : (float * float) bintree -> float
  4. val maximum_ordinate : (float * float) bintree -> float

En déduire une fonction calculant la diagonale et le centre du rectangle d'un arbre (ajouter une marge de 1 de chaque côté).

  1. (* [(center,diagonal) = bounding_box tree] *)
  2. val bounding_box : (float * float) bintree -> Gg.V2.t * GG.V2.t
Calculer la vue de l'arbre.

Nous venons de voir comment calculer le plus petit rectangle contenant l'arbre, mais nous voulons afficher une image avec une largeur et une hauteur donnée, et le ratio largeur/hauteur n'est pas nécessairement le même que celui du rectangle. Nous le corrigeons ainsi :

  1. val view_of_bounding_box : float -> Gg.V2.t * Gg.V2.t -> Gg.box2

  2. let view_of_bounding_box aspect (center, diagonal) =
  3. let open Gg in
  4. let box_dim =
  5. if V2.x diagonal /. V2.y diagonal > aspect then
  6. V2.v (V2.x diagonal) (V2.x diagonal /. aspect)
  7. else V2.v (aspect *. V2.y diagonal)(V2.y diagonal)
  8. in
  9. Box2.v V2.(center - 0.5 * box_dim) box_dim
L'image d'un arbre.

Une image affichable se compose de l'image elle-même, de la taille désirée exprimée par un vecteur Gg.V2.t en millimètre, et de la vue calculée à la question précédente. Écrire la fonction créant une telle image depuis un arbre et une spécification de la taille de l'image voulue.

  1. val draw_tree :
  2. ?width:float
  3. -> ?height:float
  4. -> 'node tree
  5. -> (Gg.V2.t * Gg.box2 * Vg.image)
Rendu de l'image.

À partir de là, l'image peut être affichée dans un canvas html, dans un fichier pdf ou dans un fichier svg. Nous choisissons la dernière option. On utilise le code suivant (à modifier légèrement) :

  1. let render_image ?(title="A binary tree") out_channel (size,view, image) =
  2. let xmp = (* metadata *)
  3. Vg.Vgr.xmp
  4. ~title
  5. ~authors:["TODO: add your name here"]
  6. ~create_date:(Unix.gettimeofday ())
  7. ()
  8. in
  9. let target = Vgr_svg.target ~xmp () in
  10. let renderer = Vg.Vgr.create target (`Channel out_channel) in
  11. Vg.Vgr.render renderer (`Image (size,view,image)) |> ignore;
  12. Vg.Vgr.render renderer `End |> ignore;
  13. ()

render_image prend un titre pour l'image, un descripteur de fichier en sortie out_channel : Pervasive.out_channel, et l'image, et écrit l'image dans le descripteur.

Nous le complétons avec l'ouverture et la fermeture d'un fichier :

  1. let output_image ?title ?width ?height filename tree =
  2. let out_channel = open_out filename in
  3. tree
  4. |> draw_tree ?width ?height
  5. |> render_image ?title out_channel;
  6. close_out out_channel

Générer aléatoirement des arbres binaires.

Pour finir, voici trois fonctions pour générer des arbres binaires aléatoires.

  1. let rec random_tree_v1 ~distr current_depth =
  2. if Random.float 1. > distr current_depth then
  3. Leaf
  4. else
  5. Node (random_tree_v1 ~distr (current_depth + 1),
  6. (),
  7. random_tree_v1 ~distr (current_depth + 1))

  8. let distr1 depth = 2. /. 1.2 ** (float n)
  9. let distr2 depth =
  10. if depth < 5 then 1.
  11. else 0.48

Arbre aléatoire. Arbre aléatoire. Arbre aléatoire.

Arbre aléatoire. Arbre aléatoire. Arbre aléatoire.

  1. let rec random_tree_v2 ~distr nbr_nodes =
  2. if nbr_nodes = 0 then Leaf
  3. else
  4. let left_nodes = int_of_float ( distr () *. float (nbr_nodes - 1)) in
  5. Node (random_tree_v2 ~distr left_nodes,
  6. (),
  7. random_tree_v2 ~distr (nbr_nodes - 1 - left_nodes)
  8. )

  9. let distr = (fun () -> Random.float 1.)

Arbre aléatoire. Arbre aléatoire. Arbre aléatoire.

Le troisième générateur permet de créer des arbres plus profonds. Avec un grand nombre de nœuds, votre algorithme risque de provoquer un stack overflow. Pour les arbres de hauteur 100.0 00 ou plus, il faudrait réécrire votre algorithme en utilisant ContinuationMonad pour toutes les récursions, comme ci-dessous.

  1. module ContinuationMonad = struct
  2. type 'value m = { apply : 'b . ('value -> 'b) -> 'b }

  3. let return v = { apply = fun f -> f v }

  4. let (>>=) value_m fct =
  5. { apply =
  6. fun res_to_any ->
  7. value_m.apply (fun value -> (fct value).apply res_to_any)
  8. }

  9. let run value fct = value.apply fct
  10. let run_with_id value = run value (fun x -> x)
  11. end


  12. let rec add_left_path length tree =
  13. let open ContinuationMonad in
  14. if length = 0 then return tree
  15. else
  16. return () >>= fun () ->
  17. add_left_path (length-1) tree >>= fun res ->
  18. return (Node (res,(),Leaf))

  19. let rec add_right_path length tree =
  20. let open ContinuationMonad in
  21. if length = 0 then return tree
  22. else
  23. return () >>= fun () ->
  24. add_right_path (length-1) tree >>= fun res ->
  25. return (Node (Leaf,(),res))

  26. let random_tree_v3 nbr_nodes =
  27. let open ContinuationMonad in
  28. let rec generate nbr_nodes =
  29. let half = int_of_float (Random.float 1. *. float (nbr_nodes-1)) in
  30. match Random.int 6 with
  31. | _ when nbr_nodes = 0 -> return Leaf
  32. | 1 -> generate half >>= add_left_path (nbr_nodes-half)
  33. | 2 -> generate half >>= add_right_path (nbr_nodes-half)
  34. | any ->
  35. generate half >>= fun left ->
  36. generate (nbr_nodes-half-1) >>= fun right ->
  37. return (Node (left,(),right))
  38. in
  39. run_with_id (generate nbr_nodes)

Arbre aléatoire. Arbre aléatoire. Arbre aléatoire.

Et une fonction pour chronométrer votre algorithme. Quel comportement asymptotique semble-t-il avoir ?(gare aux stack overflow sur de trop gros arbres).

  1. let chrono fct =
  2. let start_time = Unix.gettimeofday () in
  3. let res = fct () in
  4. let end_time = Unix.gettimeofday () in
  5. (res, end_time -. start_time)


  6. let _ =
  7. (fun () -> layout (random_tree_v2 ~distr 100_000))
  8. |> chrono
  9. |> snd