From SICP:
Exercise 2.65
Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.41
I wrote the following answer:
(define (union-set a b)
(define (rec set1 set2)
(cond ((null? set1) set2)
((null? set2) set1)
((= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2))))
((> (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2)))
(else (cons (car set2) (rec set1 (cdr set2))))))
(let ((ls-result (rec (tree->list a) (tree->list b))))
(partial-tree ls-result (length ls-result))))
(define (intersection-set a b)
(define (rec set1 set2)
(cond ((or (null? set1) (null? set2)) '())
((= (car set1) (car set2)) (cons (car set1) (rec (cdr set1) (cdr set2))))
((> (car set1) (car set2)) (rec set1 (cdr set2)))
((> (car set2) (car set1)) (rec (cdr set1) set2))))
(let ((ls-result (rec (tree->list a) (tree->list b))))
(partial-tree ls-result (length ls-result))))
Is this answer ok? Could it be better?
