1 #lang racket 2 3 (define (entry tree) (car tree)) 4 5 (define (left-branch tree) (cadr tree)) 6 7 (define (right-branch tree) (caddr tree)) 8 9 (define (make-tree entry left right) 10 (list entry left right)) 11 12 (define (tree->list-1 tree) 13 (if (null? tree) 14 '() 15 (append (tree->list-1 (left-branch tree)) 16 (cons (entry tree) 17 (tree->list-1 (right-branch tree)))))) 18 19 (define (tree->list-2 tree) 20 (define (copy-to-list tree result-list) 21 (if (null? tree) 22 result-list 23 (copy-to-list (left-branch tree) 24 (cons (entry tree) 25 (copy-to-list (right-branch tree) 26 result-list))))) 27 (copy-to-list tree '())) 28 29 (define tree1 30 (make-tree 7 31 (make-tree 3 '(1 () ()) '(5 () ())) 32 (make-tree 9 '() '(11 () ())))) 33 34 (define tree2 35 (make-tree 3 36 '(1 () ()) 37 (make-tree 7 38 '(5 () ()) 39 (make-tree 9 '() '(11 () ()))))) 40 41 42 43 ;;;;;;;;;;;;;;;;test 44 ;;;;;;;;;;;;;;产生相同的结果 45 ;;;;;;;;;;;;;; 46 (tree->list-1 tree1) 47 (tree->list-2 tree1) 48 (tree->list-1 tree2) 49 (tree->list-2 tree2) 50 51 ;;;;;;;;;;;;;;;2.64 52 (define (list-tree elements) 53 (car (partial-tree elements (length elements)))) 54 55 (define (partial-tree elts n) 56 (if (= n 0) 57 (cons '() elts) 58 (let ((left-size (quotient (- n 1) 2))) 59 (let ((left-result (partial-tree elts left-size))) 60 (let ((left-tree (car left-result)) 61 (non-left-elts (cdr left-result)) 62 (right-size (- n (+ left-size 1)))) 63 (let ((this-entry (car non-left-elts)) 64 (right-result (partial-tree (cdr non-left-elts) 65 right-size))) 66 (let ((right-tree (car right-result)) 67 (remaining-elts (cdr right-result))) 68 (cons (make-tree this-entry left-tree right-tree) 69 remaining-elts)))))))) 70 71 ;;;;;;;;;;;;test(a) 72 ;;;;;;;;;;;;先算出左子树的size再构造左子树，以及剩下的非左子树 73 ;;;;;;;;;;;;的序列，以及右子树的size再根据这些构造完整的树 74 ;;;;;;;;;;;;实际上就是中序构造一颗平衡树 75 (list-tree '(1 3 5 7 9)) 76 77 ;;;;;;;;;;;;(b) 78 ;;;;;;;;;;;;O(log(n)) 79 80 ;;;;;;;;;;;;;2.65 81 (define (new-union-set set1 set2) 82 (list-tree (union-set (tree->list-2 set1) (tree->list-2 set2)))) 83 84 (define (union-set set1 set2) 85 (cond ((null? set1) set2) 86 ((null? set2) set1) 87 ((< (car set1) (car set2)) 88 (cons (car set1) (union-set (cdr set1) set2))) 89 ((< (car set2) (car set1)) 90 (cons (car set2) (union-set set1 (cdr set2)))) 91 ((= (car set1) (car set2)) 92 (cons (car set1) (union-set (cdr set1) (cdr set2)))))) 93 94 (define (new-intersection-set set1 set2) 95 (list-tree (intersection-set (tree->list-2 set1) 96 (tree->list-2 set2)))) 97 98 (define (intersection-set set1 set2) 99 (if (or (null? set1) (null? set2)) 100 '() 101 (let ((x1 (car set1)) (x2 (car set2))) 102 (cond ((= x1 x2) 103 (cons x1 104 (intersection-set (cdr set1) 105 (cdr set2)))) 106 ((< x1 x2) 107 (intersection-set (cdr set1) set2)) 108 ((< x2 x1) 109 (intersection-set set1 (cdr set2))))))) 110 111 ;;;;;;;;;;;;;;;;test 112 ;;;;;;;;;;;;;;;;因为union-set和intersection-set 113 ;;;;;;;;;;;;;;;;都是O(n)而list-tree 和 tree->list-2 114 ;;;;;;;;;;;;;;;;都是O(log(n))所以总的步数为O(n) 115 (new-intersection-set (list-tree '(1 2 3 4 5)) 116 (list-tree '(3 4 5 6 7))) 117 118 (new-union-set (list-tree '(1 2 3 4 5)) 119 (list-tree '(3 4 5 6 7)))
对于2.63 对步数还是没有好的理解
从参考一中可以看出tree->list-1 append数是正比于n的，但是步数应该为O（n*log（n））
因为append并不是每次都会append 个数为n的list
tree->list-2 只有cons操作，步数正比于n，O（n）
参考二中有一句话：
We can see from the results above and from inspecting the two procedures that each node of the tree is visited one time by each algorithm. What happens at each of those n steps is subtly different though. The second procedure simply calls cons at each step, which we'll assume is a constant-time operation
可以仔细想一下