#light
type Elem = int
type Tree = E | T of Tree * Elem * Tree
let empty = E
let rec mem = function
| x, E -> false
| x, T(a, y, b) when x < y -> mem(x, a)
| x, T(a, y, b) when y < x -> mem(x, b)
| _ -> true
let rec insert = function
| x, E -> T(E, x, E)
| x, T(a, y, b) when x < y -> T(insert(x, a), y, b)
| x, T(a, y, b) when y < x -> T(a, y, insert(x, b))
| _, s -> s
Here's what the tree looks like in use:
> let t = T(E, 1, E);;
val t : Tree
> t;;
val it : Tree = T (E,1,E)
> let t1 = insert(0, t);;
val t1 : Tree
> t1;;
val it : Tree = T (T (E,0,E),1,E)
> let t2 = insert(10, t1);;
val t2 : Tree
> t2;;
val it : Tree = T (T (E,0,E),1,T (E,10,E))
> let t3 = insert(5, t2);;
val t3 : Tree
> t3;;
val it : Tree = T (T (E,0,E),1,T (T (E,5,E),10,E))
> mem(10, t1);;
val it : bool = false
> mem(10, t2);;
val it : bool = true
2 comments:
Good for people to know.
Interesting.
I tried changing Elem from int to System.IComparable; that makes the code as generic as possible given this particular structure.
I wonder though, would this need to be memoized in order for the performance to be half-decent?
Post a Comment