1 665c255d 2023-08-04 jrmu (define (entry tree) (car tree))
2 665c255d 2023-08-04 jrmu (define (left-branch tree) (cadr tree))
3 665c255d 2023-08-04 jrmu (define (right-branch tree) (caddr tree))
4 665c255d 2023-08-04 jrmu (define (make-tree entry left right)
5 665c255d 2023-08-04 jrmu (list entry left right))
7 665c255d 2023-08-04 jrmu (define (element-of-set? x set)
8 665c255d 2023-08-04 jrmu (cond ((null? set) #f)
9 665c255d 2023-08-04 jrmu ((= x (entry set)) #t)
10 665c255d 2023-08-04 jrmu ((< x (entry set))
11 665c255d 2023-08-04 jrmu (element-of-set? x (left-branch set)))
12 665c255d 2023-08-04 jrmu ((> x (entry set))
13 665c255d 2023-08-04 jrmu (element-of-set? x (right-branch set)))))
15 665c255d 2023-08-04 jrmu (define (adjoin-set x set)
16 665c255d 2023-08-04 jrmu (cond ((null? set) (make-tree x '() '()))
17 665c255d 2023-08-04 jrmu ((= x (entry set)) set)
18 665c255d 2023-08-04 jrmu ((< x (entry set))
19 665c255d 2023-08-04 jrmu (make-tree (entry set)
20 665c255d 2023-08-04 jrmu (adjoin-set x (left-branch set))
21 665c255d 2023-08-04 jrmu (right-branch set)))
22 665c255d 2023-08-04 jrmu ((> x (entry set))
23 665c255d 2023-08-04 jrmu (make-tree (entry set)
24 665c255d 2023-08-04 jrmu (left-branch set)
25 665c255d 2023-08-04 jrmu (adjoin-set x (right-branch set))))))
26 665c255d 2023-08-04 jrmu (define (tree->list-1 tree)
27 665c255d 2023-08-04 jrmu (if (null? tree)
29 665c255d 2023-08-04 jrmu (append (tree->list-1 (left-branch tree))
30 665c255d 2023-08-04 jrmu (cons (entry tree)
31 665c255d 2023-08-04 jrmu (tree->list-1 (right-branch tree))))))
32 665c255d 2023-08-04 jrmu (define (tree->list-2 tree)
33 665c255d 2023-08-04 jrmu (define (copy-to-list tree result-list)
34 665c255d 2023-08-04 jrmu (if (null? tree)
36 665c255d 2023-08-04 jrmu (copy-to-list (left-branch tree)
37 665c255d 2023-08-04 jrmu (cons (entry tree)
38 665c255d 2023-08-04 jrmu (copy-to-list (right-branch tree)
39 665c255d 2023-08-04 jrmu result-list)))))
40 665c255d 2023-08-04 jrmu (copy-to-list tree '()))
42 665c255d 2023-08-04 jrmu (define (list->tree elements)
43 665c255d 2023-08-04 jrmu (car (partial-tree elements (length elements))))
45 665c255d 2023-08-04 jrmu (define (partial-tree elts n)
47 665c255d 2023-08-04 jrmu (cons '() elts)
48 665c255d 2023-08-04 jrmu (let ((left-size (quotient (- n 1) 2)))
49 665c255d 2023-08-04 jrmu (let ((left-result (partial-tree elts left-size)))
50 665c255d 2023-08-04 jrmu (let ((left-tree (car left-result))
51 665c255d 2023-08-04 jrmu (non-left-elts (cdr left-result))
52 665c255d 2023-08-04 jrmu (right-size (- n (+ left-size 1))))
53 665c255d 2023-08-04 jrmu (let ((this-entry (car non-left-elts))
54 665c255d 2023-08-04 jrmu (right-result (partial-tree (cdr non-left-elts)
55 665c255d 2023-08-04 jrmu right-size)))
56 665c255d 2023-08-04 jrmu (let ((right-tree (car right-result))
57 665c255d 2023-08-04 jrmu (remaining-elts (cdr right-result)))
58 665c255d 2023-08-04 jrmu (cons (make-tree this-entry left-tree right-tree)
59 665c255d 2023-08-04 jrmu remaining-elts))))))))
61 665c255d 2023-08-04 jrmu ;; a. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).
63 665c255d 2023-08-04 jrmu ;; If we want a tree with 0 elements in it, we just return an empty tree (nil). Otherwise, we're going to build a tree by finding the middle element of a list rounded down (so if we had 6 elements, the middle element will be 3. If we have 7 elements, it will be 4). We then create a tree with the middle element as the entry of the tree and then call ourselves recursively to build the left-branch of the tree and the right-branch of the tree. We then return this tree along with any elements that have not been put into the tree. The reason we need the remaining elements is because it helps us quickly pass along all the elements of the list that go into the entry and right branch of the tree.
65 665c255d 2023-08-04 jrmu ;; b. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?
67 665c255d 2023-08-04 jrmu ;; We call partial-tree O(n) times for a list of n elements (a bit more again because we also call it when n = 0). It looks like the order of growth is roughly O(n).
69 665c255d 2023-08-04 jrmu (define (tree->list-1 tree)
70 665c255d 2023-08-04 jrmu (if (null? tree)
72 665c255d 2023-08-04 jrmu (append (tree->list-1 (left-branch tree))
73 665c255d 2023-08-04 jrmu (cons (entry tree)
74 665c255d 2023-08-04 jrmu (tree->list-1 (right-branch tree))))))
75 665c255d 2023-08-04 jrmu (define (tree->list-2 tree)
76 665c255d 2023-08-04 jrmu (define (cons-tree->list tree larger-items)
77 665c255d 2023-08-04 jrmu (if (null? tree)
78 665c255d 2023-08-04 jrmu larger-items
79 665c255d 2023-08-04 jrmu (cons-tree->list (left-branch tree)
80 665c255d 2023-08-04 jrmu (cons (entry tree)
81 665c255d 2023-08-04 jrmu (cons-tree->list (right-branch tree)
82 665c255d 2023-08-04 jrmu larger-items)))))
83 665c255d 2023-08-04 jrmu (cons-tree->list tree '()))
