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))
  )
​x
 
#<undef>

 
(define (make-tree entry left right)
  (list entry left right)
  )
 
#<undef>

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

按照前面的做法，将一个表变成一棵二叉树，还要是平衡的，前提是这个表得有序。但是在有序表的前提下，其实不用二叉树也可以实现 $\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))
 
(1 2 3 4 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))
 )
 
(4 (2 (1 nil nil) (3 nil nil)) (6 (5 nil nil) (7 nil (8 nil nil))))

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

 
(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)))
 
(4 nil (5 nil nil))