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