2.3.3实例：集合表示

集合支持一系列的操作，同时也就可以把集合定义为一组可以作用于集合的操作。分别是判断元素是否存在于集合里的方法，插入，求交，求并

方法一：把集合表示成未排序的表。这种方法时间复杂度较高，基础操作element-of-set? 增长阶是线性的。

#lang sicp
(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set) ) true)
        (else (element-of-set? x (cdr set)))))
(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))
      
      
;;递归。如果已经得到了部分的交集，只需要确定当前元素是否应该在交集里即可
(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2) ) '())
        ((element-of-set? (car set1) set2)
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2)))) 

方法二：把集合表述为排好序的表。这种方法比上一种有一定的优势，在此不再提供代码。

方法三：把集合表述为一个二叉树。时间复杂度是对数阶的（这个结论假设二叉树是平衡的）

(define (entry tree)
  (car tree)
  )
(define (left-branch tree)
  (cadr tree))
(define (right-branch tree)
  (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

(define (element-of-set x set)
  (cond ((null? set) false)
        ((= x (entry set) ) true)
        ((< x (entry set))
         (element-of-set x (left-branch set)))
        ((> x (entry set))
         (element-of-set x (right-branch)))))

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
            (make-tree
             (entry set)
             (adjoin-set x (left-branch set))
             (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    adjoin-set x (right-branch set)))))