SICP Exercise 2.65: Unioning and Intersection Binary Search Trees

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.

Okay, so in exercise 2.63 we established that the procedure tree->list-2 is an Θ(n) procedure, and in exercise 2.64 we established that list->tree is also an Θ(n) procedure. This means that we can convert a balanced binary tree to a list and back again in Θ(n). Further to this, we can convert a balanced binary tree to a list, transform that list into another list, and then convert the resulting list to a balanced binary tree and, provided the transformation of the list is no worse than Θ(n), we can do all this in Θ(n).

If we assume that we're dealing with binary search trees, and not just binary trees, as the authors imply, then we know that tree->list-2 will produce an ordered list. We also know that, given an ordered list, list->tree will produce a balanced binary search tree. So one way of achieving our goal would be to take the balanced binary search trees to be unioned or intersected, convert them to ordered lists using tree->list-2, perform the union or intersection on the ordered lists, and then convert the resulting set back to a balanced binary search tree using list->tree.

If only we had some way of performing union-set and intersection-set on ordered list representations with Θ(n) growth. Oh look! We produced such a union-set in exercise 2.62, and the authors give us such an intersection-set in the "Sets as ordered lists" section. It's almost like that was planned...

Okay, so what we'll do is we'll convert these previously defined procedures to inner procedures in the corresponding union-set and intersection-set procedures for binary trees:

(define (union-set set1 set2)
  (define (union s1 s2)
    (cond ((null? s1) s2)
          ((null? s2) s1)
          (else (let ((x1 (car s1))
                      (x2 (car s2)))
                  (cond ((= x1 x2) (cons x1 (union (cdr s1) (cdr s2))))
                        ((< x1 x2) (cons x1 (union (cdr s1) s2)))
                        ((< x2 x1) (cons x2 (union s1 (cdr s2)))))))))
  (let ((list1 (tree->list-2 set1))
        (list2 (tree->list-2 set2)))
    (list->tree (union list1 list2))))

(define (intersection-set set1 set2)
  (define (intersect s1 s2)
    (if (or (null? s1) (null? s2))
        '()    
        (let ((x1 (car s1)) (x2 (car s2)))
          (cond ((= x1 x2) (cons x1 (intersect (cdr s1) (cdr s2))))
                ((< x1 x2) (intersect (cdr s1) s2))
                ((< x2 x1) (intersect s1 (cdr s2)))))))
  (let ((list1 (tree->list-2 set1))
        (list2 (tree->list-2 set2)))
    (list->tree (intersect list1 list2))))

Okay, so let's see these in action:

> (define odd-set (list->tree '(1 3 5)))
> (define even-set (list->tree '(2 4 6)))
> (define low-set (list->tree '(1 2 3 4)))
> (define high-set (list->tree '(3 4 5 6)))
> odd-set
'(3 (1 () ()) (5 () ()))
> even-set
'(4 (2 () ()) (6 () ()))
> low-set
'(2 (1 () ()) (3 () (4 () ())))
> high-set
'(4 (3 () ()) (5 () (6 () ())))
> (intersection-set odd-set odd-set)
'(3 (1 () ()) (5 () ()))
> (intersection-set odd-set even-set)
'()
> (intersection-set even-set odd-set)
'()
> (intersection-set low-set high-set)
'(3 () (4 () ()))
> (union-set odd-set odd-set)
'(3 (1 () ()) (5 () ()))
> (union-set odd-set even-set)
'(3 (1 () (2 () ())) (5 (4 () ()) (6 () ())))
> (union-set even-set odd-set)
'(3 (1 () (2 () ())) (5 (4 () ()) (6 () ())))
> (union-set low-set high-set)
'(3 (1 () (2 () ())) (5 (4 () ()) (6 () ())))