Homework 7b

home work!

Programming Language #lang htdp/isl+


Due Date Thu at 9:00pm (Week 7)

Purpose Practice with trees


Tree Maps

NOTE: To test functions that return treemaps, you will have to extract the BST, since the comparison functions will not work inside check-expect.


Consider the following definition of a Tree Map

(define (Comparison X) (signature (X X -> Number)))
; with a negative output indicating the first parameter comes first,
;      a positive output indicating the first parameter comes second,
;      and 0 indicating they are equal
(define-struct leaf [])
(define-struct node [key info smaller bigger])
(define (BST X Y) (signature (mixed Leaf [NodeOf X Y [BST X Y] [BST X Y]])))
; and represents either an empty BST or
; a node with key, info, and two subtrees with smaller/larger keys, respectively
(define-struct treemap [comp bst])
(define (ATreemap X Y) (signature [TreemapOf [Comparison X] [BST X Y]]))
; and represents a treemap with a searchable bst with comp comparing over type x

Exercise 1 Design a function insert : X Y [ATreemap X Y] -> [ATreemap X Y], which given a key and an info (with types X and Y, respectively) inserts the pair into a treemap. If the key is already present, the old value should be overwritten. Be sure to uphold the invariants of a binary search tree.

Exercise 2 Design a function find : [ATreemap X Y] X -> Y, which given a key finds the associated info in the tree. Don’t search any more of the tree than necessary, and error if no such key is found.

Exercise 3 Design a function submap : [ATreemap X Y] X X -> [ATreemap X Y], which given two keys, lo and hi, and a treemap, outputs a treemap where the binary search tree is a subtree of the original, containing no keys lower than lo or higher than hi (as indicated by the comparison function).