NoSyu의 주저리주저리 :: SICP Exercise 연습문제 2.63

이 문제는 두 갈래 나무(binary tree)를 리스트로 바꾸는 프로시저를 살펴보고

결과물이 어떻게 나오는지, 자람 차수(order of growth)가 어떤지 확인하는 문제입니다.

실행식이 조금 깁니다.

두 프로시저는 어떤 나무를 집어넣어도 같은 결과를 냅니다.

그 예로 그림 2.16의 나무를 각각 집어넣었더니(tree1, 2, 3)

(1 3 5 7 9 11)이라는 결과를 모두 똑같이 내놓았습니다.

혹시나 다른 것도 되는가 싶어 그림 2.17에 나오는 나무도 해보았습니다.(tree4)

역시 문제없이 잘 되었습니다.

두 프로시저의 자람 차수는 Θ(n)으로 같다고 생각합니다.

왜냐하면 두 프로시저 모두 하나의 원소에 한 번씩

그리고 마지막에 달린 원소는 세 번 실행되기에(끝의 원소는 null을 두 개 가지므로)

전체적으로 Θ(n)의 자람 차수를 가진다고 생각합니다.

하지만 성능만을 따진다면 append 프로시저가 있는

tree->list1 프로시저가 조금 느리지 않을까 싶습니다.

참조

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

(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))
(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)))))
(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))))))

; exercise 2.63 - a
(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 '()))

; execute
(define tree1 (make-tree 7
                         (make-tree 3
                                    (make-tree 1 null null)
                                    (make-tree 5 null null))
                         (make-tree 9 null (make-tree 11 null null))))
(define tree2 (make-tree 3
                         (make-tree 1 null null)
                         (make-tree 7
                                    (make-tree 5 null null)
                                    (make-tree 9 null (make-tree 11 null null)))))
(define tree3 (make-tree 5
                         (make-tree 3 (make-tree 1 null null) null)
                         (make-tree 9
                                    (make-tree 7 null null)
                                    (make-tree 11 null null))))
(define tree4 (make-tree 1 null (make-tree 2 null (make-tree 3 null (make-tree 4 null (make-tree 5 null (make-tree 6 null (make-tree 7 null null))))))))

tree1
tree2
tree3
(tree->list-1 tree1)
(tree->list-1 tree2)
(tree->list-1 tree3)
(tree->list-2 tree1)
(tree->list-2 tree2)
(tree->list-2 tree3)
(newline)
tree4
(tree->list-1 tree4)
(tree->list-2 tree4)

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