14장 탐색
- 정리의 기반은 학교 강의 노트와 [c언어로 쉽게 풀어쓴 자료구조]를 참고하였습니다.
저의 정리가 옳지 않다면 피드백 부탁드립니다.
탐색
순차 탐색
- 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법
- 탐색 성공 -> 인덱스 반환
- 탐색 실패 -> 종료 후 -1 반환
개선된 순차 탐색
- 리스트의 끝을 찾는 값으로 하고, 반복문 탈출 조건을 키 값을 찾을 때까지로 설정
- ex) for (i = low; list[i] != key; i++)
- 시간 복잡도 : O(n)
이진 탐색
- 정렬된 배열의 탐색에 가장 적합
- 시간 복잡도 : O(log n) (로그 밑 = 2)
![binarySearch]()
색인 순차 탐색(Indexed Sequential Search)
- 인덱스 테이블을 사용하여 정렬된 배열을 탐색
- 인덱스 테이블도 정렬이 되어있어야 함
- ex) index[i] <= key <= index[i+1]을 만족하는 항목 탐색
- 성능이 인덱스 테이블 크기에 따라 좌우됨
- 인덱스 테이블 크기가 크면, 주 자료 리스트 탐색 시간이 증가
- 인덱스 테이블 크기가 작으면, 주 자료 리스트 탐색 시간이 감소하는 대신, 인덱스 테이블 크기의 탐색 시간이 증가
- 시간 복잡도 : O(m + n/m)
- m = 인덱스 테이블 크기
- n = 자료 리스트 크기
보간 탐색(Interpolation Search)
- 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색
- 불균등 분할 탐색
- 탐색 위치 = (k - list[low]) / (list[high] - list[low]) * (high - low) + low
![interpolation]()
- 시간 복잡도 : O(log n) (로그 밑 = 2)
이진 탐색 트리(Binary Search Tree)
- 이진 탐색(배열)이랑 비슷하긴 하나, 삽입과 삭제가 더 용이하다.
- 시간 복잡도 : O(log n) (로그 밑 = 2)
- 균형트리가 아닐 경우(최악의 경우) : O(n)
균형트리 여부가 중요
- AVL 트리 : 스스로 노드를 재배치하여 균형 상태로 만드는 이진 탐색 트리
- 균형 상태란 ? : 왼쪽 서브 트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하인 상태
- 시간 복잡도 : 항상 O(log n) (로그 밑 = 2)
- 균형 인수 : 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이
- 균형인수가 +-1 이하인 트리가 AVL 트리
- AVL 트리의 삽입 연산 : 균형 인수가 +-2가 된 가장 가까운 조상 노드의 서브 트리들에 대해 다시 균형을 잡는다.
- 균형을 잡기 위해 새로운 노드부터 조상 노드까지 회전 시킨다
- 회전 방법
LL, LR, RR, RL
- 트리의 높이 계산 : 루트 노드의 왼쪽 서브 트리와 오른쪽 서브 트리에 대하여 순환 호출을 사용하여 각각의 높이를 구한 후, 더 큰 값에 +1을 한다.