3 (require "ch2_3_3_sets_as_trees.rkt")
6 (define (list->tree elements)
7 (car (partial-tree elements (length elements))))
9 (define (partial-tree elts n)
12 (let ((left-size (quotient (- n 1) 2)))
13 (let ((left-results (partial-tree elts left-size)))
14 (let ((left-tree (car left-results))
15 (non-left-elements (cdr left-results))
16 (right-size (- n (+ left-size 1))))
17 (let ((this (car non-left-elements))
18 (right-results (partial-tree (cdr non-left-elements) right-size)))
19 (let ((right-tree (car right-results))
20 (remaining-elts (cdr right-results)))
21 (cons (make-tree this left-tree right-tree)
22 remaining-elts))))))))
25 ;;(trace partial-tree)
31 Let us take an example:
33 (list->tree '(1 3 5 7 9 11))
36 (partial-tree '(1 3 5 7 9 11) 6)
37 => (partial-tree '(1 3 5 7 9 11) 2)
38 => (partial-tree '(1 3 5 7 9 11) 0)
40 At this point, we have found a leaf node. So, we push the null list,
41 take the first element on the list as the parent and look for the
42 right tree. The call returns to the previous call to partial-tree
43 (i.e. (partial-tree '(1 3 5 7 9 11) 2)) which means n is 2.
45 The right-size = (- n (+ left-size 1)) => (- 2 (+ 0 1)) => 1
46 So we invoke partial-tree for the right tree.
48 (partial-tree '(3 5 7 9 11) 1)
49 => (partial-tree '(3 5 7 9 11) 0)
51 This will push an empty list (as the left node) and look for right node.
52 (partial-tree '(5 7 9 11) 0)
54 this gives us the subtree (1 () (3 () ()))
56 At every stage of making a subtree, we cons it with the remaining elements.
57 The tree looks like this:
70 part b. For each node, we do a cons of the tree under the node with the remaining
71 elements. So the order of growth is O(n).