이 문제는 데이터베이스에서

어떤 열쇠에 맞는 레코드를 찾아내는 lookup 프로시저를 만드는 문제입니다.

책에 데이터베이스가 차례 없는 리스트로 구현되어있다면

lookup 프로시저를 어떻게 만들어야 하는지 예가 나와있습니다.

문제는 데이터베이스가 두 갈래 나무(binary tree)로 되어있을 때

같은 기능을 하는 lookup 프로시저를 만들어야 합니다.

잘 되는군요..가 아니네요.^^

왜냐하면 key 라는 프로시저를 모르니까요.

다만 두 갈래 나무로 만들어져있기에

그에 맞는 element-of-set? 프로시저를 변경하였습니다.(SICP 203쪽)

그리고 키가 숫자인지 어떤지 알 수없기에

less?, more?라는 프로시저를 만들어 후에 변경이 가능하도록 하였습니다.

(일단은 숫자로 생각하였습니다.)

참조

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

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

; answer
(define (lookup given-key set-of-records)
  (let ((less? (lambda (a b) (< a b))) ; key표현에 따라 변할 수 있음.
        (more? (lambda (a b) (> a b)))) ; key표현에 따라 변할 수 있음.
    (cond ((null? set-of-records) false)
          ((equal? given-key (key (entry set-of-records)))
           (entry set-of-records))
          ((less? given-key (key (entry set-of-records)))
           (lookup given-key (left-branch set-of-records)))
          ((more? given-key (key (entry set-of-records)))
           (lookup given-key (right-branch set-of-records))))))

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

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