(* Code for Lecture 5: Datatypes *) (************************************************************************) datatype 'a tree = Empty | Node of 'a * 'a tree * 'a tree (* size of a tree size: 'a tree -> int size(T) = n where n is size of the tree determined by the number of nodes. *) fun size (Empty) = 0 | size (Node(a, L, R)) = size(L) + size(R) + 1 (* insert: (int * 'b) -> (int * 'b) tree -> (int * 'b) tree insert (x,d) T = T' where (x,d) has been inserted into T and any previous occurrences of (x,d') in T have been overwritten *) fun insert (e as (x,d)) Empty = Node(e, Empty, Empty) | insert (e as (x,d)) (Node((y,d'), L, R)) = if x = y then Node(e, L, R) else (if x < y then Node((y,d'), insert e L, R) else Node((y,d'), L, insert e R)) (* lookup : int -> (int * 'b) tree -> 'b option lookup x T = if there exists a node in T with key x and data d, then return SOME(d) else NONE NOTE: Although the type of this function is polymorphic in 'a and 'b, it depends on the fact that we do have functions to compare elements of type 'a! *) fun lookup x Empty = NONE | lookup x (Node((y,d), L, R)) = if x = y then SOME(d) else (if x < y then lookup x L else lookup x R) (* NOTE: We enforce the property : lookup x (insert (x,d) t) = SOME(d) *) (************************************************************************) (* Examples of trees *) val t1 = Node(9, Node(3, Node(2, Empty, Empty), Node(5, Node(4, Empty, Empty), Node(6, Empty, Empty))), Node(13, Node(11, Empty, Empty), Node(15, Empty, Empty))); (* 9 / \ 3 13 / \ / \ 2 5 11 15 / \ 4 6 *)