Homework 7b

MUST BE DONE SOLO

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

Purpose Practice with trees

Exercises

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.

Definition

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).