쉽게 배우는 알고리즘 5장. 검색트리

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

학습목표 검색에서 레코드와 키의 역할을 구분한다. 이진검색트리에서의 검색·삽입·삭제 작업의 원리를 이해한다. 이진검색트리의 균형이 작업의 효율성에 미치는 영향을 이해하고, 레드블랙트리의 삽입·삭제 작업의 원리를 이해한다. B-트리의 도입 동기를 이해하고 검색·삽입·삭제 작업의 원리를 이해한다. 검색트리 관련 작업의 점근적 수행시간을 이해한다. 일차원 검색의 기본 원리와 다차원 검색의 연관성을 이해한다.

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

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

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

서브트리의 예 r 30 20 40 10 25 35 45 (a) 20 40 10 25 35 45 (b) 노드 r의 왼쪽 서브트리 (c) 노드 r의 오른쪽 서브트리

BST에서의 검색 x: 검색하고자 하는 키 t: 트리의 루트 노드 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: 삽입하고자 하는 키 t: 트리의 루트 노드 treeInsert(t, x) {         if (t=NIL) then {                 key[r] ← x;                             ▷ r : 새 노드                 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가지 경우에 따라 다르게 처리한다 r: 삭제하고자 하는 노드 Case 1 : r이 리프 노드인 경우

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

BST에서의 삭제 t: 트리의 루트 노드 r: 삭제하고자 하는 노드 p: r의 부모 노드 treeDelete(t, r, p) { if (r = t) then root ← deleteNode(t);     ▷ r이 루트 노드인 경우     else if (r = left[p]) ▷ r이 루트가 아닌 경우 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;         }

삭제의 예: 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의 모든 노드에 블랙 또는 레드의 색을 칠하되 다음의 레드블랙특성을 만족해야 한다 루트는 블랙이다 모든 리프는 블랙이다 노드가 레드이면 그 노드의 자식은 반드시 블랙이다 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다 여기서 리프 노드는 일반적인 의미의 리프 노드와 다르다. 모든 NIL 포인터가 NIL이라는 리프 노드를 가리킨다고 가정한다.

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

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

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

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

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

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

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

m 삭제 후 문제 발생 (레드블랙특성 ④ 위반) x 옆의 -1은 루트에서 x 를 통해 리프에 이르는 경로에서 블랙 노드의 수가 하나 모자람을 의미한다. p p p ? m x x s ? -1 -1 x l r ? ? m 삭제 후 문제 발생 (레드블랙특성 ④ 위반) 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 디스크의 접근 단위는 블록(페이지) 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다 B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것이다

… 다진검색트리 T0 T1 T2 T3 Tk Ti keyi-1 < < keyi key0 key1 key2 …

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

… B-트리의 노드 구조 … <key0, p0> <key1, p1> <keyk-1, pk-1> 부모 노드의 페이지 <key0, p0> <key1, p1> … <keyk-1, pk-1> …

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

B-Tree에서의 삽입 ▷ t : 트리의 루트 노드 BTreeInsert(t, x) ▷ x : 삽입하고자 하는 키 {         x를 삽입할 리프 노드 r을 찾는다;         x를 r에 삽입한다;         if (r에 오버플로우 발생) then clearOverflow(r); } clearOverflow(r) {       if (r의 형제 노드 중 여유가 있는 노드가 있음) then {r의 남는 키를 넘긴다};      else {                 r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다;                 if (부모 노드 p에 오버플로우 발생) 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 오버플로우! 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 오버플로우! 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 오버플로우! 오버플로우! 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 : 트리의 루트 노드 ▷ x : 삭제하고자 하는 키 ▷ v : x를 갖고 있는 노드 BTreeDelete(t, x, v) {         if (v가 리프 노드 아님) then {          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);          } ▷ t : 트리의 루트 노드 ▷ x : 삭제하고자 하는 키 ▷ v : x를 갖고 있는 노드

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 언더플로우! 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) 언더플로우! 5 6 8 10 3 병합! 3 15 19 22

다차원 검색 검색키가 두 개 이상의 필드로 이루어진 검색 3개의 다차원 검색트리와 하나의 다차원 저장/검색 방법 소개 KD-트리 KDB-트리 R-트리 그리드 파일

KD-Tree 각 레벨에서 필드를 번갈아가며 검색에 사용한다 한 level에서는 하나의 필드만 사용한다 총 k 개의 필드를 사용하는 검색이라면, k 개의 level을 내려가면 검색에 사용하는 필드가 일치한다

KD-Tree … … … … … … a0 a1 … ak-1 b0 b1 … bk-1 c0 c1 … ck-1 d0 d1 d2 … 레벨 0 a0 a1 … ak-1 레벨 1 b0 b1 … bk-1 c0 c1 … ck-1 … 레벨 2 d0 d1 d2 … e0 e1 e2 … … … 레벨 k-1 r0 r1 … rk-1 … 레벨 k x0 x1 … xk-1 … …

A 50 50 B 10 70 C 80 85 D 25 20 E 40 85 F 70 85 G 10 60

50 50 A 10 70 B 80 85 C 25 20 D 40 85 E 70 85 F 10 60 G E(40,85) A(50,50) F(70,85) C(80,85) B(10,70) D(25,20) G(10,60)

A 50 50 B 30 55 C 55 70 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 L 68 72 M 76 78

A 50 50 B 30 55 C 55 70 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 L 68 72 M 76 78

A 50 50 B 30 55 C 55 70 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 L 68 72 M 76 78

A 50 50 C 55 70 B 30 55 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 L 68 72 M 76 78

C 55 70 B 30 55 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 L 68 72 M 76 78

C 55 70 B 30 55 L 68 72 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 M 76 78

C 55 70 B 30 55 L 68 72 40 85 D 65 20 E 60 85 F 61 60 G 65 80 I H 70 60 75 55 J K 70 75 M 76 78

KDB-Tree KD-Tree와 B-Tree의 특성 결합 각 레코드는 k차원 공간에서 하나의 점에 해당 KD-Tree의 특성 다차원 key B-Tree의 특성 디스크의 한 페이지가 한 노드와 일치 Balanced tree 각 레코드는 k차원 공간에서 하나의 점에 해당 자신이 속한 공간을 담당하는 색인 node들을 따라감

KDB-Tree의 Node들 Internal node 하나는 k차원 공간에서 한 영역을 담당한다 같은 level에 있는 모든 노드들은 서로 겹치는 영역이 없다 같은 level에 있는 모든 노드들의 담당 영역을 합하면 k차원 공간 전체가 됨 리프 노드는 데이터 페이지 정보를 저장

: 제외된 영역 : 점 (하나의 레코드 포인터)

x의 자식 노드에서 분할 (a) 분할 전 (b) 노드 x 분할 후 x

Disk의 한 페이지 …

R-Tree B-트리의 다차원 확장 균형잡힌 검색트리 모든 레코드는 리프 노드에서만 가리킴 다차원 도형의 저장 가능 점, 선, 면, 폐공간, 각종 도형 MBR(Minimum Bounding Rectangle)로 근사

이름 Key1 Key2 A 8 100 B 4 10 C 6 35 D 1 E 40 F 5 45 G 7 85 H 3 20 I 70 J 2 30 K 50 L

120 110 100 90 80 70 60 50 40 30 20 10 A G I E K L F C J H D B 1 2 3 4 5 6 7 8 9 10 11 12

x R1 R2 R3 R4 R5 R6 R7 A I C G E K D H B F J L 120 110 100 90 80 70 60 50 40 30 20 10 R1 A R3 R4 G I R5 R2 E K R7 L F C J R6 H D B 1 2 3 4 5 6 7 8 9 10 11 12

R1 R2 R3 R4 R5 R6 R7 A I C G E K D H B F J L M 120 110 100 90 80 70 60 50 40 30 20 10 N R1 A R3 R4 G I R2 E R5 K R7 L F C N J R6 M H D B 1 2 3 4 5 6 7 8 9 10 11 12

R1 R2 R3 R4 R5 R6 R7 A I C G E K D H B M J N L F 120 110 100 90 80 70 60 50 40 30 20 10 R1 A R3 R4 G I R5 R2 E K R7 L F C N J R6 M H D B 1 2 3 4 5 6 7 8 9 10 11 12

R1 R2 y R3 R4 R5 R6 R7 A I C G E K D H B M P J N L F O 120 110 100 90 80 70 60 50 40 30 20 10 Q R1 A R3 R4 G I E R5 R2 L K R7 F C J O N R6 M P H D B Q 1 2 3 4 5 6 7 8 9 10 11 12

… R1 R2 R3 R4 R5 R6 R7 R8 D H P Q J N L F O B M 120 110 100 90 80 70 60 50 40 30 20 10 R1 A R3 R4 G I E R5 R2 L K R7 F C J O N R6 R8 M P H D B Q 1 2 3 4 5 6 7 8 9 10 11 12

Grid File 60 a(10, 50) k(55, 45) f(30, 45) d(85, 45) e(60, 40) h(80, 35) l(25, 25) j(40, 15) b(10, 10) c(80, 10) g(55, 5) 100

(a) (b) P1 60 a b c a(10, 50) 30 b(10, 10) c(80, 10) 100 P1 60 a b 100 P1 (b) 60 a b a(10, 50) P2 d(85, 45) c d 30 b(10, 10) c(80, 10)

(c) (d) P1 60 a b a(10, 50) P2 d(85, 45) e(60, 40) c d e 30 b(10, 10) 50 100 (d) P1 60 a b f a(10, 50) P2 f(30, 45) d(85, 45) e(60, 40) c d e 30 b(10, 10) c(80, 10)

(e) (f) P1 60 a b f a(10, 50) f(30, 45) d(85, 45) e(60, 40) 30 P2 d e g c P3 b(10, 10) c(80, 10) g(55, 5) 50 100 P1 (f) 60 a b f a(10, 50) f(30, 45) d(85, 45) e(60, 40) h(80, 35) 30 P2 d e g c P3 h b(10, 10) c(80, 10) g(55, 5)

(g) (h) P1 60 a b f a(10, 50) h d P4 P2 i e f(30, 45) d(85, 45) c(80, 10) P3 b(10, 10) g(55, 5) c g 50 75 100 P1 f a (h) 60 j b P5 a(10, 50) f(30, 45) d(85, 45) e(60, 40) P2 i e i(65, 35) h(80, 35) 30 h d P4 j(40, 15) b(10, 10) c(80, 10) P3 g(55, 5) c g

(i) P1 f a 60 l j b P5 a(10, 50) f(30, 45) k(55, 45) d(85, 45) e(60, 40) P2 k i e i(65, 35) h(80, 35) 30 l(25, 25) h d P4 j(40, 15) b(10, 10) c(80, 10) P3 g(55, 5) c g 50 75 100

50 75 30 1 2 4 5 3 3

Thank you