검색 (1) - 개요

1. 검색이란 ?

• 자료 집합에서 원하는 데이터를 찾아내는 것

• 검색의 3요소 : 검색, 삽입, 삭제

• 검색과 삽입과 삭제가 빨라야 좋은 검색 알고리즘이다.

 

2. Key와 Record 

• Key : 해당 데이터를 유일하게 구별되도록 해주는 값 (e.g. 주민등록번호, 사원번호 등)

• Record : 해당 Key의 전체 데이터 (사원번호가 1번인 사원의 이름, 나이, 부서, 연봉 등)

 

3. 검색의 종류 : 

• 차원) 1차원 검색 : Key가 1개 (사원번호가 9인 사원 검색)

• 차원) 다차원 검색 : Key가 여러개 (직책이 대리이고 부서가 총무부인 사원 검색)

• 범위) 단일 키 검색 : Key가 고정되어있는 검색 (나이가 30인 사원)

• 범위) 범위 검색 : Key가 범주형인 검색 (나이가 30보다 크고 40보다 작은 사원)

 

4. 검색 알고리즘 종류 :

• 순차 검색 (Sequantial Search)

• 이분 검색 (Binary Search)

• 내분 검색 (Interpolation Search)

• 이진트리 검색 (Binary Search Tree)

• AVL 트리 (AVL Tree)

• 레드블랙 트리 (Red Black Tree)

• 기수 검색 (Radix Search)

• B 트리 (B Tree)

• 해싱 (Hasing)

 

등등 다양한 검색 알고리즘 존재

 

5. Reference