Homework 9b🔗

MUST BE DONE SOLO

Due Date Fri 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

; A [Comparison X] is a [X X -> Number]

; Interpretation: A Comparison function allows us to compare two inputs,

; with: a negative output indicating the first input is less than the second input,

;       a zero output     indicating the two inputs are equal,

;       a positive output indicating the first input is greater than the second input,

; according to some ordering.  The exact numerical values don't matter, but

; only whether they are negative, zero or positive.

(define-struct leaf [])

(define-struct node [key info smaller bigger])

; A [BST X Y] is one of

; - (make-leaf)

; - (make-node X Y [BST X Y] [BST X Y])

; and represents either an empty binary search tree or

; a node with key, info, and two subtrees with smaller/larger keys, respectively

(define-struct treemap [comp bst])

; An [ATreeMap X Y] is a (make-treemap [Comparison X] [BST X Y])

; The bst field is a binary search tree with values of type Y, whose keys are

; of type X and that are ordered according to the comparison function in the comp field.

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 new tree containing all the keys (and associated data) from the original tree that are at least lo and at most hi (as indicated by the comparison function).