2.65

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

先复用一下前面的代码：

(define entry car)
(define left-branch cadr)
(define right-branch caddr)

(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))
            )
        )
    )
)

按照前面的做法，将一个表变成一棵二叉树，还要是平衡的，前提是这个表得有序。但是在有序表的前提下，其实不用二叉树也可以实现 $\Theta(n)$ 的union-set （练习2.62）。

(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))

所以很自然地想到，利用 2.62 的实现，将两棵平衡二叉树转换成两个有序的列表，在完成合并后，再转换回成树（由于结果表是有序的，转换回成树仍然是平衡二叉树）。

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)))