CHAP 12: 탐색 순천향대학교 컴퓨터학부 2015. 11. 23 하 상 호.

Presentation on theme: "CHAP 12: 탐색 순천향대학교 컴퓨터학부 2015. 11. 23 하 상 호."— Presentation transcript:

1 CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호

2 탐색이란? 탐색(search)은 탐색은 기본적으로 여러 개의 자료 중에서 원하는 자료를 찾는 작업
컴퓨터가 가장 많이 하는 작업 중의 하나 탐색을 효율적으로 수행하는 것은 매우 중요. 탐색키(search key): 항목과 항목을 구별해주는 키(key) 탐색을 위하여 사용되는 자료 구조 배열, 연결 리스트, 트리, 그래프 등 탐색키 데이터

3 순차 탐색 순차 탐색(sequential search)은 탐색 방법 중에서 가장 간단하고 직접적인 탐색 방법
순차 탐색은 정렬되지 않은 배열의 항목들을 처음부터 마지막까지 하나씩 검사하여 원하는 항목을 찾아가는 방법

4 순차 탐색 알고리즘 알고리즘 복잡도 탐색 성공시 탐색 실패시
int seq_search(a: array of integers, key, low, high: integer) { i: integer; // 탐색이 성공이면, 키 값의 인덱스를 반환화고, // 탐색이 실패이면, -1을 반환하라. }

5 개선된 순차탐색 순차 탐색에서 비교 횟수를 줄이기 위해 리스트의 끝에 찾고자 하는 키 값을 저장하고 반복문의 탈출 조건을 키 값을 찾을 때까지로 설정

6 개선된 순차탐색 알고리즘 알고리즘 복잡도는? int seq_search2(list: array of integers, key, low, high: integer) { i: integer; list[high+1] = key; // 리스트 끝에 키 값 배치 // 탐색이 성공이면, 키 값의 인덱스를 반환화고, // 탐색이 실패이면, -1을 반환하라. }

7 ⅹ 이진탐색 영어사전 정렬된 배열의 탐색에는 이진 탐색(binary search)이 적합
배열의 중앙에 있는 값을 조사하여 찾고자 하는 항목이 왼쪽 또는 오른쪽 부분 배열에 있는지를 알아내어 탐색의 범위를 반으로 줄인다. (예) 10억 명중에서 이진 탐색을 이용하여 특정한 이름을 탐색 순차 탐색에서 비교 회수는? 이진탐색에서 비교 회수는? 5을 탐색하는 경우 7과 비교 영어사전 1 3 5 6 7 9 11 20 30 ⅹ 5< 7이므로 앞부분만을 다시 탐색 moveable 1 3 5 6 7 9 11 20 30 move 5를 3과 비교 1 3 5 6 7 9 11 20 30 5> 3이므로 뒷부분만을 다시 탐색 1 3 5 6 7 9 11 20 30 5==5이므로 탐색성공 data 1 3 5 6 7 9 11 20 30

8 이진탐색 알고리즘 알고리즘 알고리즘 복잡도는?
search_binary(list: array of integers, key, low, high: integer) { // 탐색 성공시 색인 값 반환하고, 그렇지 않으면 -1 반환 middle: integer; if (low <= high) { middle = (low + high) / 2; } return -1;

9 이진탐색 알고리즘 (반복 버전) 알고리즘 알고리즘 복잡도는?
search_binary(list: array of integers, key, low, high: integer) { middle: integer; }

10 색인순차탐색 색인 순차 탐색(indexed sequential search) 방법은 인덱스(index)라 불리는 테이블을 사용하여 탐색의 효율을 높이는 방법 인덱스 테이블은 주 자료 리스트에서 일정 간격으로 발췌한 자료를 가지고 있다. 주 자료 리스트와 인덱스 테이블은 모두 정렬되어 있어야 한다. 인덱스 테이블 구조체 typedef struct { int key; int index; } 22 자료 리스트 크기가 n이고, 인덱스 테이블 크기가 m이면, 인덱스 테이블 항목 i는 자료 리스트의 i *(n/m)번째 항목을 갖는다.

11 색인순차탐색 알고리즘 인덱스 테이블 구조체 typedef struct { int key; int index; }
Integer searchIndex(a, itab: array of integers, key, n, m: integer) { I, low, high: integer; if (key < a[0] or key > a[n-1]) // key가 리스트 범위에 속하지 않으면 then return -1; // key가 속한 인덱스 테이블 구간을 결정해서, 그 구간내 순차 탐색 수행 return seqSearch(a, key, low, high); } for (i=0; i < m; i++) do // key가 속한 테이블 구간 결정 if (key >= itab[i].key and key < itab[i+1].key) then break; end if end for 22 if (i < m) then else

12 보간 탐색 보간 탐색(interpolation search)은 사전이나 전화번호부를 탐색하는 방법과 같이 탐색키가 존재할 위치를 예측하여 탐색하는 방법 사전을 찾을 때 ‘ㅎ’으로 시작하는 단어는 사전의 뒷부분에서 찾고 ‘ㄱ'으로 시작하는 단어는 앞부분에서 찾는 것과 같은 원리이다. 보간 탐색은 이진 탐색과 유사하나 리스트를 반으로 분할하지 않고 불균등하게 분할하여 탐색한다. (자료는 정렬되었다고 가정) 값과 위치가 비례한다고 가정

13 보간 탐색 예제 리스트: (3, 9, 15, 22, 31, 55, 67, 88, 89, 91) Key: 55 탐색 위치는?

14 보간 탐색 알고리즘 복잡도는? Integer searchInterpolation(a: array of integers, key, n: integer) { I, low, high: integer; low <- 0; high <- n-1; while (key > a[low] and key <= a[high]) { // 탐색이 종료되지 않았으면 } if(a[low] == key) then return low; else return -1

15 균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉 자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 한다. 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 삽입, 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다. 이진 탐색 트리는 균형 트리를 보장하지 않는다. 이진탐색트리에서의 시간복잡도 균형트리: 불균형트리:

16 Recall: 이진 탐색 트리 정의? 탐색 알고리즘 모든 원소의 키는 유일
Key(왼쪽 서브트리의 노드) < Key(루트 노드) Key(오른쪽 서브트리의 노드) > Key(루트 노드) 왼쪽, 오른쪽 서브트리도 이진 탐색 트리 탐색 알고리즘 Search(T, key) { p <- T; }

17 AVL 트리 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리
각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 트리는 균형 트리를 항상 보장 정의 균형 인수(balance factor): (왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이) 모든 노드의 균형 인수가 ±1 이하이면 AVL 트리이다.

18 AVL 트리의 연산 탐색연산: 이진탐색트리와 동일
균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입 연산과 삭제 연산시이다. 삽입 연산시에는 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 따라서 즉 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 한다.

19 AVL 트리의 삽입 연산 균형트리로 만드는 방법: 회전(rotation)
AVL 트리에서 균형이 깨지는 경우에는 다음의 4가지의 경우가 있다. 새로 삽입된 노드 N로부터 가장 가까우면서 균형 인수가 ±2가 된 조상 노드를 A라고 하자. LL 타입: N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. LR 타입: N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. RR 타입: N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. RL 타입: N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. N A

20 예제: AVL 트리의 삽입 연산 LL 타입 LR 타입 8 8 2 9 2 1 7 1 5

21 예제: AVL 트리의 삽입 연산 RR 타입 RL 타입 2 7 1 5 8 3 7 9 4

22 삽입 연산: LL 유형 N을 A의 왼쪽 서브트리의 왼쪽 서브트리에 삽입 방법: LL 회전 N: 새로 삽입된 노드
A: N으로부터 가장 가까우면서 균형인수가 ±2가 된 조상 노드 방법: LL 회전 A부터 N까지의 경로상의 노드들을 오른쪽으로 회전

23 삽입 연산: LL 유형 예제 8 2 1

24 삽입 연산: LL 유형 알고리즘 nodeptr rotateLL(A: nodeptr) { B: nodeptr; return B;
}

25 삽입 연산: RR 유형 N을 A의 오른쪽 서브트리의 오른쪽 서브트리에 삽입 방법: RR 회전 N: 새로 삽입된 노드
A: N으로부터 가장 가까우면서 균형인수가 ±2가 된 조상 노드 방법: RR 회전 A부터 N까지의 경로상의 노드들을 왼쪽으로 회전

26 삽입 연산: RR 유형 예제 7 8 9

27 삽입 연산: RR 유형 알고리즘 nodeptr rotateRR(A: nodeptr) { B: nodeptr; return B;
}

28 삽입 연산: LR 유형 N을 A의 왼쪽 서브트리의 오른쪽 서브트리에 삽입 방법: LR 회전 N: 새로 삽입된 노드
A: N으로부터 가장 가까우면서 균형인수가 ±2가 된 조상 노드 방법: LR 회전 두 번의 회전 필요 RR 회전, LL 회전

29 삽입 연산: LR 유형 예제 8 2 9 1 7 5

30 삽입 연산: LR 유형 알고리즘 nodeptr rotateLR(A: nodeptr) { B: nodeptr; }

31 삽입 연산: RL 유형 N을 A의 오른쪽 서브트리의 왼쪽 서브트리에 삽입 방법: RL 회전 N: 새로 삽입된 노드
A: N으로부터 가장 가까우면서 균형인수가 ±2가 된 조상 노드 방법: RL 회전 두 번의 회전 필요 LL 회전, RR 회전

32 삽입 연산: RL 유형 예제 2 1 5 3 7 4

33 삽입 연산: RL 유형 알고리즘 nodeptr rotateRL(A: nodeptr) { B: nodeptr; }

34 예제 다음 리스트를 순차적으로 삽입하면서 AVL 트리를 구성하라. (7, 8, 9, 2, 1, 5, 3, 6, 4)

35 문제 다음 리스트를 순차적으로 삽입하면서 AVL 트리를 구성하라.
(60, 50, 20, 80, 90, 70, 55, 10, 40, 35)

36 AVL 트리: 알고리즘 트리 탐색 avlSearch(T, key) // 탐색된 노드를 반환 {
if (T = null) then return null; }

37 AVL 트리: 알고리즘 트리 탐색시 비교 회수 계산하여 반환 AvlCount(T, key) {
if (T = null) then return 0; }

38 AVL 트리: 알고리즘 노드 삽입 AvlAdd(T, key) {
if (T = null) then T = getNode(key); else { } return T;

39 AVL 트리: 알고리즘 노드 삽입 AvlAdd(T, key) {
if (T = null) then T = getNode(key); else { if (key < T.data) then { T.left <- avlAdd(T.left, key); T <- rebalance(T); } else if (key > T.data) then { T.right <- avlAdd(T.right, key); } else { error (“key 중복”); } return T;

40 AVL 트리: 알고리즘 rebalance rebalance(T) {
diff <- getHeightDiff(T); // T의 bf를 구함 }

41 AVL 트리: 알고리즘 rebalance rebalance(T) { diff <- getHeightDiff(T);
if (diff > 1 ) then { // LL or LR type if (getHeight(T.left) > 0) then return rotateLL(T); else return rotateLR(T); } else if (diff < -1 ) then // RR or RL type if (getHeight(T.right) > 0) then return rotateRR(T); return rotateRL(T); else return T; }

42 AVL 트리: 알고리즘 getHeightDiff(T) getHeight(T) getHeightDiff(T) { }