#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