Revision of 2.3.3 Example: Representing Sets from 18 July 2009 - 10:47pm

The revisions let you track differences between multiple versions of a post.

Printer-friendly versionPrinter-friendly version

In the previous examples we built representations for two kinds of compound data objects: rational numbers and algebraic expressions. In one of these examples we had the choice of simplifying (reducing) the expressions at either construction time or selection time, but other than that the choice of a representation for these structures in terms of lists was straightforward. When we turn to the representation of sets, the choice of a representation is not so obvious. Indeed, there are a number of possible representations, and they differ significantly from one another in several ways.

Informally, a set is simply a collection of distinct objects. To give a more precise definition we can employ the method of data abstraction. That is, we define “set” by specifying the operations that are to be used on sets. These are union-set, intersection-set, element-of-set?, and adjoin-set. Element-of-set? is a predicate that determines whether a given element is a member of a set. Adjoin-set takes an object and a set as arguments and returns a set that contains the elements of the original set and also the adjoined element. Union-set computes the union of two sets, which is the set containing each element that appears in either argument. Intersection-set computes the intersection of two sets, which is the set containing only elements that appear in both arguments. From the viewpoint of data abstraction, we are free to design any representation that implements these operations in a way consistent with the interpretations given above.[37]

Sets as unordered lists

One way to represent a set is as a list of its elements in which no element appears more than once. The empty set is represented by the empty list. In this representation, element-of-set? is similar to the procedure memq of section 2.3.1. It uses equal? instead of eq? so that the set elements need not be symbols:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((equal? x (car set)) true)
        (else (element-of-set? x (cdr set)))))

Using this, we can write adjoin-set. If the object to be adjoined is already in the set, we just return the set. Otherwise, we use cons to add the object to the list that represents the set:

(define (adjoin-set x set)
  (if (element-of-set? x set)
      set
      (cons x set)))

For intersection-set we can use a recursive strategy. If we know how to form the intersection of set2 and the cdr of set1, we only need to decide whether to include the car of set1 in this. But this depends on whether (car set1) is also in set2. Here is the resulting procedure:

(define (intersection-set set1 set2)
  (cond ((or (null? set1) (null? set2)) '())
        ((element-of-set? (car set1) set2)        
         (cons (car set1)
               (intersection-set (cdr set1) set2)))
        (else (intersection-set (cdr set1) set2))))

In designing a representation, one of the issues we should be concerned with is efficiency. Consider the number of steps required by our set operations. Since they all use element-of-set?, the speed of this operation has a major impact on the efficiency of the set implementation as a whole. Now, in order to check whether an object is a member of a set, element-of-set? may have to scan the entire set. (In the worst case, the object turns out not to be in the set.) Hence, if the set has n elements, element-of-set? might take up to n steps. Thus, the number of steps required grows as Θ(n). The number of steps required by adjoin-set, which uses this operation, also grows as Θ(n). For intersection-set, which does an element-of-set? check for each element of set1, the number of steps required grows as the product of the sizes of the sets involved, or Θ(n2) for two sets of size n. The same will be true of union-set.

[37]

If we want to be more formal, we can specify “consistent with the interpretations given above” to mean that the operations satisfy a collection of rules such as these:

  • For any set S and any object x, (element-of-set? x (adjoin-set x S)) is true (informally: “Adjoining an object to a set produces a set that contains the object”).

  • For any sets S and T and any object x, (element-of-set? x (union-set S T)) is equal to (or (element-of-set? x S) (element-of-set? x T)) (informally: “The elements of (union S T) are the elements that are in S or in T”).

  • For any object x, (element-of-set? x '()) is false (informally: “No object is an element of the empty set”).

[back]

Exercises

Exercise 2.61

in

Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

Exercise 2.62

in

Give a Θ(n) 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. Each node of the tree holds one element of the set, called the “entry” at that node, and a link to each of two other (possibly empty) nodes. The “left” link points to elements smaller than the one at the node, and the “right” link to elements greater than the one at the node. Figure 2.16 shows some trees that represent the set {1,3,5,7,9,11}. The same set may be represented by a tree in a number of different ways. The only thing we require for a valid representation is that all elements in the left subtree be smaller than the node entry and that all elements in the right subtree be larger.

The advantage of the tree representation is this: Suppose we want to check whether a number x is contained in a set. We begin by comparing x with the entry in the top node. If x is less than this, we know that we need only search the left subtree; if x is greater, we need only search the right subtree. Now, if the tree is “balanced,” each of these subtrees will be about half the size of the original. Thus, in one step we have reduced the problem of searching a tree of size n to searching a tree of size n/2. 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 Θ(log n).[38] For large sets, this will be a significant speedup over the previous representations.

We can represent trees by using lists. Each node will be a list of three items: the entry at the node, the left subtree, and the right subtree. A left or a right subtree of the empty list will indicate that there is no subtree connected there. We can describe this representation by the following procedures:[39]

(define (entry tree) (car tree))
(define (left-branch tree) (cadr tree))
(define (right-branch tree) (caddr tree))
(define (make-tree entry left right)
  (list entry left right))

Now we can write the element-of-set? procedure using the strategy described above:

(define (element-of-set? x set)
  (cond ((null? set) false)
        ((= x (entry set)) true)
        ((< x (entry set))
         (element-of-set? x (left-branch set)))
        ((> x (entry set))
         (element-of-set? x (right-branch set)))))

Adjoining an item to a set is implemented similarly and also requires Θ(log n) steps. To adjoin an item x, we compare x with the node entry to determine whether x should be added to the right or to the left branch, and having adjoined x to the appropriate branch we piece this newly constructed branch together with the original entry and the other branch. If x is equal to the entry, we just return the node. If we are asked to adjoin x to an empty tree, we generate a tree that has x as the entry and empty right and left branches. Here is the procedure:

(define (adjoin-set x set)
  (cond ((null? set) (make-tree x '() '()))
        ((= x (entry set)) set)
        ((< x (entry set))
         (make-tree (entry set) 
                    (adjoin-set x (left-branch set))
                    (right-branch set)))
        ((> x (entry set))
         (make-tree (entry set)
                    (left-branch set)
                    (adjoin-set x (right-branch set))))))

The above claim that searching the tree can be performed in a logarithmic number of steps rests on the assumption that the tree is “balanced,” i.e., that the left and the right subtree of every tree have approximately the same number of elements, so that each subtree contains about half the elements of its parent. But how can we be certain that the trees we construct will be balanced? Even if we start with a balanced tree, adding elements with adjoin-set may produce an unbalanced result. Since the position of a newly adjoined element depends on how the element compares with the items already in the set, we can expect that if we add elements “randomly” the tree will tend to be balanced on the average. But this is not a guarantee. For example, if we start with an empty set and adjoin the numbers 1 through 7 in sequence we end up with the highly unbalanced tree shown in figure 2.17. In this tree all the left subtrees are empty, so it has no advantage over a simple ordered list. One way to solve this problem is to define an operation that transforms an arbitrary tree into a balanced tree with the same elements. Then we can perform this transformation after every few adjoin-set operations to keep our set in balance. There are also other ways to solve this problem, most of which involve designing new data structures for which searching and insertion both can be done in Θ(log n) steps.[40]

[38] Halving the size of the problem at each step is the distinguishing characteristic of logarithmic growth, as we saw with the fast-exponentiation algorithm of section 1.2.4 and the half-interval search method of section 1.3.3. [back]
[39] We are representing sets in terms of trees, and trees in terms of lists — in effect, a data abstraction built upon a data abstraction. We can regard the procedures entry, left-branch, right-branch, and make-tree as a way of isolating the abstraction of a “binary tree” from the particular way we might wish to represent such a tree in terms of list structure. [back]
[40] Examples of such structures include B-trees and red-black trees. There is a large literature on data structures devoted to this problem. See Cormen, Leiserson, and Rivest 1990. [back]

Exercises

Exercise 2.63

in

Each of the following two procedures converts a binary tree to a list.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))
  1. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

  2. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

Exercise 2.64

in

The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree.

define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))
  1. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).

  2. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?

Exercise 2.65

in

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]

[41] Exercises 2.63-2.65 are due to Paul Hilfinger. [back]

Exercises

Exercise 2.61

in

Give an implementation of adjoin-set using the ordered representation. By analogy with element-of-set? show how to take advantage of the ordering to produce a procedure that requires on the average about half as many steps as with the unordered representation.

Exercise 2.62

in

Give a Θ(n) implementation of union-set for sets represented as ordered lists.

Exercise 2.63

in

Each of the following two procedures converts a binary tree to a list.

(define (tree->list-1 tree)
  (if (null? tree)
      '()
      (append (tree->list-1 (left-branch tree))
              (cons (entry tree)
                    (tree->list-1 (right-branch tree))))))
(define (tree->list-2 tree)
  (define (copy-to-list tree result-list)
    (if (null? tree)
        result-list
        (copy-to-list (left-branch tree)
                      (cons (entry tree)
                            (copy-to-list (right-branch tree)
                                          result-list)))))
  (copy-to-list tree '()))
  1. Do the two procedures produce the same result for every tree? If not, how do the results differ? What lists do the two procedures produce for the trees in figure 2.16?

  2. Do the two procedures have the same order of growth in the number of steps required to convert a balanced tree with n elements to a list? If not, which one grows more slowly?

Exercise 2.64

in

The following procedure list->tree converts an ordered list to a balanced binary tree. The helper procedure partial-tree takes as arguments an integer n and list of at least n elements and constructs a balanced tree containing the first n elements of the list. The result returned by partial-tree is a pair (formed with cons) whose car is the constructed tree and whose cdr is the list of elements not included in the tree.

define (list->tree elements)
  (car (partial-tree elements (length elements))))

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))
  1. Write a short paragraph explaining as clearly as you can how partial-tree works. Draw the tree produced by list->tree for the list (1 3 5 7 9 11).

  2. What is the order of growth in the number of steps required by list->tree to convert a list of n elements?

Exercise 2.65

in

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]

[41] Exercises 2.63-2.65 are due to Paul Hilfinger. [back]

Exercise 2.66

in

Implement the lookup procedure for the case where the set of records is structured as a binary tree, ordered by the numerical values of the keys.

Comments

car and cdr

While the clojure interpreter will parse car and cdr, would it be more idiomatic to use first and rest?

On an unrelated note, the text in the editor is very small in Chrome v5 OS X (having to squint).

GDIhKoRHJj

Excellent goods from you, man. [sweet]c3a9c281c2a0c3a4c2bcc28138Fc3a3c281c2aec3a9c2a6c2acc3a5c28fc2afc3a6c2b3c2a2c3a7c2bee280a6c3a9e280a6e28099c3a5c2bbc5a0 |c3a4c2b8e280b9c3a5c28dcb86c3a8c592c2b6 c3a2e284a2c2a5 | c3a8e280bae280b9c3a5c2a0c2a1c3a3c281c2aepeace c3a2cb9cc2ae & love c3a2e284a2c2a5 I’ve understand your stuff prievous to and you are just extremely great. I really like what you’ve acquired here, really like what you are stating and the way in which you say it. You make it enjoyable and you still care for to keep it wise. I cant wait to read much more from you. This is actually a tremendous [sweet]c3a9c281c2a0c3a4c2bcc28138Fc3a3c281c2aec3a9c2a6c2acc3a5c28fc2afc3a6c2b3c2a2c3a7c2bee280a6c3a9e280a6e28099c3a5c2bbc5a0 |c3a4c2b8e280b9c3a5c28dcb86c3a8c592c2b6 c3a2e284a2c2a5 | c3a8e280bae280b9c3a5c2a0c2a1c3a3c281c2aepeace c3a2cb9cc2ae & love c3a2e284a2c2a5 informations.

beats by dre clearance

cheap monster beats Before I tell you about my experience, cheap monster beats let me tell you a bit more about these headphones. beats by dre solo According to the information I’ve read, Dr. beats by dre solo Dre worked with Monster Cable and Robert Brunner, dre beats an industrial designer, dre beats for more than two years to perfect these headphones. beats by dre clearance In Dr. Dre’s words,People aren’t hearing all the music beats by dre clearance.

http://www.rateamateapp.com

http://bimeido.lolipop.jp/luntan/forum.php?mod=viewthread&tid=637186 http://demo.bee.com.my/discuzx/forum.php?mod=viewthread&tid=706059 http://www.shumat.net/bbs/forum.php?mod=viewthread&tid=256971 http://www.rad3d.ca/plastic/index.php?title=User:L8ynelsn#http:.2F.2Fwww… http://ianylang.xoom.it/forum.php?mod=viewthread&tid=2197456 http://pftbgs.com/thread-697689-1-1.html http://sanfuyuqi.com/bbs/forum.php?mod=viewthread&tid=727868&fromuid=54592 http://www.mexiaoyuan.me/sc/forum.php?mod=viewthread&tid=7257536 http://cluo.cn/forum.php?mod=forumdisplay&fid=41&filter=typeid&typeid=26 http://dz30.4ucn.com/forum.php?mod=viewthread&tid=450988&fromuid=43947 http://www.hpv99.net/bbs/thread-1556106-1-1.html http://hldyizhi.com/Review.asp?NewsID=1327 http://dalanzhu.com/bbs/forum.php?mod=viewthread&tid=941672 http://vvi.cn/bbs/forum.php?mod=viewthread&tid=651148 http://shufazj.com/forum.php?mod=viewthread&tid=118067&fromuid=18273 http://www.chaobairen.com/forum.php?mod=viewthread&tid=605561&fromuid=49218 http://kangfuc.com/forum.php?mod=viewthread&tid=5654479 http://www.ooxxxxoo.com/forum.php?mod=viewthread&tid=2812409 http://isamrt.com/forum.php?mod=viewthread&tid=1476068&fromuid=87479 http://www.gzchlz.com/bbs/forum.php?mod=viewthread&tid=386098 http://www.as1000.net/bbs/forum.php?mod=viewthread&tid=830111 http://www.yqqqx.com/forum.php?mod=viewthread&tid=533641&fromuid=62078 http://jingliansi.w204.mc-test.com/thread-155408-1-1.html http://www.cslife.org/forum.php?mod=viewthread&tid=353412 http://www.smmin.com/forum.php?mod=viewthread&tid=603548 http://www.ggfabu.com/thread-9973280-1-1.html http://sj.sekwan.cn/forum.php?mod=viewthread&tid=3217234&fromuid=414115 http://konica.fuyinji.com/forum.php?mod=viewthread&tid=313349&fromuid=81774 http://www.brisk-e.com/forum.php?mod=viewthread&tid=820353&fromuid=71642 http://fllxxc.com/forum.php?mod=viewthread&tid=87512 http://www.51liuxue.ca/forum.php?mod=viewthread&tid=368276 http://www.98party.com/thread-315458-1-1.html http://www.gzhcws.com/bbs/forum.php?mod=viewthread&tid=4223958 http://bbs.jkym.cn/forum.php?mod=viewthread&tid=875317&fromuid=78690 http://www.hldyizhi.com/Review.asp?NewsID=1315 http://www.hldyizhi.com/Review.asp?NewsID=1312 http://www.ptuquan.com/space.php?uid=219888&do=blog&id=394327 http://www.wenwanjia.com/forum.php?mod=forumdisplay&fid=45&filter=typeid… http://bb.16feel.com/forum.php?mod=viewthread&tid=219460&fromuid=17656 http://xydcx.com.id39636.aliasl3.doctoryun.net/bbs/forum.php?mod=viewthr… http://www.mtbyw.com/forum.php?mod=viewthread&tid=100977&fromuid=3839 http://www.fftchina.org/bbs/forum.php?mod=viewthread&tid=376143&fromuid=… http://www.7dian.net.cn/bbs/showtopic-1397104.aspx http://www.mcgoa.com/forum.php?mod=viewthread&tid=130304&fromuid=4122 http://www.mcctv.com.cn/bbs/showtopic-220683.aspx http://www.fuyangbaijiale.com/forum.php?mod=viewthread&tid=542738&fromui… http://sszbb.cn/bbs/showtopic-471.aspx http://www.1886ckj.com/forum.php?mod=viewthread&tid=100337 http://xurui.net/forum.php?mod=viewthread&tid=222596&fromuid=201573 http://www.vku998.com/forum.php?mod=viewthread&tid=37046&fromuid=11482 http://www.projectshyb.com/forum.php?mod=viewthread&tid=118805 http://puss1982.7991.ftpdo.com/Review.asp?NewsID=535 http://www.njzhangwenjun.com/Review.asp?NewsID=520 http://www.qzmuseum.net/Review.asp?NewsID=139 http://i.misslele.com/forum.php?mod=viewthread&tid=831750 http://qzmuseum.net/Review.asp?NewsID=139 http://www.xwdlzx365.com/Review.asp?NewsID=535 http://cwc.hlbrc.cn/Review.asp?NewsID=852 http://www.hldyizhi.com/Review.asp?NewsID=1324 http://pin.ybshangjie.com/forum.php?mod=viewthread&tid=780042 http://rsxx.sdedu.net/jiaoliu1/Review.asp?NewsID=928 http://bbs.ruijie123.com/showtopic-305161.aspx http://ttkc123.com/forum.php?mod=viewthread&tid=413659 http://www.jzlsw.com/Review.asp?NewsID=1199 http://old.moto8.com/old/Review.asp?NewsID=1265 http://inclusionwsuv.org/wiki/User:Wwyi3vdz#http:.2F.2Fwww.scprt.com.2Fi… http://wiki.iproj.org/index.php?title=User:Wa4nvwuv#http:.2F.2Fwww.shiff… http://maxxyme.free.fr/wiki/index.php?title=User:B9eaniyy#http:.2F.2Fwww… http://www.yxqnlxx.cn/Review.asp?NewsID=267 http://shamanita.org/wiki/index.php?title=User:PlfvqjBf#http:.2F.2Fwww.a…
http://www.rateamateapp.com http://www.rateamateapp.com

Revision of 2.3.3 Example: Representing Sets from 18 July 2009 -

This web site can be a stroll-by way of for all the data you needed about this and didn

Post new comment

  • Web page addresses and e-mail addresses turn into links automatically.
  • Allowed HTML tags: <a> <em> <strong> <cite> <code> <pre> <hr> <ul> <ol> <li> <dl> <dt> <dd> <img>
  • Lines and paragraphs break automatically.
  • Adds typographic refinements.

More information about formatting options