| 12345678910111213141516171819202122232425 |
- type key = string
- datatype 'a tree = LEAF | TREE of 'a tree * (key * 'a) * 'a tree
- val empty = LEAF
- fun insert (LEAF, key, newval) = TREE(LEAF, (key, newval), LEAF)
- | insert (TREE(l,(k,v),r), key, newval) =
- if key < k
- then TREE(insert(l,key,newval),(k,v),r)
- else if key > k
- then TREE(l,(k,v),insert(r,key,newval))
- else TREE(l,(key,newval),r)
- (* This is not exhaustive, and will fail if the tree
- was not created using `insert` *)
- fun lookup (TREE(l,(k,v),r), key) =
- if key = k
- then v
- else if key < k
- then lookup (l, key)
- else lookup (r, key)
- | lookup (LEAF, key) = raise Subscript
|
