Ch.13 탐색

(Chap.13 ) Search

Sequential search(순차탐색)는 O(n)으로 탐색알고리즘의 하한선에 해당하는 알고리즘임.
정렬된 배열을 이용한 Binary search 는 정렬하는 complexity를 제외한다면 O(logn)으로 순차탐색 보다 성능이 좋음.
정렬된 배열을 이용한 Indexed sequential search는 기정렬된 주자료에서 (n/m) x i, i = 0, 1, 2, ... 번째 record들로 구성한 index table을 만들고 index table을 우선적으로 탐색하고 실패하면 index table의 연속된 두 엔트리 사이에 해당하는 주자료 테이블 내용을 검색하는 방식임.  index table 크기(m)이 커지면  index table에서 탐색이 실패할 경우 원본 dataset에서 탐색할 대상의 크기가 작아짐.
정렬된 배열을 이용한 Interpolation search(보간탐색)
이진탐색(binary search) 방법과 매우 유사하나,
매 반복(iteration) 마다 정확히 탐색범위를 반으로 줄이는 이진탐색(binary search)과는 달리 탐색하고자 하는 값이 저장되었을 것으로 예상되는 index를 유추하는 계산식을 이용하여 탐색 횟수를 줄이려는 아이디어임.
만일 정렬된 dataset에 저장된 데이터들의 값들이 "연속된 두 항의 크기 차이"가 모두 유사하게 분포한 경우 이진탐색(binary search) 보다 실행 속도가 빠름.
그러나, 정렬된 dataset에 저장된 데이터들의 값들이 "연속된 두 항의 크기 차이"가 불균등한 경우 이진탐색(binary search) 보다 느릴 수 있으나 그래도 O(logn)임.

이진탐색트리 (BST: Binary Search Tree) vs. (AVL tree or 2-3 tree)

BST 의 성능 (time complexity)는 트리의 높이에 의존적임, 즉, O(h)
동일한 dataset 도 만일 불균형한 트리 (극단적으로 skewed binary tree)로 구성하며 탐색에 O(n)이 필요함.
따라서 탐색 속도를 O(logN) N = dataset의 크기 로 하기 위해서 트리 높이를 logN으로 유지해야함.
이를 위해 탄생한 것이 AVL tree, 2-3 tree 임.
AVL tree 구성 방법 : BST의 삽입 알고리즘을 수행하고 만일 삽입된 leaf node (A) 로 부터 root 노드 까지의 경로 중 balance factor (왼쪽 subtree의 높이 - 오른쪽 subtree의 높이) 가 2 이상인 노드(B)가 있다면 노드 A 부터 노드 B 까지의 subtree를 재구성해서 balance factor를 낮춤.