01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리
탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터
순차탐색 (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]!= key; i++) } ; if(i==(high+1)) return -1; // 탐색실패 else return i; // 탐색성공
자기구성순차탐색 (Self-Organizing Sequential Search) 자주사용되는항목을데이터집합의앞쪽에배치함으로써순차탐색의검색효율을끌어올리는방법 전진이동법 (Move To Front) 전위법 (Transpose) 빈도계수법 (Frequency Count)
전진이동법 (Move to front method) 어느항목이한번탐색되고나면, 그항목을데이터집합의가장앞 ( 링크드리스트에서는헤드 ) 에위치시키는방법 71 5 13 1 2 48 222 136 3 15 71 5 13 1 2 48 222 136 3 15 48 71 5 13 1 2 222 136 3 15
전위법 (Transpose method) 탐색된항목을바로이전항목과교환한다는것말고는기본적으로전진이동법과같은전략을취하는알고리즘 71 5 13 1 2 48 222 136 3 15 71 5 13 1 48 2 222 136 3 15 71 5 13 1 48 2 222 136 3 15 71 5 13 48 1 2 222 136 3 15
계수법 (Frequency count method) 데이터집합내의각요소들이탐색된횟수를별도의공간에저장해두고, 탐색된횟수가높은순으로데이터집합을재구성 계수결과를저장하는별도의공간을유지해야하고계수결과에따라데이터집합을재배치해야한다.
정렬된데이터집합에서사용할수있는 고속 탐색알고리즘 데이터집합의중앙에있는요소선택 중앙요소의값과찾고자하는목표값을비교 목표값이중앙요소의값보다작다면중앙을기준으로데이터집합의왼편에대 해새로검색을수행하고크다면오른편에대해이진탐색을새로이수행 찾고자하는값을찾을때까지 1 번 ~3 번과정을반복
배열의중앙에있는값을조사하여찾고자하는항목이왼쪽또는오른쪽부분배열에있는지를알아내어탐색의범위를반으로줄인다. ( 예 ) 10억명중에서이진탐색을이용하여특정한이름을탐색 이진탐색은단지 30번의비교 순차탐색에서는평균 5억번의비교 5 을탐색하는경우 영어사전 ⅹ 7과비교 1 3 5 6 7 9 11 20 30 5< 7이므로앞부분만을다시탐색 1 3 5 6 7 9 11 20 30 5를 3과비교 1 3 5 6 7 9 11 20 30 5> 3 이므로뒷부분만을다시탐색 1 3 5 6 7 9 11 20 30 5==5 이므로탐색성공 1 3 5 6 7 9 11 20 30
이진탐색예 1 7 11 12 14 23 67 139 672 871 67 1 7 11 12 14 23 67 139 672 871 2 67 1 7 11 12 14 23 67 139 672 871 67 1 7 11 12 14 23 67 139 672 871 67 1 7 11 12 14 23 67 139 672 871
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] 에서의탐색 ;
이진탐색의성능 탐색대상의범위 : ½ ¼ 1/16 Let n : 데이터집합의크기 x : 탐색반복횟수 1 = n x (1/2) x x = log 2 n 100 만개의데이터집합 : 최대 20 회 1000 만개의데이터집합 : 최대 23 회
이진탐색의구현 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;
C 표준라이브러리의이진탐색함수 bsearch() void *bsearch( const void *key, /* 찾고자하는목표값데이터의주소 */ const void *base, /* 데이터집합배열의주소 */ size_t num, /* 데이터요소의개수 */ size_t width, /* 한데이터요소의크기 */ int ( cdecl *compare)(const void *, const void *) /* 비교함수에대한포인터 */ );
각노드가다음규칙을따르는이진트리 왼쪽자식노드는부모보다작고, 오른쪽자식노드는부모보다크다. 23 11 139 1 14 67 871 이진탐색트리의예 23 82 11 139 73 1 14 58 78 13 20 11 68
이진탐색 (binary search) vs. 이진탐색트리 (binary search tree) 근본적으로같은원리에의한탐색구조 이진탐색은배열에저장된데이터를탐색 동적으로크기가변하는데이터집합탐색에는부적합 삽입과삭제가상당히힘들다. 이진탐색트리는연결리스트데이터에대한탐색 비교적빠른시간안에삽입과삭제를끝마칠수있는구조 삽입, 삭제가빈번히이루어진다면반드시이진탐색트리를사용하여야한다. 이진탐색트리에서의시간복잡도 균형트리 : O(logn) 불균형트리 : O(n), 순차탐색과동일
이진탐색트리의연산 노드탐색 노드삽입 노드삭제
이진탐색트리에서의이진탐색 23 23 11 139 11 139 > 67 1 14 67 871 1 14 67 871 23 < 67 23 11 139 11 139 1 14 67 871 1 14 67 871
이진탐색트리에서의노드삽입 23 23 11 139 11 139 1 67 1 14 67
이진탐색트리에서의노드삭제 #1 삭제할노드가잎노드인경우 23 23 11 139 11 139 1 14 67 1 67
이진탐색트리에서의노드삭제 #2 삭제할노드가잎노드가아닌경우 && 왼쪽 / 오른쪽중어느한쪽자식노드만갖고있는경우 23 삭제된노드의부모노드가삭제된노드의자식을가리키게합니다. 23 11 139 11 139 1 14 67 1 14 67
이진탐색트리에서의노드삭제 #3 삭제할노드가잎노드가아닌경우 && 양쪽자식노드를모두갖고있는경우 삭제 23 23 23 23 11 139 139 13 139 13 139 1 16 67 1 16 67 1 16 67 1 16 67 13 20 13 20 20 20 15 최소값노드 15 15 15
문제 : 순수이진탐색트리는다음과같은모습을가질수있게되며, 이때탐색효율은극도로떨어진다. 해결책 : 트리가균형잡힌모습으로자라도록하는알고리즘
레드블랙트리 : 모든노드가검은색또는붉은색 다음의규칙을가진다. 1. 모든노드는빨간색아니면검은색이다. 2. 루트노드는검은색이다. 3. 잎노드는검은색이다. 4. 빨간노드의자식들은모두검은색이다 ( 하지만검은색노드의자식이빨간색일필요는없다.). 5. 루트노드에서모든잎노드사이에있는검은색노드의수는모두동일하다.
레드블랙트리의예 4. 빨간노드의자식들은모두검은색이다 2. 루트노드는검은색이다. NIL NIL NIL NIL NIL NIL 5. 루트노드에서모든잎노드사이에있는검은색노드의수는모두동일하다. NIL NIL 3. 잎노드는모두검은색이다.
레드블랙트리의구현예
노드색상전환 (Color Flipping) 노드의색상을바꾸는연산 노드회전 (Rotation) 8 우회전 5 9 3 5 8 3 6 좌회전 6 9 우회전을할때에는왼쪽자식노드의오른쪽자식노드를부모노드의왼쪽자식으로연결한다. 좌회전을할때에는오른쪽자식노드의왼쪽자식노드를부모노드의오른쪽자식으로연결한다.
레드블랙트리연산 노드탐색연산 노드삽입연산 노드삭제연산 노드탐색연산 이진탐색트리에서의노드탐색연산과동일 이진탐색트리에대한중위순회 ( in-order traversal)
노드삽입연산 레드블랙트리의노드삽입연산 1 이진탐색트리의노드삽입연산을수행한다. 2 새노드를빨간색으로칠하고양쪽자식에 NIL 을연결한다. 3 무너진레드블랙트리규칙을고치기위해트리를재구성한다. 삽입연산후에어긋나는레드블랙트리규칙 루트노드는검은색이어야한다. 빨간색노드의자식노드들은검은색이어야한다.
노드삽입연산의후처리 (1) 빨간색노드의자식은검은색이어야한다 는규칙을복원 가정 : 부모노드가빨간색이고할아버지노드의왼쪽자식인경우 다음의 3 가지경우로나누어해결 삼촌노드도빨간색인경우 삼촌노드는검은색이고, 삽입노드가부모노드의오른쪽자식인경우 삼촌노드는검은색이고, 삽입노드가부모노드의왼쪽자식인경우
노드삽입연산의후처리 (2) 삼촌노드도빨간색인경우
노드삽입연산의후처리 (3) 삼촌노드는검은색이고, 삽입노드가부모노드의오른쪽자식인경우 세번째경우로전환
노드삽입연산의후처리 (4) 삼촌노드는검은색이고, 삽입노드가부모노드의왼쪽자식인경우
노드삭제연산 레드블랙트리의노드삭제연산 1 이진탐색트리의노드삭제연산을수행한다. 2 무너진레드블랙트리규칙을고치기위해트리를재구성한다. 삭제노드의색깔이빨간색인경우 레드블랙트리규칙이그대로보전된다 별도의후처리가필요없음 삭제노드의색깔이검은색인경우 다음의레드블랙트리규칙이무너질수있다. 1 빨간색노드의자식은검은색이어야한다. 2 루트노드에서잎노드까지의모든경로에서검은색노드수는동일하여야한다.
노드삭제연산의후처리 (1) 빨간색노드의자식은검은색이어야한다 규칙복원 삭제노드의자식은삭제노드의색상속성을상속한다
노드삭제연산의후처리 (2) 삭제노드와삭제후이동하는노드모두검은색인경우 5 번위반을 1 번위반으로전환하여문제를축소
노드삭제연산의후처리 (3) (1) 이중흑색노드의형제노드가빨간색인경우
노드삭제연산의후처리 (4) (2) 이중흑색노드의형제노드가검은색이고, 형제노드의양쪽자식이모두검은색인경우
노드삭제연산의후처리 (5) (3) 이중흑색노드의형제노드가검은색이고, 형제노드의왼쪽자식은빨간색이고오른쪽자식은검은색인경우 넷번째경우로전환
노드삭제연산의후처리 (6) (4) 이중흑색노드의형제노드가검은색이고, 형제노드의오른쪽자식은빨간색인경우
Adelson-Velskii와 Landis에의해 1962년에제안된트리각노드에서왼쪽서브트리의높이와오른쪽서브트리의높이차이가 1 이하인이진탐색트리 트리가비균형상태로되면스스로노드들을재배치하여균형상태로만든다. AVL 트리는균형트리가항상보장되기때문에탐색이 O(logn) 시간안에끝나게된다. 균형인수 (balance factor)=( 왼쪽서브트리의높이 - 오른쪽서브트리의높이 ) 모든노드의균형인수가 ±1 이하이면 AVL 트리이다.
탐색연산 : 이진탐색트리와동일균형을이룬이진탐색트리에서균형상태가깨지는것은삽입연산과삭제연산시이다. 삽입연산시에는삽입되는위치에서루트까지의경로에있는조상노드들의균형인수에영향을줄수있다. 새로운노드의삽입후에불균형상태로변한가장가까운조상노드, 즉균형인수가 ±2가된가장가까운조상노드의서브트리들에대하여다시균형을잡아야한다.
균형트리로만드는방법 : 회전 (rotation) AVL 트리에서균형이깨지는경우에는다음의 4 가지의경우가있다. 새로삽입된노드 N 로부터가장가까우면서균형인수가가된조상노드를 A 라고하자. LL 타입 : N 이 A 의왼쪽서브트리의왼쪽서브트리에삽입된다. LR 타입 : N 이 A 의왼쪽서브트리의오른쪽서브트리에삽입된다. RR 타입 : N 이 A 의오른쪽서브트리의오른쪽서브트리에삽입된다. RL 타입 : N 이 A 의오른쪽서브트리의왼쪽서브트리에삽입된다.
LL 회전 :A 부터 N 까지의경로상의노드들을오른쪽으로회전시킨다. LR 회전 : A 부터 N 까지의경로상의노드들을왼쪽 - 오른쪽으로회전시킨다. RR 회전 : A 부터 N 까지의경로상의노드들을왼쪽으로회전시킨다. RL 회전 : A 부터 N 까지의경로상의노드들을오른쪽 - 왼쪽으로회전시킨다.