하나의 집합 인터페이스는 여러 구조적 약속을 활용할 수 있다.
무순서 리스트와 정렬 리스트와 이진 탐색 트리를 비교하면서 포함 검사와 추가라는 추상 질문을 표현별 순회와 분리합니다.
집합 표현이 순서나 탐색 트리 모양을 약속하면 어떤 연산이 더 적은 일을 할 수 있을까요?
- 무순서 리스트 집합의 포함 검사와 추가 구현하기
- 오름차순을 이용해 포함 검사를 일찍 멈추고 제자리에 삽입하기
- 이진 탐색 트리의 각 비교에서 한 갈래만 따라가기
- 포함 의미를 바꾸지 않고 트리 집합을 정렬 수열로 바꾸기
- 유한한 트리 모양에서 균형과 탐색 비용 비교하기
무순서 리스트 집합은 중복을 검사한 뒤 새 원소를 앞에 놓을 수 있습니다. 정렬 리스트 집합은 오름차순에 주목합니다. 현재 원소가 목표보다 이미 크면 포함 검사를 멈출 수 있고 추가는 그 앞에 삽입할 수 있습니다. 추상 질문은 같지만 표현 불변식이 프로세스를 바꿉니다.
이진 탐색 트리는 더 작은 원소를 왼쪽에, 더 큰 원소를 오른쪽에 둡니다. 각 비교는 모든 원소를 훑지 않고 한 갈래를 고릅니다. tree->list는 중위 순회로 정렬 수열을 되찾습니다. 직접 만든 트리는 균형 모양에서의 탐색 규칙을 보여 주고 한쪽으로 기운 트리는 선형 경로를 드러냅니다.
- 출력
- —
- 값
- —
- 진단
- —
리스트 집합 프로그램은 ((1 3 5) (4 1 3 5) #f (1 3 4 5 7))을 반환합니다. 트리 프로그램은 (#t #f (1 3 4 5 7 8 9))를 반환합니다.
무순서 전체 순회와 5 앞에서 멈추는 정렬 순회를 비교하세요. ordered-adjoin에서는 삽입 지점 하나를 찾으세요. 트리에서는 각 비교가 왼쪽과 오른쪽 중 어느 갈래를 고르는지 기록한 뒤 tree->list의 전체 중위 순회와 대조하세요.
프로그램을 수정하고 결과를 비교해 보세요.
adjoin-tree를 구현하고 표본 트리에 6을 삽입하세요. 포함 검사와 정렬된 tree->list 결과를 확인한 뒤 일부러 한쪽으로 기운 트리를 만들고 균형 트리의 로그 경로와 기운 트리의 선형 경로를 비교하세요.
힌트 보기
tree-member?와 같은 세 비교 경우를 사용하되 새 값이 들어간 갈래만 다시 구성하세요.