보간 탐색과 피보나치

(연습문제 18 참조.) 이것은 동일 빈도 분석으로 예측한 것의 약 절반이며, 이진 탐색을 사용할 때보다 적다.

그림 12는 가장 일반적인 31개의 영어 단어가 빈도의 내림차순으로 입력될 때 결과로 생기는 트리를 보여준다. 각 단어와 함께 상대 빈도가 표시되어 있으며, H. F. Gaines의 Cryptanalysis (New York: Dover, 1956), 226의 통계를 사용했다. 이 트리에서 성공적인 탐색의 평균 비교 횟수는 4.042이다. 알고리즘 6.2.1B 또는 6.2.1C를 사용하는 해당 이진 탐색은 4.393회의 비교가 필요할 것이다.

그림 12. 가장 일반적인 31개의 영어 단어, 빈도의 내림차순으로 삽입됨.

그림 12. 가장 일반적인 31개의 영어 단어, 빈도의 내림차순으로 삽입됨.

최적 이진 탐색 트리. 이러한 고려 사항들은 주어진 빈도를 가진 키 테이블을 탐색하기 위한 최적의 트리에 대해 묻는 것을 자연스럽게 만든다. 예를 들어, 가장 일반적인 31개의 영어 단어에 대한 최적 트리는 그림 13에 나와 있다. 이것은 평균 성공적인 탐색에 3.437회의 비교만 필요로 한다.

그림 13. 가장 일반적인 31개의 영어 단어에 대한 최적 탐색 트리.

그림 13. 가장 일반적인 31개의 영어 단어에 대한 최적 탐색 트리.

이제 최적 트리를 찾는 문제를 탐구해 보자. N = 3일 때, 예를 들어, 키 K₁ < K₂ < K₃가 각각 확률 p, q, r을 갖는다고 가정하자. 다섯 가지 가능한 트리가 있다:

그림 14는 각 트리가 최적인 p, q, r의 범위를 보여준다. 균형 트리는 p, q, r을 무작위로 선택하면 약 45%의 시간 동안 최선이다(연습문제 21 참조).