Question:  In this assignment you are to implement and use a simple binary tree-map structure in Scheme. A binary tree map is a binary search tree where each node contains a key and a value. The key is used to maintain the order of the tree and value can be any value that you wish to associate with that key. In this exercise keys are numeric. As with all binary search trees all the keys in the left sub-tree of a node are less than the key of the node and all the keys in the right sub-tree of a node are greater than the key of the node. It is assumed that there are no duplicate keys in the the tree. The left and/or right subtrees may also be empty. Do the parts below in sequence.  Note, in all parts below you are encouraged to define helper procedures to help you complete each part. In some parts, helper methods will make the task much easier. Part 1- Constructor and Accessors Methods (30 marks) Start editing a file called tree-map.scm. In that file put the following code used to define and test for an empty tree:  ;;; an emtpy tree (define empty ())  ;;; and a test for an empty tree (define empty? null?)  Define the following constructor method:  (define (tree-node key value left right) ...)  and the following accessor methods:  (define (get-key tn) ...) (define (get-val tn) ...) (define (get-left tn) ...) (define (get-right tn) ...)  Where you have to define code in place of the ... symbols. You can choose any respresentation that you like for your tree nodes but the following code:  (define a (tree-node 5 50 empty empty)) (define b (tree-node 2 80 empty empty)) (define c (tree-node 3 10 b a))  (get-key (get-left c)) (get-val (get-right c)) (get-key c) (get-key a)   must return 2, 50, 3 and 5 respectively. These tests are not thorough. You must define your own tests for this part in your tests.scm file. Part 2 - Display Inorder (15 marks) Add a Scheme procedure of the form:  (define (display-inorder t) ...)  to your tree-map.scm file. display-inorder must display pairs of keys and values of the file as they appear in an in-order traversal, one line at a time. An in-order display of any tree will display the left sub-tree first and then display the current node and then display the right-hand sub-tree. As an example of how your display-inorder procedure must work the calls:  (display-inorder a) (display-inorder c)  will return, respectively:  5 50 ;Unspecified return value  and  2 80 3 10 5 50 ;Unspecified return value  where a and c were the trees defined in the previous part. Again, you must provide some more tests for this part in your tests.scm file. Part 3 - Tree Insertion (25 marks) Define a procedure of the form:  (define (insert t key val) ...)  that inserts a key key and a value val into the tree-map t returning a new tree with a node containing the key and the value in the appropriate location. Note, if the key already exists in the tree then insert should just return t. As an example of how insert should work the calls:  (define right (insert (insert empty 3 10) 5 20)) (define middle (insert (insert (insert empty 3 10) 5 20) 1 30)) (display-inorder right) (display-inorder middle)  will display:  3 10 5 20 ;Unspecified return value 1 30 3 10 5 20 ;Unspecified return value  Again, you must add tests for this part to the end of tests.scm Part 4 - Tree find (20 marks) Implement a Scheme procedure with the format:  (define (find t x) ...)  That finds the the value in t that corresponds to the key x. If the key x is not present then find must return #f. As an example of how find should work the code:  (find right 3) (find middle 5)  will return the values 10 and 20 respectively. Again, you must add more tests to your tests.scm file to test your find procedure. Part 5 - Enum Inorder (10 marks) Implement a Scheme procedure with the format:  (define (enum-inorder t) ...)  which traverses t in-order to produce a list of (key,value) pairs. So for example the call:  (enum-inorder middle)  will produce the result:  ((1 . 30) (3 . 10) (5 . 20))  Again, you must add more tests to your tests.scm file. Part 6 - Remove Duplicates (30 marks) In this part you are to implment a procedure that uses your tree map to help remove duplcates from a list of numbers. Your procedure must have the format:  (define (remove-duplicates xs) ...)  It must make use of a tree-map to record elements of xs that have been enocountered aready and to check to see if elements are duplicates. It is to return a copy of xs with duplicate elements filtered out.  Note that, for this exercise, it is sufficient to use just the keys in the tree map (the values can be ignored). As an example of how remove-duplicates must work. The call:  (remove-duplicates (list 1 2 3 4 1 3 2 5 5 8 1 7 3 2 1))  must return the list:  (1 2 3 4 5 8 7)  Again, you must place thorough tests for this part in your tests.scm file. Part 7 - Tree Sorting (15 marks) Define a Scheme procedure with the format:  (define (tree-sort xs) ...)  that takes a list of numbers xs and returns a sorted version of xs with any duplicates removed. Hint, to implement this procedure you may find it useful to build a helper procedure to insert all of the elements of xs into a tree and then use enum-inorder to enumerate the tree in sorted order.  Again make sure you add tests to tests.scm for this part.    Solution files included :   

1out.txt 1K

2out.txt 1K

3out.txt 1K

4out.txt 1K

5out.txt 1K

6out.txt 1K

7out.txt 1K

tree-map.scm 5K

http://ge.tt/1aLvkUX/v/0

tree-map. scm

;;

;; Part 1- Constructor and Accessors Methods

;;

(define (tree-node key value left right) (list key value left right))

(define (get-key tn) (if (empty? tn) empty (car tn)))

(define (get-val tn) (if (empty? tn) empty (cadr tn)))

(define (get-left tn) (if (empty? tn) empty (caddr tn)))

(define (get-right tn) (if (empty? tn) empty (cadddr tn)))

(define a (tree-node 5 50 empty empty))

(define b (tree-node 2 80 empty empty))

(define c (tree-node 3 10 b a))

; tests

(display “get-*: “)

(newline)

(get-key (get-left c))

(get-val (get-right c))

(get-key c)

(get-key a)

(get-right c)

(newline)

; additional tests

(define aa (tree-node 5 50 (tree-node 4 40 (tree-node 3 30 empty empty) empty) (tree-node 2 20 (tree-node 1 10 empty empty) empty)))

(get-key empty) ; -> empty

(get-val empty) ; -> empty

(get-left empty) ; -> empty

(get-right empty) ; ->empty

(get-key (get-right (get-left (get-left aa)))) ; -> empty

(get-key (get-left (get-left aa))) ; -> 3

(get-val (get-right aa)) ; -> 20

(newline)

;;

;; Part 2 – Display Inorder

;;

(define (display-inorder t)

(if (not (empty? t))

(begin

(display-inorder (get-left t))

(display (get-key t))

(display ” “)

(display (get-val t))

(newline)

(display-inorder (get-right t))

)

)

)

; tests

(display “display-inorder: “)

(newline)

(display-inorder a)

(display-inorder c)

(newline)

; additional tests

(define aa (tree-node 5 50 (tree-node 4 40 empty (tree-node 3 30 empty empty)) (tree-node 2 20 (tree-node 1 10 empty empty) empty)))

(display-inorder aa)

(newline)

;;

;; Part 3 – Tree Insertion

;;

(define (insert t key val)

(if (empty? t)

(tree-node key val empty empty)

(cond

((> key (get-key t)) (tree-node (get-key t) (get-val t) (get-left t) (insert (get-right t) key val)))

((< key (get-key t)) (tree-node (get-key t) (get-val t) (insert (get-left t) key val) (get-right t)))

(else (tree-node (get-key t) (get-val t) (get-left t) (get-right t)))

)

)

)

; tests

(display “insert: “)

(newline)

(define right (insert (insert empty 3 10) 5 20))

(define middle (insert (insert (insert empty 3 10) 5 20) 1 30))

(display-inorder right)

(display-inorder middle)

(newline)

; additional tests

(display-inorder (insert aa 6 60))

(newline)

;;

;; Part 4 – Tree find

;;

(define (find t x)

(if (empty? t)

#f

(cond

((< x (get-key t)) (find (get-left t) x))

((> x (get-key t)) (find (get-right t) x))

(else (get-val t))

)

)

)

; tests

(display “find: “)

(newline)

(find right 3)

(find middle 5)

(newline)

; additional tests

(find empty 1) ; -> #f

(find right 111) ; -> #f

(find aa 5) ; -> 50

(newline)

;;

;; Part 5 – Enum Inorder

;;

(define (enum-inorder t)

(define r ‘())

(define (enum-inorder-intern t collector)

(if (empty? t)

‘()

(begin

(enum-inorder-intern (get-left t) collector)

(collector (list `(,(get-key t) . ,(get-val t))))

(enum-inorder-intern (get-right t) collector)

)

)

)

(enum-inorder-intern t (lambda (v) (set! r (append r v))))

r

)

; tests

(display “enum-inorder: “)

(newline)

(enum-inorder middle)

(newline)

; additional tests

(enum-inorder empty) ; -> ()

(enum-inorder a) ; -> ((5 . 50))

(newline)

;;

;; Part 6 – Remove Duplicates

;;

(define (remove-duplicates xs)

(define (iter xs t)

(cond

((empty? xs) ‘())

((find t (car xs)) (iter (cdr xs) t))

(else

(cons (car xs) (iter (cdr xs) (insert t (car xs) 1)))

)

)

)

(iter xs empty)

)

; tests

(display “remove-duplicates: “)

(newline)

(remove-duplicates (list 1 2 3 4 1 3 2 5 5 8 1 7 3 2 1))

(newline)

; additional tests

(remove-duplicates ‘()) ; -> ()

(remove-duplicates (list 1 1 1)) ; -> (1)

(newline)

;;

;; Part 7 – Tree Sorting

;;

(define (tree-sort xs)

(define (tree-from-list xs t)

(cond

((empty? xs) t)

(else

(tree-from-list (cdr xs) (insert t (car xs) 1))

)

)

)

(map (lambda (e) (car e)) (enum-inorder (tree-from-list (remove-duplicates xs) empty)))

)

; tests

(display “tree-sort: “)

(newline)

(tree-sort (list 8 7 1 2 1 3 4 1 3 2 5 5 8 1 7 3 2 1))

(newline)

; additional tests

(tree-sort ‘()) ; -> ()

(tree-sort (list 1 1 1)) ; -> (1)

(tree-sort (list 2)) ; -> (2)