쉽게 배우는 알고리즘 5장. 검색트리 http://academy.hanb.co.kr

5장. 검색 트리 나는 보다 응용력 있는 유형의 수학이라는 이유 때문에 컴퓨터 과학을 하고 싶었다. -로버트 타잔

학습목표 Search에서 Record와 Key의 역할을 구분한다. Binary Search Tree(BST)에서의 검색·삽입·삭제 작업의 원리를 이해한다. BST의 균형이 작업의 효율성에 미치는 영향을 이해하고, Red-Black Tree의 삽입·삭제 작업의 원리를 이해한다. B-Tree의 도입 동기를 이해하고 검색·삽입·삭제 작업의 원리를 이해한다. Search Tree 관련 작업의 점근적 수행시간을 이해한다.

Record, Key, Search Tree Record Field Search Key / Key Search Tree 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 e.g., 사람의 레코드 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰 번호, 최종 학력, 연 소득, 가족 상황 등의 정보 포함 Field 레코드에서 각각의 정보를 나타내는 부분 e.g., 위 사람의 레코드에서 각각의 정보를 나타내는 부분 Search Key / Key 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다 Search Tree 각 Node가 규칙에 맞도록 하나씩의 키를 갖고 있다 이를 통해 해당 레코드가 저장된 위치를 알 수 있다

Record, Key, Search Tree (Continued…) Field Name Char [10] Char [8] Char [20] Char [14] Char [25] Char [13] Char [13] ID PASSWD NAME JUMIN_NO ADDR HOME_TEL MOBILE_NO 2011001 ******** Kim 880204-1232834 Seoul 02-1234-5678 010-1234-5678 2011002 Lee 890405-1234567 Wonju 033-324-4567 010-4321-0987 2011003 Park 870608-1546743 Chunchun 033-245-6789 010-3456-8796 2011004 Jung 881011-1615162 Daejun 041-346-4567 010-5609-1010 2011005 Song 901209-1813456 Inchon 031-678-0908 010-3950-0678 Field Key

Search Algorithms 1. 순차 검색(Sequential Search) 2. 이진 검색(Binary Search) 3. 이진 나무 검색(Binary Tree Search) / 이진 검색 트리(Binary Search Tree) 4. 균형 잡는 나무 검색(Balanced Search Tree) 4-1. AVL Tree 4-2. 2-3 Tree 4-3. 2-3-4 Tree 4-4. Red-Black Tree 5. 해시(Hash) 6. 기수 검색(Radix Search) 6-1. Binary Radix Tree Search 6-2. Binary Radix Trie Search 7. 외부 검색(External Search) 7-1. ISAM(Indexed Sequential Access Method) 7-2. 연장 해시(Extendible Hashing 또는 Dynamic Hashing) 7-3. B-Tree

Sequential Search 레코드를 하나씩 순차적으로 찾는 방법 비 정렬 자료의 검색에 적절 배열로 표현된 데이터에 대한 순차 검색 알고리즘 struct rec { int key; … } A[N+1]; int seqsearch1 (int k) { // 입력 : k – 검색 Key // 출력 : i – k의 존재 위치 int i = 1; while ( (i < N+1) && (A[i].key != k) ) i++; return ( i ); } 레코드를 하나씩 순차적으로 찾는 방법 비 정렬 자료의 검색에 적절 n개의 비 정렬 자료의 순차 검색은 검색에 실패할 경우 n+1번의 비교, 검색에 성공할 경우에는 평균적으로 (n+1)/2번의 비교 요구

Sequential Search (Continued…) 포인터로 표현된 데이터에 대한 순차 검색 알고리즘 struct node { int key; struct node *link; }; struct node *seqsearch2 (int k) // 입력 : k – 검색 Key // 출력 : t – Node 포인트 { struct node *t; t = head->link; while ( (t != NULL) && (t->key != k) ) t = t->link; return (t); }

Binary Search 정렬된 레코드의 선형 리스트에 분할정복을 적용한 방법 검색 범위의 중간 위치를 비교해 나가는 방법 int bisearch (int k) { // 입력 : k – 검색 Key // 출력 : k의 존재 위치 int low, high, mid; low = 1, high = n; while (low <= high) { mid = (low + high)/2; if (k < A[mid].key) high = mid –1; if (k == A[mid].key) return (mid); if (k > A[mid].key) low = mid + 1; } return (0); 정렬된 레코드의 선형 리스트에 분할정복을 적용한 방법 검색 범위의 중간 위치를 비교해 나가는 방법 최악의 시간 복잡도는 O(log n) 삽입이나 삭제 시 최악의 경우 n번의 자료 이동이 필요하며 평균적으로도 약 n/2번의 이동을 요구 삽입이나 삭제가 빈번한 경우 부적절

Binary Search Tree (BST) 각 Node는 하나씩의 Key 값을 갖는다. 각 Node의 Key 값은 다르다. 최상위 레벨에 Root Node가 있고, 각 Node는 최대 두 개의 자식을 갖는다. 임의의 Node의 Key 값은 자신의 왼쪽 자식 Node의 Key 값보다 크고, 오른쪽 자식의 Key 키 값보다 작다.

BST의 예 40 30 30 45 20 40 20 35 10 25 35 45 10 25 (a) (b)

Subtree의 예 r 30 20 40 10 25 35 45 (a) 20 40 10 25 35 45 (b) Node r의 왼쪽 Subtree (c) Node r의 오른쪽 Subtree

BST에서의 검색 x: 검색하고자 하는 Key t: Tree의 Root Node 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 left[t] right[t]

BST에서의 삽입 x: 삽입하고자 하는 Key t: Tree의 Root Node treeInsert(t, x) {         if (t=NIL) then {                 key[r] ← x;                             ▷ r : New Node                 return r;                 }         if (x < key(t))                 then {left[t] ← treeInsert(left[t], x); return t;}                  else {right[t] ← treeInsert(right[t], x); return t;} }

삽입의 예 30 30 30 30 20 20 20 40 25 25 (a) (b) (c) (d) 30 30 20 40 20 40 10 25 10 25 35 (e) (f)

BST에서의 삭제 3가지 경우에 따라 다르게 처리한다 Case 1 : r이 Leaf Node인 경우 t: Tree의 Root Node r: 삭제하고자 하는 Node 3가지 경우에 따라 다르게 처리한다 Case 1 : r이 Leaf Node인 경우 Case 2 : r의 자식 Node가 하나인 경우 Case 3 : r의 자식 Node가 두 개인 경우

BST에서의 삭제 r: 삭제하고자 하는 Node Sketch-TreeDelete(t, r) { t: Tree의 Root Node r: 삭제하고자 하는 Node Sketch-TreeDelete(t, r) {         if (r이 Leaf Node) then                   ▷ Case 1                 그냥 r을 버린다;         else if (r의 자식이 하나만 있음) then     ▷ Case 2                 r의 부모가 r의 자식을 직접 가리키도록 한다;         else                                   ▷ Case 3                 r의 오른쪽 Subtree의 최소 원소 Node s를 삭제하고,                 s를 r 자리에 놓는다; }

BST에서의 삭제 t: Tree의 Root Node r: 삭제하고자 하는 Node p: r의 Parent Node treeDelete(t, r, p) { if (r = t) then root ← deleteNode(t);     ▷ r이 Root Node인 경우     else if (r = left[p]) ▷ r이 Root가 아닌 경우 then left[p] ← deleteNode(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: Tree의 Root Node r: 삭제하고자 하는 Node p: r의 Parent Node

삭제의 예: Case 1 r (a) r의 자식이 없음 (b) 단순히 r을 제거한다 55 28 8 60 15 90 48 30 18 38 3 50 r (a) r의 자식이 없음 (b) 단순히 r을 제거한다 36 32 33

삭제의 예: Case 2 r (c) r 자리에 r의 자식을 놓는다 (a) r의 자식이 하나뿐임 (b) r을 제거 55 55 15 60 15 60 15 60 8 28 90 8 28 90 8 28 90 r 3 18 30 3 18 3 18 48 48 48 38 50 38 50 38 50 33 33 33 32 36 32 36 32 36 (a) r의 자식이 하나뿐임 (b) r을 제거 (c) r 자리에 r의 자식을 놓는다

삭제의 예: Case 3 r s (b) r을 없앤다 (a) r의 직후원소 s를 찾는다 55 28 8 60 15 90 48 30 45 18 41 38 3 50 r s (a) r의 직후원소 s를 찾는다 36 32 33 (b) r을 없앤다

s (c) s를 r자리로 옮긴다 (d) s가 있던 자리에 s의 자식을 놓는다 55 30 8 60 15 90 48 45 18 41 3 50 s (d) s가 있던 자리에 s의 자식을 놓는다 38 36 32 33 (c) s를 r자리로 옮긴다

Red-Black Tree (RB Tree) BST의 모든 Node에 Black 또는 Red의 색을 칠하되 다음의 Red Black 특성을 만족해야 한다 모든 Node는 Red 혹은 Black이다. / Every node is either red or black Root는 Black이다./ The root is black 모든 Leaf는 Black이다. / Every leaf is black Node가 Red이면 그 Node의 자식은 반드시 Black이다. If a node is red, then both its children are black Root Node에서 임의의 Leaf Node에 이르는 경로에서 만나는 Black Node의 수는 모두 같다. For each node, all paths from the node to descendant leaves contain the same number of black nodes. 여기서 Leaf Node는 일반적인 의미의 Leaf Node와 다르다. 모든 NIL 포인터가 NIL이라는 Leaf Node를 가리킨다고 가정한다.

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

RB Tree에서의 삽입 BST에서의 삽입과 같다. 다만 삽입 후 삽입된 Node를 Red로 칠한다. (이 Node를 x라 하자) 만일 x의 부모 Node p의 색상이 Black이면 아무 문제 없다. Red이면 Red Black 특성 ④가 깨진다. p p x x 그러므로 p가 Red인 경우만 고려하면 된다

RB Tree에서의 삽입 주어진 조건: p is red p2와 x의 형제 Node는 반드시 Black이다 Case 1: s가 Red Case 2: s가 Black p2 p s ? x

Case 1: s가 Red : 색상이 바뀐 Node Case 1 x x p2 p2 p s p s p2에서 방금과 같은 문제가 발생할 수 있다: recursive problem!

Case 2-1: s가 Black이고, x가 p의 오른쪽 자식 y x 2 y 1 2 1

Case 2-2: s가 Black이고, x가 p의 왼쪽 자식 : 색상이 바뀐 Node x p s p2 y Case 2-2 삽입 완료!

RB Tree에서의 삭제 삭제 Node의 자식이 없거나 1개만을 가진 Node로 제한해도 된다 텍스트의 p.146의 첫 문단 참조 삭제 Node를 m이라 하자 삭제 Node가 Red이면 아무 문제 없다 삭제 Node가 Black이라도 (유일한) 자식이 Red이면 문제 없다 m x m x x x

m 삭제 후 문제 발생 (Red Black 특성 ④ 위반) x 옆의 -1은 Root에서 x 를 통해 Leaf에 이르는 경로에서 Black Node의 수가 하나 모자람을 의미한다. p p p ? m x x s ? -1 -1 x l r ? ? m 삭제 후 문제 발생 (Red Black 특성 ④ 위반) x의 주변 상황에 따라 처리 방법이 달라진다

경우의 수 나누기 p is red p is black x Case 1 -1 x -1 Case 2

x s l r s s x x l r r l x s l r s x r l x s l r p p Case 1-3 -1 p

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

각 경우에 따른 처리 p p Case 1-1 s s x x -1 l r 삭제 완료! l r

1 x -1 s p 2 3 Case *-2 r 삭제 완료! Case *-3 x -1 s p l r 1 2 Case *-2로

발생. Recursive problem. 재귀적으로 처리. Case 2-1 x s x s p에서 방금과 같은 문제가 l r l Case 1-1, Case 1-2, Case 1-3 중의 하나로 Case 2-4 x s p r -1 l l x r -1

B-Trees 디스크의 접근 단위는 블록(페이지) 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다 Access time = Seek time + Latency + Transfer time; Seek time : 디스크 헤드를 정확한 트랙 위로 이동시키는 시간 Latency : 디스크를 회전시켜 해당 블록이 디스크 헤드 아래로 오게 하는 시간 (전체 접근 시간의 50%정도 차지) Transfer time : 디스크 블록을 메모리로 전송하는 시간 보통 디스크 접근 시간 단위가 milli-second인데 CPU는 mirco-second나 nano-second 단위로 일을 처리 디스크보다 CPU가 적어도 약 1000~1000000배 빠르며 이렇게 느린 디스크 I/O를 위해 색인(Index) 구조인 B-Tree 탄생

B-Trees (Continued…) Index(색인)가 가져야 할 특성 보조 기억 장치에서의 검색은 시간적인 부하가 많이 걸리기 때문에 탐색을 쉽게 하기 위해 File과는 별도로 Index를 만들어 사용한다. Index가 커질 경우 Index 역시 보조 기억 장치에 저장하는데 보조 기억 장치는 상대적으로 느리므로 보조 기억 장치의 Access 회수를 최대한 억제시켜야 한다. Index에의 Access 회수를 줄이기 위해서는 최대 탐색 길이 즉, Tree 높이를 줄여야 한다. 높이를 낮추기 위해서는 하나의 Node에서 나가는 Branch의 개수를 증가시킨다. Search Tree가 디스크에 저장되어 있다면 Tree의 높이를 최소화하는 것이 유리하다 B-Tree는 다진 Search Tree가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다

B-Trees (Continued…) 각 Node는 최대 m개, 최소 (m/2)개의 Sub-tree를 가져야 한다. Tree의 각 Node가 적어도 반 이상은 key값으로 채워져 있도록 한다. 따라서 Sub-tree가 없는 Node가 발생하지 않고 key 값이 가능한 효율적으로 Sub-tree에 분배될 수 있도록 한다. Root Node는 최소한 두 개의 Sub-tree를 가져야 한다. 단 Tree에 Root 만 있을 경우 Sub-tree는 없다. 모든 Leaf Node는 같은 Level에 있어야 한다. 모든 Leaf Node가 Root로부터 같은 거리에 있으므로 어느 Leaf Node를 탐색하든 처리 횟수가 같도록 한다. 각 Leaf Node의 key 값의 개수는 최소 (m/2)-1개, 최대 m-1개이다

… 다진 Search Tree T0 T1 T2 T3 Tk Ti keyi-1 < < keyi key0 key1

B-Tree B-Tree는 균형 잡힌 다진 Search Tree로 다음의 성질을 만족한다 Root를 제외한 모든 Node는 k/2 ~ k 개의 키를 갖는다 모든 Leaf Node는 같은 깊이를 가진다

… B-Tree의 Node 구조 … <key0, p0> <key1, p1> <keyk-1, pk-1> …

B-Tree를 통해 Record에 접근하는 과정 <key0, p0> … <keyi, pi> 키 keyi를 가진 record 페이지 pi

B-Tree에서의 삽입 ▷ t : Tree의 Root Node BTreeInsert(t, x) ▷ x : 삽입하고자 하는 Key BTreeInsert(t, x) {         x를 삽입할 Leaf Node r을 찾는다;         x를 r에 삽입한다;         if (r에 Overflow 발생) then clearOverflow(r); } clearOverflow(r) {       if (r의 형제 Node 중 여유가 있는Node가 있음) then {r의 남는 Key를 넘긴다};      else {                 r을 둘로 분할하고 가운데 키를 부모 Node로 넘긴다;                 if (부모 Node p에 Overflow 발생) then clearOverflow(p);      }

B-Tree에서 삽입의 예 (a) 7 13 25 34 1 2 3 4 6 8 10 15 17 19 20 27 28 30 33 37 38 40 41 45 9, 31 삽입 (b) 7 13 25 34 1 2 3 4 6 8 9 10 15 17 19 20 27 28 30 31 33 37 38 40 41 45 5 삽입

(c) 7 13 25 34 1 2 3 4 5 6 8 9 10 15 17 19 20 27 28 30 31 33 37 38 40 41 45 Overflow! 6 13 25 34 1 2 3 4 5 7 8 9 10 15 17 19 20 27 28 30 31 33 37 38 40 41 45 39 삽입

39 삽입 (d) 6 13 25 34 1 2 3 4 5 7 8 9 10 15 17 19 20 27 28 30 31 33 37 38 39 40 41 45 Overflow! 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 27 28 30 31 33 37 38 39 41 45 23, 35, 36 삽입 분할!

23, 35, 36 삽입 (e) 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 30 31 33 35 36 37 38 39 41 45 32 삽입

32 삽입 (f) 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 30 31 32 33 35 36 37 38 39 41 45 Overflow! Overflow! 6 13 25 31 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 30 32 33 35 36 37 38 39 41 45 분할! 31 분할! 6 13 25 34 40 1 2 3 4 5 7 8 9 10 15 17 19 20 23 27 28 30 32 33 35 36 37 38 39 41 45

B-Tree에서의 삭제 ▷ t : Tree의 Root Node ▷ x : 삭제하고자 하는 Key BTreeDelete(t, x, v) {         if (v가 Leaf Node 아님) then {          x의 직후원소 y를 가진 Leaf Node를 찾는다;          x와 y를 맞바꾼다;         }         Leaf Node에서 x를 제거하고 이 Leaf Node를 r이라 한다;         if (r에서 Underflow 발생) then clearUnderflow(r); } clearUnderflow(r) {          if ( r의 형제 Node 중 키를 하나 내놓을 수 있는 여분을 가진 Node가 있음)          then { r이 Key를 넘겨받는다;}          else {                  r의 형제 Node와 r을 합병한다;                  if (부모 Node p에 Underflow 발생) then clearUnderflow(p);          } ▷ t : Tree의 Root Node ▷ x : 삭제하고자 하는 Key ▷ v : x를 갖고 있는 Node

B-Tree에서 삭제의 예 15 1 2 3 5 6 7 9 10 16 18 24 25 26 20 21 19 22 4 8 7 삭제 (a) (b) 5 6 4 삭제

15 1 2 3 6 9 10 16 18 24 25 26 20 21 19 22 5 8 Underflow! 1 2 5 6 3 8 9 삭제 (c) 4 6 4 제거 4, 5 교환 재분배

15 1 2 5 6 10 16 18 24 25 26 20 21 19 22 3 8 (d) Underflow! 5 6 8 10 3 병합! 3 15 19 22

B Tree, B+ Tree, B* Tree B Tree Balanced Tree, 차수가 2이상 가능 m-원 Tree의 단점인 한 쪽으로 편중된 Tree가 생성되는 경우를 보완하고자 Root Node로부터 Leaf Node의 Level이 같도록 유지 대용량의 데이터를 효율적으로 관리하기 위해 고안 모든 Leaf Node가 Root Node로부터 같은 거리에 있어야 한다. 항상 균형을 유지해야 하므로 삽입, 삭제가 일어날 때 Tree의 균형을 유지하기 위해 보조연산이 필요 Node의 차수가 여유가 있으면 보조연산이 필요 없지만, 차수가 꽉 차면 Leaf Node의 중간 값을 부모 Node로부터 두 갈래로 분열 B+ Tree B Tree의 문제점(보조연산 필요)을 보완하기 위해 B Tree를 약간 변형한 트리 보조연산 회수를 줄였다 B Tree에 비해 공간 활용도를 높일 수 있다. B Tree는 최소 ½면 분할할 수 있지만, B* Tree는 최소 2/3가 되야 분열 Node의 분열을 줄여서 보조연산 회수를 감소. Node가 꽉 차면 분열하지 않고 형제 Node로 재배치(인접 Node가 찰 때까지 지연 가능) B* Tree Index 부분과 순차 데이터 부분으로 구성 모든 데이터를 가진 Node들이 Leaf Node로서 Tree의 마지막 높이에 존재하도록 유지하고 연결 리스트로 순차적 접근 접근 시간을 동일하게 유지

Thank you