자료구조 검색(탐색)

소개글

자료구조 검색(탐색) 과제물 및 시험 자료입니다.

중간고사, 기말고사 및 과제물 작성시 많은 도움이 될 것 입니다.

목차

1. 검색(Search)의 정의
2. 순차 검색(Linear Search)
3. 피보나치 검색(Fibonacci Search)
4. 보간 검색(Interpolation Search)
5. 블록 검색(Block Search)
6. 이진 트리 검색(Binary Tree Search)

본문내용

1. 검색(Search)
1. 정의
(1) 검색은 기억 장치에 저장되어 있는 파일에서 원하는 레코드를 찾는 과정이며, 리스트의 레코드를 키와
비교하여 검색하는 방식과 특정 함수를 이용하여 레코드의 위치를 계산하여 탐색하는 방법이 있다.
(2) 탐색 작업 시 고려 사항
① 자료를 적절한 구조로 기억 공간에 표현하는 문제
② 원하는 자료를 찾는 적절한 방법의 선택
③ 수행 가능한 기억 공간의 요구량
④ 알고리즘의 복잡도 및 자료의 이용 횟수

(중략)

4. 보간 검색(Interpolation Search)
1. 정의
(1) 사전에서 단어를 찾는 것처럼 검색 대상 자료가 있음직한 부분을 계산하여 비교 검색하는 방법이다.
(2) 보간 검색의 성능은 키의 분포 상태에 영향을 받으므로 일양 분포(균등 분포)일 경우 평균적인 탐색은
2진 탐색보다 우수하다.
(3) 그러나 키가 군집되어있다면 순차 검색과 같은 결과를 초래할 수 있을 뿐 아니라 키를 결정할 때 곱셉과
나눗셈의 산술식을 수행하므로 계산이 느려진다.

(중략)

6. 이진 트리 검색(Binary Tree Search)
1. 정의
(1) 공백이 가능한 이진 트리로, 공백이 아니라면 특정 부 노드를 기준으로 자 노드 값이 크면 오른쪽에, 작으면 왼쪽에 배치할 수 있는 트리이다.
(2) 모든 원소는 key를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다. 즉, key는 유일한 값을 갖는다.
(3) 이진 검색 트리는 키 입력 순서에 따라 다른 모습을 갖는다.

2. 특징
(1) 검색 비교 횟수는 노드의 레벨 수이다. (구조 모양이 검색에 영향을 미친다.)
(2) 트리 검색은 검색할 자료를 이진 검색 트리로 구성하여 검색에 이용하는 것으로 연산 시간은 이진 검색과 비슷하다.

참고 자료

자료구조와 C ㅣ 이석호 저 | 정익사