Chapter 2, Building Abstractions with Data
Section - 2.3 Symbolic Data
Exercise 2.65
This can be done in following steps:
- Convert both trees of the sets using part(a) into ordered list.
- Use
union-set
andintersection-set
procedure of ordered list from previous section to get a set in oredered list representation. - Convert the ordered list into tree with part(b).
Clearly all of these parts are of $O(n)$ complexity. The overall complexity will be $O(n)$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
(define (union-set-tree tree1 tree2)
(list->tree (union-set
(tree->list tree1)
(tree->list tree2)
)
)
)
(define (intersection-set-tree tree1 tree2)
(list->tree (intersection-set
(tree->list tree1)
(tree->list tree2)
)
)
)