이 문제는 차례 매긴 리스트(ordered list)를

균형 잡힌 두 갈래 나무(balanced binary tree)로 바꾸는 프로시저를 살펴봅니다.

실행기는 그리 필요없을 듯싶지만,

quotient 프로시저가 어떻게 작동하는지 정확히 알 수없어 돌려보았습니다.

quotient 프로시저는 몫이라는 뜻답게

6을 2로 나누면 3, 5를 2로 나누면 2, 1을 2로 나누면 0을 내놓습니다.

즉, 1 = 2 * 0 + 1이라는 식에서 몫만을 내놓는 프로시저입니다.

a.

partial-tree 프로시저가 어떻게 돌아가는지 깔끔하고 짧은 문장으로 설명하라는군요.

(SICP 206쪽)

이것을 깔끔하고 짧게라...

이건 거의 코드를 읽어내린 수준이네요.;;;

그럼 조금 바꿔서 말하겠습니다.

이것도 너무 길군요.OTL...

앞에서 프로시저를 만드는 생각을 할 때

'이미 만드는 방법을 알고 있다고 가정하고...'라는 표현을 씁니다.

(예 : 'set1의 cdr과 set2의 교집합을 어떻게 구하는지 안다 치고' - SICP 197쪽)

어차피 해당 프로시저를 호출하면 tree가 나오도록 해야할 것이니

'왼쪽 tree와 오른쪽 tree는 부르면 알아서 나온다.'라 가정하고

그렇게 나온 것들을 어떻게 구성하여 내놓을 것인가를 고민한다면

프로시저를 만드는데 좀 더 쉽게 만들 수 있지 않을까 생각했습니다.

하지만 그렇게 말을 하더라도 복잡하군요.OTL...

아직 실력이 멀었다는 증거이겠죠.ㅜㅜ

리스트 (1 3 5 7 9 11)을 넘길 경우 나무는 이렇게 그려집니다.

조금은 이상한 듯싶지만,

entry를 기준으로 큰 것과 작은 것이 각각 왼쪽과 오른쪽에 있으니 문제 없습니다.^^

b.

이 프로시저의 자람 차수(order of growth)는

연습문제 2.63의 tree->list 프로시저처럼 Θ(n)이라 생각합니다.

왜냐하면 tree의 각 entry에 맞춰 한 번씩 연산이 되고

마지막의 경우 세 번 연산이 되기 때문입니다.

각 entry는 n과 같기에 자람 차수는 Θ(n)이 됩니다.

참조

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

; 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.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))))))))

; execute
(define list1 (list 1 3 5 7 9 11))
(list->tree list1)
(newline)
(length list1)
(quotient 6 2)
(quotient 5 2)
(quotient 1 2)
(quotient 0 2)

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

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