WikiLuc

Guest connection: login: Guest, password: anonymous

User Tools

Site Tools


dit:cours:prog1:cours06

Recherche dans un arbre par continuation

Voir ci-dessous pour le fichier mitree.ml. Voici l'arbre qui est construit dans l'exemple.

#use "mitree.ml";;
 
open Mitree;;
 
let search a t k =
  let break () = k true in
  let rec search_aux t k =
    begin
      tick();
      if is_empty t then k ();
      if (get_node t) = a then break ();
      let k' () = search_aux (get_right t) k
      in search_aux (get_left t) k'
    end
  in search_aux t (fun () -> k false)
 
exception End_of_world;;
 
let cont b =
  print_endline (if b then "Found!" else "Not Found...");
  raise End_of_world
;;
 
let test n t =
  print_endline "______________________";
  reset();
  print_endline ("Searching " ^ (string_of_int n) ^"..." );
  try
    search n t cont;
  with
  | End_of_world -> print_endline ("Number of explored nodes: " ^ (string_of_int (get())))
;;
 
let t0 = make_single 80;;
let l = [40; 120; 20; 60; 100; 140; 10; 30; 50; 70; 90; 110; 130; 150];;
List.iter (fun x -> insert x t0) l;;
print t0;;
 
let test_values = [40; 121; 20; 61; 100; 141; 10; 31; 50; 71; 90; 111; 130; 151];;
 
List.iter (fun n -> test n t0) test_values;;

(********* Module Milist *********)
 
module type Mitree =
sig
  type mitree (* Opaque type *)
  val empty : unit -> mitree
  val make : int -> mitree -> mitree -> mitree
  val get_node : mitree -> int
  val get_left : mitree -> mitree
  val get_right : mitree -> mitree
  val is_empty : mitree -> bool
  val print :  mitree -> unit
  val replace_left : mitree -> mitree -> unit
  val replace_right : mitree -> mitree -> unit
end
;;
 
module Mitree =
struct
  type mitree = Empty | Node of node
  and node = {item: int; left: mitree ref; right: mitree ref};;
 
  let empty () = Empty;;
 
  let make x t1 t2 = Node {item = x; left = (ref t1); right = (ref t2)}
 
  let get_node t =
    match t with
    | Node n -> n.item
    | Empty -> failwith "get_node"
 
  let get_left t =
    match t with
    | Node n -> !(n.left)
    | Empty -> failwith "get_left"
 
  let get_right t =
    match t with
    | Node n -> !(n.right)
    | Empty -> failwith "get_right"
 
  let is_empty t =
    match t with
    | Node n -> false
    | Empty -> true
 
  let print t =
    let rec aux t =
      if is_empty t then print_string "."
      else begin
        print_string "(";
        print_int (get_node t);
        print_string " ";
        aux (get_left t);
        print_string " ";
        aux (get_right t);
        print_string ")"
      end
    in begin
      aux t; print_newline ()
    end
 
  (**************)
 
  let replace_left t t' =
    match t with
    | Node n -> (n.left := t')
    | _ -> failwith "replace_left"
 
  let replace_right t t' =
    match t with
    | Node n -> (n.right := t')
    | _ -> failwith "replace_right"
 
end
;;
 
(************* additional functions *******************)
 
open Mitree;;
 
let make_single x = let e = empty () in make x e e;;
 
let (reset, tick, get) =
  let c = ref 0 in (
    (fun () -> (c := 0)),
    (fun () ->  (c := !c + 1)),
    (fun () -> (!c)))
;;
 
let rec insert x t =
  (if is_empty t then failwith "insert");
  let a = get_node t in begin
    (if x = a then failwith "insert");
    if x < a then
      let t' = get_left t in
      if is_empty t' then replace_left t (make_single x)
      else insert x t'
    else
      let t' = get_right t in
      if is_empty t' then replace_right t (make_single x)
      else insert x t'
  end
;;

dit/cours/prog1/cours06.txt · Last modified: 2017/10/16 17:20 (external edit)