Suppose, however, that x1 is less than x2 . Hence, the intersection is equal to the intersection of set2 with the cdr of set1 . Give an implementation of adjoin-set using the ordered representation. Give a implementation of union-set for sets represented as ordered lists. Sets as binary trees We can do better than the ordered-list representation by arranging the set elements in the form of a tree.
Figure shows some trees that represent the set .
The same set may be represented by a tree in a number of different ways. We begin by comparing x with the entry in the top node. Since the size of the tree is halved at each step, we should expect that the number of steps needed to search a tree of size n grows as . For large sets, this will be a significant speedup over the previous representations. We can represent trees by using lists.