2.65

练习 2.65 利用练习2.63和练习2.64的结果，给出对采用（平衡）二叉树方式实现的集合的union-set和intersection-set操作的$\Theta(n)$实现。

(define entry car)

(define (quotient n m)
(floor (/ n m))
)

(define (make-tree entry left right)
(list entry left right)
)

(define (list->tree elements)
(car
(partial-tree
elements
(length elements)
)
)
)

(define (partial-tree elts n)
(if (= n 0)
(cons '() elts)
(let
(
(left-size
(quotient (- n 1) 2)
)
)
(let ((left-result (partial-tree elts left-size)))
(let
(
(left-tree (car left-result))
(non-left-elts (cdr left-result))
(right-size (- n (+ left-size 1)))
)

(let
(
(this-entry (car non-left-elts))
(right-result
(partial-tree
(cdr non-left-elts)
right-size
)
)
)

(let
(
(right-tree (car right-result))
(remaining-elts
(cdr right-result)
)
)

(cons
(make-tree this-entry left-tree right-tree)
remaining-elts
)
)
)
)
)
)
)
)

(define (tree->list tree)
(if (null? tree)
'()
(append
(tree->list (left-branch tree))
(cons
(entry tree)
(tree->list (right-branch tree))
)
)
)
)


(define (union-set-sorted-list set1 set2)
(cond
((null? set1) set2)
((null? set2) set1)
(
(< (car set1) (car set2))
(cons
(car set1)
(union-set-sorted-list (cdr set1) set2)
)
)
(
(= (car set1) (car set2))
(union-set-sorted-list (cdr set1) set2)
)
(
else
(cons
(car set2)
(union-set-sorted-list set1 (cdr set2))
)
)
)
)

(union-set-sorted-list (list 1 2 3 4) (list 5 6 7 8))


union-set

(define (union-set tree1 tree2)
(list->tree
(union-set-sorted-list (tree->list tree1) (tree->list tree2))
)
)

(union-set
(list->tree (list 1 2 3 4))
(list->tree (list 5 6 7 8))
)


intersection-set

(define (intersection-set-sorted-list list1 list2)
(if (or (null? list1) (null? list2))
'()
(if (= (car list1) (car list2))
(cons
(car list1)
(intersection-set-sorted-list (cdr list1) (cdr list2))
)
(if (< (car list1) (car list2))
(intersection-set-sorted-list (cdr list1) list2)
(intersection-set-sorted-list list1 (cdr list2))
)
)
)
)

(intersection-set-sorted-list (list 1 2 3 4) (list 4 5 6 7))

(define (intersection-set tree1 tree2)
(list->tree
(intersection-set-sorted-list
(tree->list tree1)
(tree->list tree2)
)
)
)

(intersection-set (list->tree (list 1 2 3 4 5)) (list->tree (list 4 5 6 7 8)))