자료구조 4 탐색

 

 

 

 

 

 

 

1. 순차 탐색

: 정렬되지 않은 배열을 처음부터 마지막까지 하나씩 검사한다.

 

1) 시간 복잡도

- 평균 비교 횟수

if 탐색 성공 : (n+1)/2

if 탐색 실패 : n번 비교

따라서 시간복잡도는 O(n)이다.

 

 

2) 코드

 

 

 

 

 

 

 

2. 개선된 순차 탐색

: 리스트 끝에 탐색 키를 저장한다.

(* 탐색 키 : 찾는 값 )

 

 

 

1) 코드

 

 

 

 

 

 

 

3. 이진 탐색(binary search)

 

1) 동작 방식

: 정렬된 배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분에 배열에 있는지 알아내어

탐색의 범위를 반으로 줄여 가며 탐색을 진행한다.

 

 

 

 

 

 

2) 코드

 

 

3) 시간 복잡도

: log2(N)

 

 

 

 

 

 

4. 색인 순차탐색

: 인덱스 테이블을 사용하여 탐색의 효율을 증대시킨다.

-> 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다.

 

 

 

1) 시간 복잡도

O( (m+n)/m )

 

 

 

 

 

 

5. 보간 탐색

: 사전이나 전화번호부를 탐색하는 방법이다.

 

1) 작동 방식

: 탐색 키가 존재할 위치를 예측하여 탐색한다.

이진 탐색과 유사하나, 리스트를 불균등 분할하여 탐색한다.

 

2) 시간 복잡도

O(log(n))

 

3) 탐색 위치

 

 

 

 

 

 

4) 코드

 

 

 

 

 

 

 

 

 

 

 

6. 균형 이진탐색트리

 

- 이진탐색 vs 이진탐색트리 

1) 이진탐색 : 배열 사용하므로 삽입 / 삭제가 매우 비효율

2) 이진탐색트리 : 트리를 사용하므로 삽입 / 삭제가 매우 빠르다.

 

 

 

3) 시간 복잡도

- 균형 트리 : O(logn)

- 불균형 트리 : O(n), 순차탐색과 동일하다.

 

 

 

 

 

 

 

7. AVL 트리

: 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 이진탐색트리이다.

- 트리가 비균형 상태이면 스스로 노드를 재배치하여 균형 상태로 유지시킨다.

 

 

1) 개념

균형 인수 : (왼쪽 서브트리 높이 - 오른쪽 서브트리 높이)

모든 노드의 균형 인수가 +-1 이하이면 AVL 트리이다.

 

 

2) 시간복잡도

O(logn) : 균형 트리이므로

 

 

 

 

3) 삽입 연산 시,

 

 

 

 

 

 

Ex 1) LL

 

 

 

 

Ex 2) LR

 

 

 

 

Ex 3) RL

 

 

 

 

Ex 4) RR