SICP 問題 2.65（二進木の和集合、積集合を求める手続を定義する）

問題

問題 2.63 と問題 2.64 の結果を使い、（釣り合った）二進木として実装されている集合の union-set と intersection-set を Θ(n) で実装せよ。

解答

２つの集合（二進木）を、一度順序付けられたリストに変換して、その状態で和集合あるいは積集合を求め、その結果を改めて二進木にすればいいんじゃね？
どのプロセスも Θ(n) のオーダーだし。

;和集合
(define (union-set tree1 tree2)
  ;順序付けられたリストの和集合を求める手続。（SICP 問題 2.62）
  (define (union-set-for-ordered-list set1 set2)
    (cond ((null? set1)
	   set2)
	  ((null? set2)
	   set1)
	  (else
	   (let ((x1 (car set1))
		 (x2 (car set2)))
	     (cond ((= x1 x2)
		    (cons x1 (union-set-for-ordered-list (cdr set1) (cdr set2))))
		   ((< x1 x2)
		    (cons x1 (union-set-for-ordered-list (cdr set1) set2)))
		   (else ;(< x2 x1)
		    (cons x2 (union-set-for-ordered-list set1 (cdr set2)))))))))
  ;メイン処理
  (let ((l1 (tree->list-2 tree1))
	(l2 (tree->list-2 tree2)))
    (list->tree (union-set-for-ordered-list l1 l2))))

;積集合
(define (intersection-set tree1 tree2)
  ;順序付けられたリストの積集合を求める手続。
  ;（SICP § 2.3.3 集合の表現　その２　[順序づけられたリストとしての集合]）
  (define (intersection-set-for-ordered-list set1 set2)
    (if (or (null? set1) (null? set2))
	'()
	(let ((x1 (car set1))
	      (x2 (car set2)))
	  (cond ((= x1 x2)
		 (cons x1 (intersection-set-for-ordered-list (cdr set1) (cdr set2))))
		((< x1 x2)
		 (intersection-set-for-ordered-list (cdr set1) set2))
		((< x2 x1)
		 (intersection-set-for-ordered-list set1 (cdr set2)))))))
  ;メイン処理
  (let ((l1 (tree->list-2 tree1))
	(l2 (tree->list-2 tree2)))
    (list->tree (intersection-set-for-ordered-list l1 l2))))

データ作るの大変だから実験しないけど・・・あってるよな？