C언어 기초/자료구조/C로 배우는 쉬운 자료구조/Chapter10. 검색_요약

01 검색

• 자료 검색은 원하는 탐색키를 가진 항목을 찾는 것.
• 검색 성공: 찾음
• 검색 실패: 찾지 못함

 

02. 검색 방법의 분류

•  비교 검색 방식 Comparison Search Method: 검색 대상의 키를 비교(순차, 이진, 트리)
•  계산 검색 방식 Non-comparison Search Method: 계수적인 성질을 이용한 계산(해싱)

 

03. 기본 순차 검색

•  순차 검색 Sequential Sesarch은 일렬로 나열된 자료를 처음부터 마지막까지 순서대로 비교
• 가장 간단하고 직접적인 방법
• 배열이나 연결리스트로 구현한 선형 자료구조에서 원하는 항목을 찾는 방법
• 정렬 필요 없음

 

04. 색인 순차 검색

• 색인 순차 검색 Index Sequential Search은 인덱스 테이블을 추가로 사용 → 탐색의 효율 높임
• 찾을 키값을 인덱스 테이블에서 검색하여 indexTable[i].key <= key < indexTable[i+1].key를 만족하는 i를 ㅊ자아 알아낸 범위에 대해서만 순차 검색 수행
• 정렬된 배열 사용
•  

05. 이진 검색

•  이진 검색 Binary Search은 가운데 있는 항목을 키값과 비교
•  키값이 더 큼 → 오른쪽 부분 검색
•  키값이 더 작음 → 왼쪽 부분 검색
•  반드시 정렬되어 있는 자료에서 사용

 

06. 이진 트리 검색

•  이진 트리 검색 Binary  Tree Search은 이진 탐색 트리 이용

 

07. 해싱

• 해싱 Hashing은 계수적인 성질을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식
• 해싱 검색은 키값에 대해 해시 함수를 계산하여 주소를 구하고,
• 구한 주소에 해당하는 해시 테이블로 바로 가서 항목이 있으면 검색 성공, 없으면 검색 실패!

 

08. 해시 테이블에서 충돌 해결 방법

• 해시 테이블 Hash Table 에서 오버플로로 인해 충돌이 발생했을 때 해결하는 방법
• 선형 개방 주소법: 충돌이 일어난 키값을 다른 비어 있는 버킷을 찾아 저장
• 체이닝: 항목을 여러 개 저장할 수 있도록 해시 테이블의 구조를 변경(연결 리스트)