이 문제는 연습문제 2.63과 2.64에 나오는 프로시저를 이용하여

자람 차수(order of growth)가 Θ(n)인

union-set과 intersection-set 프로시저를 만드는 문제입니다.

잘 나오는군요.^^

방법은 간단합니다.

두 갈래 나무(binary tree)로 받은 집합을 list로 바꾼 후

연습문제 2.62와 책에 나오는 union-set, intersection-set 프로시저를 돌립니다.

그렇게 나온 리스트 결과물을 다시 tree로 바꾸어 처리하여 결과를 내놓습니다.

그럼 이것의 자람 차수가 Θ(n)인지 확인해보겠습니다.

list->tree 프로시저 : Θ(n)

union-set 프로시저 : Θ(n)

intersection-set 프로시저 : Θ(n)

tree->list-1 프로시저 : Θ(n)

tree->list-2 프로시저 : Θ(n)

이를 한 번에 사용하지 않고 하나씩 차례차례 사용하므로

곱셈 연산이 아닌 덧셈 연산이 된다고 생각합니다.

즉, Θ(n) + Θ(n) + Θ(n) + Θ(n)이기에

따라서 해당 두 프로시저의 자람 차수는 Θ(n)이 됩니다.

이런 생각을 하였지만 사실 여부를 잘 모르겠습니다.

n이 2일 때 생각해보니 위의 가정이 맞는 듯싶어 확정을 한 것입니다.

아직 자람 차수에 대해서는 그 명확함을 얻지 못했기에 어렵습니다.OTL...

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 207

(define true (= 0 0))
(define false (= 0 1))
; BINARY TREES
(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))

; exercise 2.63
(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 '()))
; exercise 2.64
(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))))))))
; exercise 2.62
(define (union-set-orderlist set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        ((let ((x1 (car set1)) (x2 (car set2)))
          (cond ((= x1 x2)
                 (cons x1 (union-set-orderlist (cdr set1) (cdr set2))))
                ((< x1 x2)
                 (cons x1 (union-set-orderlist (cdr set1) set2)))
                ((> x1 x2)
                 (cons x2 (union-set-orderlist set1 (cdr set2)))))))))
; section 2.3.3
(define (intersection-set-orderlist set1 set2)
  (if (or (null? set1) (null? set2))
      '()
      (let ((x1 (car set1)) (x2 (car set2)))
        (cond ((= x1 x2)
               (cons x1
                     (intersection-set-orderlist (cdr set1)
                                       (cdr set2))))
              ((< x1 x2)
               (intersection-set-orderlist (cdr set1) set2))
              ((< x2 x1)
               (intersection-set-orderlist set1 (cdr set2)))))))

; answer
(define (union-set set1 set2)
  (list->tree (union-set-orderlist
               (tree->list-1 set1)
               (tree->list-2 set2))))

(define (intersection-set set1 set2)
  (list->tree (intersection-set-orderlist
               (tree->list-2 set1)
               (tree->list-1 set2))))

; execute
(define tree1 (list->tree (list 1 3 5 7 9 11)))
(define tree2 (list->tree (list 2 4 5 6 8 9 11 13)))
tree1
tree2
(newline)
(tree->list-1 tree1)
(tree->list-2 tree2)
(newline)
(union-set tree1 tree2)
(intersection-set tree1 tree2)
(newline)
(tree->list-1 (union-set tree1 tree2))
(tree->list-2 (intersection-set tree1 tree2))

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.