자료구조에서의 검색 ( 순차 검색, 이진 검색, 이진 트리 검색, 해싱)

 

---

검색이란

"검색"이란 여러 자료들 중에서 원하는 것을 찾는 것이다.

이러한 검색 연산은 자료구조에서 삽입 연산과 삭제 연산을 할 때 원하는 자료를 삽입하거나 삭제할 때 요구된다.

---

검색의 종류

검색이 수행되는 위치에 따른 분류
-내부 검색(Internal Search) : 메모리 내의 자료에 대해서 수행
-외부 검색(External Search) : 메모리의 외부에 있는 보조 기억 장치에 있는 자료에 대해서 수행

검색 방법에 따른 분류 
-비교 검색 방식(Comparison Search Method) : 검색 대상의 키를 비교하여 검색하는 방법
ex) 순차 검색, 이진 검색, 트리 검색
-계산 검색 방식(Non-comparison Method) : 계수적인 성질을 이용한 계산으로 검색하는 방법"
ex) 해싱

 

---

순차 검색

"순차 검색(Sequential Search)"이란
선형으로 되어있는 자료를 가장 처음부터 마지막 자료까지 순서대로 검색하는 방법이다.
이는 가장 간단하고 직접적인 방법으로,
배열이나 연결 리스트로 구현된 순차 자료구조에서 원하는 항목을 찾는 방법이라 할 수 있다.
따라서 알고리즘이 단순하여 구현이 쉽지만, 자료의 양이 많아졌을 경우에는 비효율적이게 된다.

"색인 순차 검색(Index Sequential Search)"이란
인덱스 테이블을 추가로 사용하여 탐색의 효율을 높인 검색 방법이다. 
색인 순차 검색의 성능은 인덱스 테이블의 크게에 따라 달라진다.
인덱스 테이블의 크기가 줄어들면 배열의 인덱스를 저장하는 간격이 커지므로 배열에서 검색하는 범위도 커진다고 할 수 있다.

 

---

이진 검색

"이진 검색(Binary Search)"란
자료의 가운데에 있는 항목을 키값과 비교하여 키 값이 더 크면 오른쪽 부분을 검색하고,
키 값이 더 작으면 왼쪽 부분을 검색하는 방법이다.
이진 검색은 자료가 정렬되어 있지 않으면 사용할 수 없다.

"이진 트리 검색(Binary Tree Search)"란
이진 탐색 트리를 사용하여 검색하는 방법이다.
이진 트리 검색은 검색하는 과정 자체는 간단하지만, 이진 탐색 트리의 원소의 삽입이나 삭제 연산이 복잡한 과정이 있다.

---

해싱

"해싱(hashing)"이란
산술적인 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 검색 방식이다.
키값을 원소의 위치로 변환하는 함수를 해싱 함수(Hashing Function) 라고 한다.
해싱 함수에 의해 계산된 주소의 위치에 항목을 저장한 표를 해시 테이블이라고 한다.

"해싱 검색 방법"이란

해싱 검색은 키값에 대해서 해싱 함수를 계산하여 주소를 구하고, 구한 주소에 해당하는 해시 테이블에 찾는 항목이 있으면
검색이 되고, 없으면 검색 되지 않는 방식이다.

 

---

출처
자바로 배우는 쉬운 자료구조