#6-2-2 The Art of Computer Programming - 정렬과 검색

이전 절에서는 암묵적인 이진트리 구조를 사용해서

이진 검색과 피보나치식 검색을 좀 더 쉽게 이해할 수 있었다.

 

N의 주어진 임의의 값에 대해, 이진 검색에 대응하는 트리는 키 비교를 통해서

표를 검색하는데 필요한 이론적인 최소 비교 횟수를 달성한다.

그러나 고정된 크기의 표에 대해서만 적합하다.

왜냐면 레코드들의 삽입/삭제 시 비용이 꽤 비싸기 때문이다.

레코드들이 자주 변한다면 이진 검색을 통한 줄인 시간보다 관리하는 시간이 더 커질 수 있다.

 

레코드들이 자주 변하는 성장하는 테이블을 검색하는 기법들을 흔히 기호표 알고리즘이라고 부른다.

어셈블러나 컴파일러, 기타 시스템 루틴들이 사용자 정의 기호들을 관리하는 데 사용되기 때문이다.

 

트리 삽입 정렬 : 트리 삽입 정렬과 빠른정렬이 달라고 그 분석들 사이에는 강한 연관관계가 존재한다.

 

최적 이진 검색 트리에 대해서도 소개한다.

주어진 빈도들을 가진 키들의 테이블을 검색하는 가능한 최고의 트리를 구하고 싶은 경우에 해당한다.