Module Trees

Module Trees

The module contains an implementation of a dictionary by binary search trees. The condition on the search-tree is that for all nodes the keys are ordered, i.e. key_l £ key £ key_r, where key is the key of the node and key_l and key_r are the keys of the two children. The tree may contain two elements with the same key (see insert).

The constructor implementation in ocaml means that they are unidirectionally chained. Therefore determining the successor or a predecessor is complicated.

module STREEFun(Key:ORDERED)(Elem:TYPE) =
   struct
     exception Not_Found

     type elem = Elem.t
     type key = Key.t

     type (a, b) bstree = (* binary search tree *)
         Leaf | Node of (a,b) bstree × (a ×b) × (a,b) bstree

     type dict = (key,elem) bstree (* dictionary as binary search tree *)

     let empty = Leaf

     let rec delete_succ tr = (* deletes the first element, where first is defined in appearing in in-order. Succeeds exactly if tr is not a leaf.

Additionally it gives back the info of the deleted node. *)

       match tr with
         Leaf ® raise Not_Found
       | Node(Leaf,n,tr_r) ® (tr_r, n)
       | Node(tr_l,n,tr_r) ®
           let (tr_l',n') = delete_succ tr_l
           in (Node(tr_l', n, tr_r), n')

     let rec insert tr (key, elem) = (* Insert always at the leaves *)
       match tr with
         Leaf ® Node (Leaf, (key, elem), Leaf)
       | Node(tr_l, (key', elem'), tr_r) ®
           if key = key' (* Fifo insertion, right-side is important, too *)
           then Node(tr_l , (key, elem), insert tr_r (key', elem'))
           else if (key<key')
           then Node(insert tr_l (key, elem), (key', elem'), tr_r)
           else Node( tr_l , (key', elem'), insert tr_r (key, elem))

     let rec search tr key =
       match tr with
         Leaf ® raise Not_Found
       | Node(tr_l, (key', elem'), tr_r) ®
           if (key = key') then elem'
           else
             if key < key'
             then search tr_l key
             else search tr_r key

     let delete tr key =
       let rec delete' tr key =
         match tr with
           Leaf ® raise Not_Found
         | Node(Leaf, (k,e), Leaf) ®
             if key = k (* found *)
             then (Leaf, (k,e))
             else raise Not_Found
         | Node(tr_l, (k,e), tr_r) ®
             if key = k (* found *)
             then
               match (tr_l, tr_r) with
                 (Leaf, _) ® (tr_r,(k,e))
               | (_ , Leaf) ® (tr_l,(k,e))
               | _ ® (* Nachfolger *)
                   match
                     (delete_succ tr_r)
                   with
                     (tr_r',(ks,es)) ®
                       (Node(tr_l, (ks, es), tr_r'), (k,e))
             else if (key<k)
             then
               let (tr_l',n') = delete' tr_l key
               in
               (Node(tr_l',(k,e),tr_r),n')
             else
               let (tr_r', n') = delete' tr_r key
               in
               (Node(tr_l,(k,e),tr_r'),n')
       in
       fst (delete' tr key)

     let print_dict d = print_endline (" no info")

   end

delete: in CLR90, deletion takes the actual node as parameter (the pointer to it) and deletes it. In G90 wird angenommen, dass der Schluessel eindeutig ist, damit ist das Loeschen einfacher.
January 31, 2002