1장. 리스트

Size: px

Start display at page:

Download "1장. 리스트"

정헉 어금
5 years ago
Views:

1 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 05. AVL 트리 06. B- 트리

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

$seq_search(int key, int low, int high) { int i;$

3 순차탐색 (sequential search) 탐색방법중에서가장간단하고직접적인탐색방법 정렬되지않은배열의항목들을처음부터마지막까지하나씩검사하여원하는항목을찾아가는방법 int seq_search(int key, int low, int high) { int i; for(i=low; i<=high; i++) if(list[i]==key) return i; // 탐색성공 return -1; // 탐색실패 }

$int seq_search2(int key, int low, int high) { int i;$ list[high+1] = key; // 키값을찾으면종료 for(i=low; list[i]!

4 순차탐색에서비교횟수를줄이기위해리스트의끝에찾고자하는키값을저장하고반복문의탈출조건을키값을찾을때까지로설정 int seq_search2(int key, int low, int high) { int i; list[high+1] = key; // 키값을찾으면종료 for(i=low; list[i]!= key; i++) ; if(i==(high+1)) return -1; // 탐색실패 else return i; // 탐색성공 }

5 자기구성순차탐색 (Self-Organizing Sequential Search) 자주사용되는항목을데이터집합의앞쪽에배치함으로써순차탐색의검색효율을끌어올리는방법 전진이동법 (Move To Front) 전위법 (Transpose) 빈도계수법 (Frequency Count)

6 전진이동법 (Move to front method) 어느항목이한번탐색되고나면, 그항목을데이터집합의가장앞 ( 링크드리스트에서는헤드 ) 에위치시키는방법

7 전위법 (Transpose method) 탐색된항목을바로이전항목과교환한다는것말고는기본적으로전진이동법과같은전략을취하는알고리즘

8 계수법 (Frequency count method) 데이터집합내의각요소들이탐색된횟수를별도의공간에저장해두고, 탐색된횟수가높은순으로데이터집합을재구성 계수결과를저장하는별도의공간을유지해야하고계수결과에따라데이터집합을재배치해야한다.

9 정렬된데이터집합에서사용할수있는 고속 탐색알고리즘 데이터집합의중앙에있는요소선택 중앙요소의값과찾고자하는목표값을비교 목표값이중앙요소의값보다작다면중앙을기준으로데이터집합의왼편에대 해새로검색을수행하고크다면오른편에대해이진탐색을새로이수행 찾고자하는값을찾을때까지 1 번 ~3 번과정을반복

10 배열의중앙에있는값을조사하여찾고자하는항목이왼쪽또는오른쪽부분배열에있는지를알아내어탐색의범위를반으로줄인다. ( 예 ) 10억명중에서이진탐색을이용하여특정한이름을탐색 이진탐색은단지 30번의비교 순차탐색에서는평균 5억번의비교 5 을탐색하는경우 영어사전 ⅹ 7과비교 < 7이므로앞부분만을다시탐색 를 3과비교 > 3 이므로뒷부분만을다시탐색 ==5 이므로탐색성공

11 이진탐색예

12 search_binary(list, low, high) middle low 에서 high 사이의중간위치 if( 탐색값 list[middle] ) return TRUE; else if ( 탐색값 < list[middle] ) return list[0] 부터 list[middle-1] 에서의탐색 ; else if ( 탐색값 > list[middle] ) return list[middle+1] 부터 list[high] 에서의탐색 ;

13 이진탐색의성능 탐색대상의범위 : ½ ¼ 1/16 Let n : 데이터집합의크기 x : 탐색반복횟수 1 = n x (1/2) x x = log 2 n 100 만개의데이터집합 : 최대 20 회 1000 만개의데이터집합 : 최대 23 회

14 이진탐색의구현 ElementType BinarySearch(ElementType DataSet[], int Size, ElementType Target) { int Left, Right, Mid; Left = 0; Right = Size - 1; while ( Left <= Right ) { Mid = (Left + Right) / 2; } if ( Target == DataSet[Mid] ) return DataSet[Mid]; else if ( Target > DataSet[Mid] ) Left = Mid + 1; else Right = Mid - 1; } return NULL;

15 C 표준라이브러리의이진탐색함수 bsearch() void *bsearch( const void *key, /* 찾고자하는목표값데이터의주소 */ const void *base, /* 데이터집합배열의주소 */ size_t num, /* 데이터요소의개수 */ size_t width, /* 한데이터요소의크기 */ int ( cdecl *compare)(const void *, const void *) /* 비교함수에대한포인터 */ );

16 각노드가다음규칙을따르는이진트리 왼쪽자식노드는부모보다작고, 오른쪽자식노드는부모보다크다 이진탐색트리의예

17 이진탐색 (binary search) vs. 이진탐색트리 (binary search tree) 근본적으로같은원리에의한탐색구조 이진탐색은배열에저장된데이터를탐색 동적으로크기가변하는데이터집합탐색에는부적합 삽입과삭제가상당히힘들다. 이진탐색트리는연결리스트데이터에대한탐색 비교적빠른시간안에삽입과삭제를끝마칠수있는구조 삽입, 삭제가빈번히이루어진다면반드시이진탐색트리를사용하여야한다. 이진탐색트리에서의시간복잡도 균형트리 : O(logn) 불균형트리 : O(n), 순차탐색과동일

18 각노드는하나씩의키값을갖는다. 각노드의키값은다르다. 최상위레벨에루트노드가있고, 각노드는최대두개의자식을갖는다. 임의의노드의키값은자신의왼쪽자식노드의키값보다크고, 오른쪽자식의키값보다작다.

19 BST 의예 (a) (b)

20 서브트리의예 r (a) (b) 노드 r 의왼쪽서브트리 (c) 노드 r 의오른쪽서브트리

21 이진탐색트리의연산 노드탐색 노드삽입 노드삭제

22 이진탐색트리에서의이진탐색 > <

23 treesearch(t, x) { if (t=nil or key[t]=x) then return t; if (x < key[t]) then return treesearch(left[t], x); else return treesearch(right[t], x); } t: 트리의루트노드 x: 검색하고자하는키

24 검색에서재귀적관점 t left[t] right[t]

25 이진탐색트리에서의노드삽입

26 treeinsert(t, x) { if (t=nil) then { key[r] x; return r; } r : 새노드 } if (x < key(t)) then {left[t] treeinsert(left[t], x); return t;} else {right[t] treeinsert(right[t], x); return t;} t: 트리의루트노드 x: 삽입하고자하는키

27 삽입의예 (a) (b) (c) (d) (e) (f)

28 이진탐색트리에서의노드삭제 #1 삭제할노드가잎노드인경우

29 이진탐색트리에서의노드삭제 #2 삭제할노드가잎노드가아닌경우 && 왼쪽 / 오른쪽중어느한쪽자식노드만갖고있는경우 23 삭제된노드의부모노드가삭제된노드의자식을가리키게합니다

30 이진탐색트리에서의노드삭제 #3 삭제할노드가잎노드가아닌경우 && 양쪽자식노드를모두갖고있는경우 삭제 최소값노드

31 3 가지경우에따라다르게처리한다 Case 1 : r 이리프노드인경우 Case 2 : r 의자식노드가하나인경우 Case 3 : r 의자식노드가두개인경우 t: 트리의루트노드 r: 삭제하고자하는노드

32 t: 트리의루트노드 Sketch-TreeDelete(t, r) r: 삭제하고자하는노드 { if (r이리프노드 ) then // Case 1 그냥 r을버린다 ; else if (r의자식이하나만있음 ) then // Case 2 r의부모가 r의자식을직접가리키도록한다 ; else // Case 3 r의오른쪽서브트리의최소원소노드 s를삭제하고, s를 r 자리에놓는다 ; }

treedelete(t, r, p) { if (r = t) then root deletenode(t); else if (r = left[p]) then left[p] deletenode(r); r이루트노드인경우 r이루트가아닌경우 r이 p의왼쪽자식 else right[p] deletenode(r); r이 p의오른쪽자식 } deletenode(r) { if

33 treedelete(t, r, p) { if (r = t) then root deletenode(t); else if (r = left[p]) then left[p] deletenode(r); r이루트노드인경우 r이루트가아닌경우 r이 p의왼쪽자식 else right[p] deletenode(r); r이 p의오른쪽자식 } deletenode(r) { if (left[r] = right[r] = NIL) then return NIL; Case 1 else if (left[r] = NIL and right[r] NIL) then return right[r]; Case 2-1 else if (left[r] NIL and right[r] = NIL) then return left[r]; Case 2-2 else { Case 3 s right[r]; while (left[s] NIL) {parent s; s left[s];} key[r] key[s]; if (s = right[r]) then right[r] right[s]; else left[parent] right[s]; return r; } } t: 트리의루트노드 r: 삭제하고자하는노드 p: r 의부모노드

34 삭제의예 : Case r (a) r 의자식이없음 (b) 단순히 r 을제거한다

35 삭제의예 : Case r (a) r 의자식이하나뿐임 (b) r 을제거 (c) r 자리에 r 의자식을놓는다

36 삭제의예 : Case r s s (a) r 의직후원소 s 를찾는다 (b) r 을없앤다

37 s s (c) s 를 r 자리로옮긴다 (d) s 가있던자리에 s 의자식을놓는다

38 문제 : 순수이진탐색트리는다음과같은모습을가질수있게되며, 이때탐색효율은극도로떨어진다. 해결책 : 트리가균형잡힌모습으로자라도록하는알고리즘

39 레드블랙트리 : 모든노드가검은색또는붉은색 다음의규칙을가진다. 1. 모든노드는빨간색아니면검은색이다. 2. 루트노드는검은색이다. 3. 잎노드는검은색이다. 4. 빨간노드의자식들은모두검은색이다 ( 하지만검은색노드의자식이빨간색일필요는없다.). 5. 루트노드에서모든잎노드사이에있는검은색노드의수는모두동일하다.

40 BST 의모든노드에블랙또는레드의색을칠하되다음의레드블랙특성을만족해야한다 1 모든노드는색깔 ( 레드, 블랙 ) 을가진다 2 루트는블랙이다 3 모든리프는블랙이다 4 노드가레드이면그노드의자식은반드시블랙이다 5 루트노드에서임의의리프노드에이르는경로에서만나는블랙노드의수는모두같다 여기서, 리프노드는일반적인의미의리프노드와다르다. 모든 NIL 포인터가 NIL 이라는리프노드를가리킨다고가정한다.

41 레드블랙트리의예 4. 빨간노드의자식들은모두검은색이다 2. 루트노드는검은색이다. NIL NIL NIL NIL NIL NIL 5. 루트노드에서모든잎노드사이에있는검은색노드의수는모두동일하다. NIL NIL 3. 잎노드는모두검은색이다.

42 레드블랙트리의구현예

43 BST 를 RB Tree 로만든예 NIL NIL NIL NIL NIL NIL NIL NIL NIL (a) BST 의한예 (b) (a) 를 RB Tree 로만든예 NIL (c) 실제구현시의 NIL 노드처리방법

44 기본연산 노드색상전환 (Color Flipping) 노드의색상을바꾸는연산 노드회전 (Rotation) 8 우회전 좌회전 우회전을할때에는왼쪽자식노드의오른쪽자식노드를부모노드의왼쪽자식으로연결한다. 6 9 좌회전을할때에는오른쪽자식노드의왼쪽자식노드를부모노드의오른쪽자식으로연결한다.

45 레드블랙트리연산 노드탐색연산 노드삽입연산 노드삭제연산 노드탐색연산 이진탐색트리에서의노드탐색연산과동일 이진탐색트리에대한중위순회 ( in-order traversal)

46 노드삽입연산 레드블랙트리의노드삽입연산 1 이진탐색트리의노드삽입연산을수행한다. 2 새노드를빨간색으로칠하고양쪽자식에 NIL 을연결한다. 3 무너진레드블랙트리규칙을고치기위해트리를재구성한다. 삽입연산후에어긋나는레드블랙트리규칙 루트노드는검은색이어야한다. 빨간색노드의자식노드들은검은색이어야한다.

47 노드삽입연산의후처리 (1) 빨간색노드의자식은검은색이어야한다 는규칙을복원 가정 : 부모노드가빨간색이고할아버지노드의왼쪽자식인경우 다음의 3 가지경우로나누어해결 삼촌노드도빨간색인경우 삼촌노드는검은색이고, 삽입노드가부모노드의오른쪽자식인경우 삼촌노드는검은색이고, 삽입노드가부모노드의왼쪽자식인경우

48 노드삽입연산의후처리 (2) 삼촌노드도빨간색인경우

49 노드삽입연산의후처리 (3) 삼촌노드는검은색이고, 삽입노드가부모노드의오른쪽자식인경우 세번째경우로전환

50 노드삽입연산의후처리 (4) 삼촌노드는검은색이고, 삽입노드가부모노드의왼쪽자식인경우

51 RB Tree 에서의삽입 BST 에서의삽입과같다. 다만삽입후삽입된노드를레드로칠하고자식링크는 NIL 로연결한다 ( 이노드를 x 라하자 ). 5 특성이유지됨을보장함 만일 x 의부모노드 p 의색상이 블랙이면아무문제없다. 레드이면레드블랙특성 4 가깨진다. p p x x 그러므로 p 가레드인경우만고려하면된다

52 RB Tree 에서의삽입 주어진조건 : p is red P 2 와 x의형제노드는반드시블랙이다 s의색상에따라두가지로나눈다 Case 1: s가레드 Case 2: s가블랙 p 2 p? s x

53 Case 1: s 가레드 p 와 s 의색상과 p 2 의색상을바꾼다 : 색상이바뀐노드 Case 1 p 2 p2 p s p s x x p 2 에서동일한문제가발생할수있다 : recursive problem!

54 Case 2-1: s 가블랙이고, x 가 p 의오른쪽자식 p 을기준으로 rotate-left Case 2-2 문제로전환 Case 2-1 p 2 Case 2-2로! p 2 p s x s y x p y

55 Case 2-2: s 가블랙이고, x 가 p 의왼쪽자식 p 2 와 p 의색상을바꾸고, p 2 기준으로 rotate-right : 색상이바뀐노드 Case 2-2 p 2 p p s x p 2 x y y s 삽입완료!

56 노드삭제연산 레드블랙트리의노드삭제연산 1 이진탐색트리의노드삭제연산을수행한다. 2 무너진레드블랙트리규칙을고치기위해트리를재구성한다. 삭제노드의색깔이빨간색인경우 레드블랙트리규칙이그대로보전된다 별도의후처리가필요없음 삭제노드의색깔이검은색인경우 다음의레드블랙트리규칙이무너질수있다. 1 빨간색노드의자식은검은색이어야한다. 2 루트노드에서잎노드까지의모든경로에서검은색노드수는동일하여야한다.

57 노드삭제연산의후처리 (1) 빨간색노드의자식은검은색이어야한다 규칙복원 삭제노드의자식은삭제노드의색상속성을상속한다

58 노드삭제연산의후처리 (2) 삭제노드와삭제후이동하는노드모두검은색인경우 5 번위반을 1 번위반으로전환하여문제를축소

59 노드삭제연산의후처리 (3) (1) 이중흑색노드의형제노드가빨간색인경우

60 노드삭제연산의후처리 (4) (2) 이중흑색노드의형제노드가검은색이고, 형제노드의양쪽자식이모두검은색인경우

61 노드삭제연산의후처리 (5) (3) 이중흑색노드의형제노드가검은색이고, 형제노드의왼쪽자식은빨간색이고오른쪽자식은검은색인경우 넷번째경우로전환

62 노드삭제연산의후처리 (6) (4) 이중흑색노드의형제노드가검은색이고, 형제노드의오른쪽자식은빨간색인경우

63 RB Tree 에서의삭제 삭제노드의자식이없거나 1 개만을가진노드로제한해도된다 텍스트의 p.243 의중간문단참조 삭제노드를 m 이라하자 삭제노드가레드이면아무문제없다 삭제노드가블랙이라도 ( 유일한 ) 자식이레드이면문제없다 m x m x x x

64 x 옆의 -1 은루트에서 x 를통해리프에이르는경로에서블랙노드의수가하나모자람을의미한다. p p p? m x x -1 x -1 l? s?? r m 삭제후문제발생 ( 레드블랙특성 5 위반 ) x 의주변상황에따라처리방법이달라진다

65 삭제연산 : 경우의수나누기 p is red p is black x -1 x -1 Case 1 Case 2

66 p Case 1-1 x -1 l s r Case 1-2 x -1 p l s r Case 1-3 x -1 p l s r Case 2-1 x -1 p l s r Case 2-2 x -1 p l s r Case 2-3 x -1 p l s r p Case 2-4 x -1 l s r

67 p Case 1-1 x -1 l s r Case *-2 p x -1 l s r Case *-3 x -1 p l s r Case 2-1 p Case 2-4 p x -1 l s r x -1 l s r 최종적으로 5 가지경우로나뉜다

68 삭제연산 : 각경우에따른처리 p 와 s 의색상을바꾼다 Case 1-1 x -1 p l s r x p l s r 삭제완료!

69 (1) p 를기준으로 rotate-left 한후에 p 와 s 의색상을바꾼다 (2) r 의색상을블랙으로바꾼다 Case *-2 x -1 p s r x p s r 삭제완료! Case *-3 x -1 p l s r Case *-2 로 x -1 p 1 l s 를기준으로 rotate- right 하여 case *-2 로전환 s r 1 2 2

70 s 의색상을레드로바꾼다 p 에서동일한문제가발생 Recursive problem - 재귀적으로처리 Case 2-1 x -1 p l s r x p l -1 s r Case 2-4 x -1 p l s Case 1-1, Case 1-2, Case 1-3 중의하나로 p r x -1 l s r p 를기준으로 rotate-left 한후에 p 와 s 의색상을바꾼다 Case 1 의문제로전환하여처리

71 k.html black.html

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

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

74 삽입연산시에는삽입되는위치에서루트까지의경로에있는조상노드들의균형인수에영향을줄수있다. 새로운노드의삽입후에불균형상태로변한가장가까운조상노드, 즉균형인수가 ±2가된가장가까운조상노드의서브트리들에대하여다시균형을잡아야한다.

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

76 LL 회전 :A 부터 N 까지의경로상의노드들을오른쪽으로회전시킨다. LR 회전 : A 부터 N 까지의경로상의노드들을왼쪽 - 오른쪽으로회전시킨다. RR 회전 : A 부터 N 까지의경로상의노드들을왼쪽으로회전시킨다. RL 회전 : A 부터 N 까지의경로상의노드들을오른쪽 - 왼쪽으로회전시킨다.

82 외부검색트리 검색트리가방대하여트리데이터가디스크에있는상태에서검색연산을수행 CPU 효율성보다디스크접근회수가알고리즘성능을좌우 디스크의접근단위는블록 ( 페이지 ) 디스크에한번접근하는시간은수십만명령어의처리시간과동일 트리의높이를최소화하는것이유리다진검색트리 하나의노드가 2개이상의키를가짐 3개이상의서브트리를가짐 다진분기는트리의높이를축소 B-트리는다진검색트리가균형을유지하도록하여최악의경우디스크접근횟수를줄인것

83 다진검색트리 key 0 key 1 key 2 key k-1 T 0 T 1 T 2 T 3 T k key i-1 < T i < key i

84 B-Tree B-Tree 는균형잡힌다진검색트리로다음의성질을만족한다 루트를제외한모든노드는 k/2 ~ k 개의키를갖는다 모든리프노드는같은깊이를가진다

85 B- 트리의노드구조 부모노드의페이지 하나의노드가가질수있는키의개수? <key 0, p 0 > <key 1, p 1 > <key k-1, p k-1 >

86 B- 트리를통해 Record 에접근하는과정 <key 0, p 0 > <key i, p i > 키 key i 를가진 record 페이지 p i

87 B-Tree 에서의검색연산 이진탐색트리에서의검색연산과유사 이진탐색트리 : 1. 각노드가하나의키를가짐 2. 검색키와노드의키를비교 : 검색키가크면오른쪽서브트리검색 검색키가작으면왼쪽서브트리검색 B-tree: 1. 각노드가최대 k 개의의키를가짐 2. 검색키와노드의키를비교 : key i-1 <x<key i 인두키를찾아분기할서브트리를결정

88 B-Tree 에서의삽입연산 BTreeInsert(t, x) { x 를삽입할리프노드 r 을찾는다 ; x 를 r 에삽입한다 ; if (r 에오버플로우발생 ) then clearoverflow(r); } clearoverflow(r) { } t : 트리의루트노드 x : 삽입하고자하는키 if (r 의형제노드중여유가있는노드가있음 ) then {r 의남는키를넘긴다 }; else { r 을둘로분할하고가운데키를부모노드로넘긴다 ; if ( 부모노드 p 에오버플로우발생 ) then clearoverflow(p); }

89 B-Tree 에서삽입의예 (a) , 31 삽입 (b) 삽입

90 (c) 오버플로우! 삽입

91 (d) 39 삽입 오버플로우! , 35, 36 삽입 분할!

92 (e) 23, 35, 36 삽입 삽입

93 (f) 삽입 오버플로우! 오버플로우! 분할! 분할!

94 B-Tree 에서의삭제연산 BTreeDelete(t, x, v) t : 트리의루트노드 { x : 삭제하고자하는키 if (v가리프노드아님 ) then { v : x를갖고있는노드 x의직후원소 y를가진리프노드를찾는다 ; x와 y를맞바꾼다 ; } 리프노드에서 x를제거하고이리프노드를 r이라한다 ; if (r에서언더플로우발생 ) then clearunderflow(r); } clearunderflow(r) { if ( r의형제노드중키를하나내놓을수있는여분을가진노드가있음 ) then { r이키를넘겨받는다 ;} else { r의형제노드와 r을합병한다 ; if ( 부모노드 p에언더플로우발생 ) then clearunderflow(p); } }

95 (a) B-Tree 에서삭제의예 삭제 (b) 삭제

96 (c) 4, 5 교환 제거 재분배 언더플로우! 삭제

97 (d) 언더플로우! 언더플로우! 3 15 병합! 병합!

Microsoft PowerPoint - 6장 탐색.pptx

Microsoft PowerPoint - 6장 탐색.pptx 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential