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

Presentation on theme: "CHAP 12: 탐색 순천향대학교 컴퓨터학부 2016. 11. 24 하 상 호."— 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 ⅹ 이진탐색 영어사전 정렬된 배열의 탐색에는 이진 탐색(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

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

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

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

9 색인순차탐색 알고리즘 인덱스 테이블 구조체 typedef struct { int key; int index; } itable
Integer searchIndex(a, itab: array of itable, key, n, m: integer) // n: 주자료테이블 크기, m: 인덱스 테이블 크기 I, low, high: integer; if (key < a[0] or key > a[n-1]) // key가 리스트 범위에 속하지 않으면 then return -1; // key가 속한 인덱스 테이블 구간을 결정해서, 그 구간내 순차 탐색 수행 // 결정된 구간의 범위 결정: low & high // 결정된 구간 범위에서 순차 탐색 return seqSearch(a, key, low, high); end searchIndex 알고리즘 22

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

34 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;

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

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

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