| 1234567891011121314151617181920212223242526272829303132333435363738 |
- 1.1 This simple program implements persistent functional binary search
- trees, so that if tree2-insert(x,tree1), then tree1 is till available
- for lookups even while tree2 can be used.
- type key = string
- datatype tree = LEAF | TREE of tree * key * tree
- val empty = LEAF
- fun insert (key, LEAF) = TREE(LEAF, key, LEAF)
- | insert (key, TREE(l,k,r)) =
- if key < k
- then TREE(insert(key,l),k,r)
- else if key > k
- then TREE(l,k,insert(key,r))
- else TREE(l,key,r)
- a. implement a `member` function that returns `true` if the item is
- found, else `false`
- b. Extend the program to include not just membership, but the mapping
- of keys to bindings:
- datatype 'a tree = ...
- insert: 'a tree * key * 'a -> 'a tree
- lookup: 'a tree * key -> 'a
- c. These trees are not balanced; demonstrate the behavior on the
- following two sequences of insertions:
- (a) t s p i p f b s t
- (b) a b c d e f g h i
- d*. Research balanced search trees in Sedgewick [1997] and recommend a
- balanced-tree data structure for functional symbol tables. Hint: To
- preserve a functional style, the algorithm should be one that
- rebalances on insertion but not on lookup, so a data structure such as
- splay trees is not appropriate.
|
