sicp-2.3.3
Posted on 2015-02-22 23:54:30 +0900 in SICP
2.59
(define (union-set set1 set2)
(cond ((null? set1) set2)
((element-of-set? (car set1) set2)
(union-set (cdr set1) set2))
(else
(cons (car set1)
(union-set (cdr set1)
set2)))))2.60
(define (adjoin-set x set)
(cons x set))
(define (union-set set1 set2)
(append set1 set2))adjoin-set goes from $O(n)$ to $O(1)$
union-set goes from $O(n^2)$ to $O(n)$
2.61
(define (adjoin-set x set)
(cond ((null? set) (list x))
((< x (car set)) (cons x set))
((= x (car set)) set)
((> x (car set)) (cons (car set)
(adjoin-set x (cdr set))))))2.62
(define (union-set set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
(else
(let* ([x1 (car set1)] [x2 (car set2)])
(cond ((< x1 x2)
(cons x1
(union-set (cdr set1) set2)))
((= x1 x2)
(cons x1
(union-set (cdr set1) (cdr set2))))
(else
(cons x2
(union-set set1 (cdr set2)))))))))2.63
It would make no difference on the final result, both of them are in order traverse. But there is something tricky on the time complexity1.
append is much more expensive than cons.
Let $T(n)$ be the time complexity for a balanced tree of $n$ nodes.
For tree->list-1:
For tree->list-2:
2.64
The analysis of time complexity is similar to the 2.63, which is $O(nlog n)$.
2.65
Use tree-list from 2.63 and list-tree to convert bidirectional.
(define (union-set tree1 tree2)
(list->tree (union-set-list (tree->list tree1)
(tree->list tree2))))
(define (intersection-set tree1 tree2)
(list->tree (intersection-set-list (tree->list tree1)
(tree->list tree2))))2.66
(define (lookup given-key set-of-records)
(if (null? set-of-records)
#f
(let ([record (entry set-of-records)])
(cond ((= given-key (key record)) record)
((< given-key (key record))
(lookup given-key
(left-branch set-of-records)))
((> given-key (key record))
(lookup given-key
(right-branch set-of-records)))))))Hide Comments
comments powered by Disqus