SICP問題2.65

問題2.63, 2.64 の結果を使い、釣り合った二進木として実装されている集合の union-set と intersection-set を Θ(n) で実装せよという問題。
2.63 の tree->list-2 と 2.62 の union-set とテキスト中に出てきた intersection-set を使用すれば OK なはず。
というこで実装
まずはunion-set

; 元の union-set を変更
(define (union-list set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else
         (let ((x1 (car set1))
               (x2 (car set2)))
           (cond ((= x1 x2)
                  (cons x1
                        (union-list (cdr set1) (cdr set2))))
                 ((< x1 x2)
                  (cons x1
                        (union-list (cdr set1) set2)))
                 ((< x2 x1)
                  (cons x2
                        (union-list set1 (cdr set2)))))))))
; 新しい union-set
(define (union-set set1 set2)
  (list->tree 
   (union-list (tree->list-2 set1) (tree->list-2 set2))))

次にintersection-set

; 元の intersection-set を変更
(define (intersection-list set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1))
            (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-list (cdr set1) (cdr set2))))
              ((< x1 x2)
               (intersection-list (cdr set1) set2))
              ((< x2 x1)
               (intersection-list set1 (cdr set2)))))))
; 新しい intersection-set
(define (intersection-set set1 set2)
  (list->tree (intersection-list (tree->list-2 set1) (tree->list-2 set2))))

テスト

(define t1 (list->tree (list 1 2 3 6 8 9 10 11)))
; t1
t1
; (6 (2 (1 () ()) (3 () ())) (9 (8 () ()) (10 () (11 () ()))))
(define t2 (list->tree (list 2 5 7 8 10 11 12 13)))
; t2
t2
; (8 (5 (2 () ()) (7 () ())) (11 (10 () ()) (12 () (13 () ()))))
(union-set t1 t2)
; (7 (3 (1 () (2 () ())) (5 () (6 () ()))) (10 (8 () (9 () ())) (12 (11 () ()) (13 () ()))))
(intersection-set t1 t2)
; (8 (2 () ()) (10 () (11 () ())))

OK