SICP 연습문제 2.66 친절한 풀이

문제

레코드 집합을 두 갈래 나무로 짜 맞춘다고 할 때, 그에 알맞은 lookup 프로시저를 구현해 보라.

문제로 부터 얻은 것

이진 트리로 저장된 자료는 탐색 알고리즘도 간편하게 짤 수 있었습니다.

문제풀이

정렬된 트리로 집합이 구현되어 있다면, key의 값을 통해 오른쪽 가지를 탐색할 지, 왼쪽 가지를 탐색할 지 결정할 수 있습니다. 여기서 key는 트리의 원소라고 하면 따로 key 프로시저를 만들 필요는 없습니다.

(define (lookup given-key set-of-records)
    (if (null? set-of-records)
        #f
        (let ((ent (entry set-of-records)))
          (cond ((eq? ent given-key)
                 ent)
                ((< given-key ent)
                 (lookup given-key (left-branch set-of-records)))
                ((> given-key ent)
                 (lookup given-key (right-branch set-of-records)))))))

예시 집합 s1에서 7과 6을 찾아보겠습니다.

(define s1 '(5 (3 (1 () ())
                  ())
               (9 (7 () ())
                  (11 () ()))))

(lookup 7 s1)
(lookup 6 s1)

읽어주셔서 감사합니다.