이 문제는 표를 검색할 때 좀 더 빠르게 찾는 방법을 제시합니다.

표를 만들 때 키의 차례를 두어 정렬을 한 후 이를 찾도록 하는 것입니다.

그리고 이진 나무(binary tree)를 이용하여 설명하라고 되어있습니다.

처음에는 이를 프로시저로 구현하는 것이라 생각했으나

너무 복잡한 듯싶고 '설명하라'라고 적혀있어 글로 적기로 하였습니다.

알고리즘 강의 PDF

Binary Tree에 대해서 자세히 알지 못하는 터라 어떤 것을 써야할지 모르겠지만,

1학기 때 청강한 알고리즘 시간에 들은 내용이 생각났습니다.

위처럼 root를 기준으로

left에는 root보다 작은 값이, right에는 root보다 큰 값이 들어가도록 만듭니다.

그렇게 나무를 만들었을 때 root를 보고 자신이 가야할 방향을 결정합니다.

이는 이상이하게임과 비슷하다고 생각합니다.

'이상 이하 게임'

그리고 이를 Lisp에서 구현할 때 이렇게 하면 될 듯싶습니다.

cons로 pair를 만들고 처음 car에는 root의 key를

cdr에는 car에 left tree porinter를 cdr에 right tree pointer를 넣습니다.

즉, internal vertex는 이렇게 구현을 하는 것입니다.

그리고 terminal vertex는 이렇게 구현합니다.

car에는 key를 cdr에는 value를 넣습니다.

끝에 있는 vertex이기에 다른 vertex를 가리킬 필요는 없습니다.

물론 구현을 할 때 이런 일이 발생할 듯도 싶습니다.

vertex를 넣거나 삭제할 때 tree를 다시 그려야하므로

이 때 부모 vertex를 알아야 할 필요가 있을 듯싶습니다.

그럴 때는 internal vertex 구현에서 가운데에 부모 vertex pointer를 넣어야합니다.

라고 글을 적어놓고 문제에 적혀진 연습문제 2.66과 견주어 보라는 말에 살펴보니

여기서 Binary Tree를 구현하였군요.

'SICP Exercise 연습문제 2.66'

그럼 여기서도 구현해야합니까?OTL.....

참조

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

http://security.re.kr/~sjkim/sjkim_lectures.html

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

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