제5장 검색트리

(1)

http://academy.hanb.co.kr

쉽게 배우는 알고리즘

5장. 검색트리

IT COOKBOOK IT COOKBOOK

5장. 검색트리

나는 보다 응용력 있는 유형의 수학이라는 이유 때문에

컴퓨터 과학을 하고 싶었다.

-로버트 타잔

(2)

- 3 - 한빛미디어㈜

학습목표

• 검색에서 레코드와 키의 역할을 구분한다.

• 이진검색트리에서의 검색·삽입·삭제 작업의 원리를

이해한다.

• 이진검색트리의 균형이 작업의 효율성에 미치는 영향

을 이해하고, 레드블랙트리의 삽입·삭제 작업의 원리

를 이해한다.

• B-트리의 도입 동기를 이해하고 검색·삽입·삭제 작업

의 원리를 이해한다.

• 검색트리 관련 작업의 점근적 수행시간을 이해한다.

• 일차원 검색의 기본 원리와 다차원 검색의 연관성을

이해한다.

숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK

레코드, 키, 검색트리

• 레코드record – 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 – e.g., 사람의 레코드 • 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰 번호, 최종 학력, 연 소득, 가족 상황 등의 정보 포함 • 필드field – 레코드에서 각각의 정보를 나타내는 부분 – e.g., 위 사람의 레코드에서 각각의 정보를 나타내는 부분 • 검색 키search key또는 키key

– 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 – 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로 이루어질 수도 있다 • 검색 트리search tree – 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다 – 이를 통해 해당 레코드가 저장된 위치를 알 수 있다

(3)

숙명여자대학교 멀티미디어과학과

Binary Search Tree (BST)

• 각 노드는 하나씩의 키 값을 갖는다. 각 노드의 키

값은 다르다.

• 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두

개의 자식을 갖는다.

• 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키

값보다 크고, 오른쪽 자식의 키값보다 작다.

IT COOKBOOK IT COOKBOOK 30 40 20 25 10 35 45 30 40 20 25 10 45 35 (a) (b)

BST의 예

(4)

숙명여자대학교 멀티미디어과학과 30 40 20 25 10 35 45 20 25 10 40 45 35 (a) (b) 노드 r의 왼쪽 서브트리 r (c) 노드 r의 오른쪽 서브트리

서브트리의 예

BST에서의 검색

treeSearch(t, x) t: 트리의 루트 노드 x: 검색하고자 하는 키 // 성공하면 해당 노드를 리턴, 실패하면 NIL을 리턴 {

if(t=NIL orkey[t]=x) then returnt;

if(x < key[t])

then returntreeSearch(left[t], x); else returntreeSearch(right[t], x); }

(5)

t

left[t]

right[t]

BST 검색에서의 재귀적 관점

• 성공

– 검색이 leaf 노드까지 가지 않고, – 중간에 어떤 노드 r의 키 값이 x와 같아지는 순간 r을 리턴하고 종료

• 실패

– 검색이 루트 노드에서 leaf 노드까지 진행된다.

– leaf 노드는 자식이 없으므로treeSearch(NIL, x)가 되어 NIL을 리턴하고 종료.

• 그림 5-4 참조.

– 교재 P 132p

(6)

숙명여자대학교 멀티미디어과학과 30 40 20 25 10 35 30 30 20 30 20 25 30 40 20 25 30 40 20 25 10 (a) (b) (c) (d) (e) (f)

BST에서의 삽입의 예 1: 30, 20, 25, 40, 10, 35

순으로 삽입됨

숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 30 35 20 25 10 40 (f)

BST에서의 삽입의 예 2: 10, 20, 25, 30, 40, 45

순으로 삽입됨

(7)

BST에서의 삽입 개요

// 같은 키 값이 트리 내에 없다고 가정 treeInsert(t, x) t: 트리의 루트 노드 x: 삽입하고자 하는 키 // 작업 완료 후 루트 노드의 포인터를 리턴한다. {

if(t=NIL) then{ // 검색에 실패했음. Leaf까지 내려옴.

key[r] ← x; ▷ r : 새 노드 returnr;

}

if(x < key(t))

then{left[t] ← treeInsert(left[t], x); returnt;}

else{right[t] ← treeInsert(right[t], x); returnt;}

} IT COOKBOOK IT COOKBOOK

BST에서의 삽입 상세 버전

// 같은 키 값이 트리 내에 없다고 가정 treeInsert(t, x) t: 트리의 루트 노드 x: 삽입하고자 하는 키 // 작업 완료 후 루트 노드의 포인터를 리턴한다. {

if(t=NIL) then{ // 검색에 실패했음. Leaf까지 내려옴.

key[r] ← x; left[r] ← NIL; left[r] ← NIL; ▷ r : 새 노드

returnr; }

if(x < key(t))

then{left[t] ← treeInsert(left[t], x); returnt;}

else{right[t] ← treeInsert(right[t], x); returnt;}

(8)

BST에서의 삭제

• 3가지 경우에 따라 다르게 처리한다.

– Case 1 : r이 리프 노드인 경우

– Case 2 : r의 자식 노드가 하나인 경우

– Case 3 : r의 자식 노드가 두 개인 경우

t

: 트리의 루트 노드

r: 삭제하고자 하는 노드

BST에서의 삭제 개요

Sketch-TreeDelete(t, r) // t: 트리의 루트 노드 // r: 삭제하고자 하는 노드 { if(r이 리프 노드) then ▷ Case 1 그냥 r을 버린다;

else if(r의 자식이 하나만 있음) then ▷ Case 2

r의 부모가 r의 자식을 직접 가리키도록 한다;

else ▷ Case 3

r의 오른쪽 서브트리의 최소원소 노드 s를 삭제하고, s를 r 자리에 놓는다;

(9)

숙명여자대학교 멀티미디어과학과 55 28 8 60 15 90 48 30 18 38 3 50 r (a) r의 자식이 없음 (b) 단순히 r을 제거한다 36 32 33 55 28 8 60 15 90 48 30 38 3 50 36 32 33

삭제의 예: Case 1

r은 리프 노드이므로 지우고, 단지 r의 부모 노드에서 r을 가리키고 있던 포인터를 NIL로만 바꿔주면 됨 IT COOKBOOK IT COOKBOOK 55 28 8 60 15 90 48 30 18 38 3 50 r (a) r의 자식이 하나뿐임 55 28 8 60 15 90 48 18 3 50 (c) r자리에 r의 자식을 놓는다 36 32 33 38 36 32 33 55 28 8 60 15 90 48 18 38 3 50 (b) r을 제거 36 32 33

삭제의 예: Case 2

r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식 을 가리키도록 바꿔주면 됨

(10)

숙명여자대학교 멀티미디어과학과 • r 자리에 옮겨 놓아도 BST의 성질을 전혀 깨뜨리지 않는 원소는 무엇일까? • 왼쪽 서브트리 원소들보다 크고, 오른쪽 서브트리의 원소들보다 작아야 함. • 트리 전체에 딱 두 개가 존재!!! ü r의 왼쪽 서브트리에서 가장 큰 원소 ü r의 오른쪽 서브트리에서 가장 작은 원소 55 28 8 60 15 90 48 30 45 18 41 38 3 50 r s (a) r의 직후원소 s를 찾는다 36 32 33 55 30 8 60 15 90 48 45 18 41 38 3 50 s (b) r을 없앤다 36 32 33

삭제의 예: Case 3

숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 55 30 8 60 15 90 48 45 18 41 3 50 s (d) s가 있던 자리에 s의 자식을 놓는다 38 36 32 33 55 30 8 60 15 90 48 45 18 41 38 3 50 s (c) s를 r자리로 옮긴다 36 32 33 ü r의 왼쪽 서브 트리 에서 가장 큰 원소 • r의 직전원소임 • 오른자식존재불가 ü r의 오른쪽 서브트 리에서 가장 작은 원소 • r의 직후원소임 • 왼쪽자식존재불가

(11)

BST에서의 삭제 상세 버전

treeDelete(t, r, p)

{

if(r = t) thenroot ←deleteNode(t); ▷ r이 루트 노드인 경우

else if(r = left[p]) ▷ r이 루트가 아닌 경우

thenleft[p] ←deleteNode(r); ▷ r이 p의 왼쪽 자식

elseright[p] ←deleteNode(r); ▷ r이 p의 오른쪽 자식 }

deleteNode(r) // r의 부모 노드에 매달릴 노드를 리턴함 {

if(left[r] = right[r] = NIL) then returnNIL; ▷ Case 1

else if(left[r] = NIL and right[r] ≠ NIL) then returnright[r]; ▷ Case 2-1

else if(left[r] ≠ NIL and right[r] = NIL) then returnleft[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]) thenright[r] ← right[s];

elseleft[parent] ← right[s];

returnr; } } t: 트리의 루트 노드 r: 삭제하고자 하는 노드 p: r의 부모 노드 IT COOKBOOK IT COOKBOOK

Red-Black Tree (RB Tree)

• BST의 모든 노드에 블랙 또는 레드의 색을 칠하되 다음의 레드블랙특성을 만족해야 한다 ① 루트는 블랙이다 ② 모든 리프는 블랙이다 ③ 노드가 레드이면 그 노드의 자식은 반드시 블랙이다 ④ 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다 ü 여기서 리프 노드는 일반적인 의미의 리프 노드와 다르다. 모든 NIL 포인터가 NIL이라는 리프 노드를 가리킨다고 가정한다.

(12)

숙명여자대학교 멀티미디어과학과 NIL NIL

NIL NIL NIL

NIL

(a) BST의 한 예 (b) (a)를 RB Tree로 만든 예

NIL (c) 실제 구현시의 NIL 노드 처리 방법

BST를 RB Tree로 만든 예

RB Tree에서의 삽입

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

(13)

RB Tree에서의 삽입

? x p s p2 주어진 조건: p is red • p2_{는 반드시 블랙이고, x의 형제 노드도 반드시 블랙이다} • p의 형제 노드인 s는 레드/블랙이 모두 가능하므로 s의 색상에 따라 두 가지로 나눈다 – Case 1: s가레드 – Case 2: s가 블랙 IT COOKBOOK IT COOKBOOK

Case 1: s가

레드

• p와 s의 색상을 red à black으로, p2_{의 색상은 black à red}

• p2_{가 루트면 p}2_{의 색상을 다시 black을 바꾸고 끝.} • p2_{가 루트가 아니면 p}2_{의 부모 색상을 확인해야 함.} ü p2_{의 부모 색상이 black: RB트리 속성 만족됨!} ü p2_{의 부모 색상이 red: 지금과 똑 같은 경우이므로 recursion 돌면 됨.} x p s x p s Case 1 p 2 p2 : 색상이 바뀐 노드 üp2에서 방금과 같은 문제가 발생할 수 있다: recursive problem!

(14)

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

• p를 중심으로 왼쪽으로 회전한다. • 여전히 레드블랙특성 ƒ을 위반한다. Case 2-2로 간다. y p s p2 x x p 1 s p2 y 2 2 1 Case 2-1 Case 2-2로! 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK x p s x p s p2 p2 y y Case 2-2

Case 2-2: s가 블랙이고, x가 p의 왼쪽 자식

• p2_{를 중심으로 오른쪽으로 회전하고,} • p와 p2_{의 색상을 맞바꾼다.} : 색상이 바뀐 노드 ü삽입 완료!

(15)

RB Tree에서의 삭제

• 삭제 노드의 자식이 없거나 1개만을 가진 노드로 제한해도 된다 – 텍스트의 p.146의 첫 문단 참조 – 삭제 노드를 m이라 하자 • 삭제 노드가레드이면 아무 문제 없다 • 삭제 노드가 블랙이라도 (유일한) 자식 x가레드이면 문제 없다 ― 삭제 후 x의 색상을 블랙으로 바꾸면 됨. x x m x x m m이 블랙이면 m의 부모 색상은 상관 없게 됨. IT COOKBOOK IT COOKBOOK ? x -1 ? s ? ? l r p m 삭제 후 문제 발생 (레드블랙특성 ④ 위반) x의 주변 상황에 따라 처리 방법이 달라진다 x x m -1 p p x 옆의 -1은 루 트에서 x 를 통해 리프에 이르는 경로에서 블랙 노드의 수가 하 나 모자람을 의 미한다. • 이제 까다로운 경우는 m과 x의 색상이 모두 블랙일 때이다. – 이 때 m이 삭제되면 x는 m의 부모 p의 자식이 되고, – 레드블랙특성 ④ 가 깨진다.

(16)

숙명여자대학교 멀티미디어과학과 x Case 1 -1 x Case 2 -1

경우의 수 나누기

p is red

p is black

s - p가 레드면 s는 반드시 블랙임. s - p가 블랙이면 s는 블랙, 레드 모 두 가능. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK Case 1-1 x -1 s p l r x -1 s p Case 1-2 x -1 Case 2-4 s l r p x -1 Case 2-1 s l r p l r Case 1-3 x -1 s p l r Case 2-3 x -1 s p l r x -1 s p Case 2-2 l r p의 색상만 다른데 p의 색상이 처리 방법 에 영향을 미치지 않으므로 통합처리 할 수 있음

(17)

숙명여자대학교 멀티미디어과학과 Case 1-1 x -1 s p l r x -1 Case 2-4 s l r p x -1 Case 2-1 s l r p Case *-3 x -1 s p l r x -1 s p Case *-2 l r

ü최종적으로 5가지 경우로 나뉜다

IT COOKBOOK IT COOKBOOK Case 1-1 x -1 s p l r x s p l r

각 경우에 따른 처리

ü Case 1-1

• 단순히 p와 s의 색상을 맞바꾼다. • x에 이르는 경로 상에 블랙 노드가 1개 늘었으므로 OK • s에 이르는 경로 상의 블랙 노드 개수는 변화 없으므로 OK

(18)

숙명여자대학교 멀티미디어과학과 1 x -1 s p 2 3 Case *-2 1 x s p 2 3 r r

ü Case *-2

• p를 중심으로 왼쪽으로 회전하고, • p와 s의 색상을 맞바꾸고, r의 색상을 레드에서 블랙으로 바꿈 Ø x에 이르는 경로 상에 블랙 노드가 1개 늘었으므로 OK Ø 1,2,3으로 표시된 이르는 서브트리까지 경로 상의 블랙 노드 개수는 변화 없으므로 OK 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK Case *-3 x -1 s p l r 1 x -1 s p l r 2 1 2 Case *-2로

ü Case *-3

• s를 오른쪽으로 회전하고, l과 s의 색상을 맞바꾼다. • 이제 Case *-2와 같은 모양이 되었으므로 Case *-2로 이동하여 마무리 처리한다.

(19)

숙명여자대학교 멀티미디어과학과 p x -1 Case 2-1 s l r x -1 s l r p

ü Case 2-1

ü 단순히 s의 색상을 블랙에서 레드로 바꾼다. ü 이제 s를 지나는 경로에서도 블랙노드가 1개 부족 èp를 지나가는 경로 전체에서 블랙 노드가 하나 부족함 ü Recursive problem. • p를 문제 발생 노드로 하여 재귀적으로 다시 시작한다. IT COOKBOOK IT COOKBOOK x -1 Case 2-4 s l _r x -1 s l r p p Case 1-1, Case 1-2, Case 1-3 중의 하나로

ü Case 2-4

• p를 중심으로 왼쪽으로 회전하고, p와 s의 색상을 맞바꾼다. • l과 r을 경유하는 경로는 문제가 없다. • 다만 문제가 발생한 x의 부모 노드의 색상이 블랙에서 레드로 바뀌었음 è Case 1에 해당

v 색상 조합을 따져 Case 1-1, Case 1-2, Case 1-3 중의 하나로 이동한다.

(20)

B-Trees

• 검색 트리가 방대하면 검색트리를 메모리에 모두 올려놓고 사용할 수 없을 수 있음 – 검색트리를 디스크에 저장해두고 사용해야 함(외부검색트리형태) – 디스크의 접근 단위는 블록(페이지) – 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다 • 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리 – 예) 10억 개 내외의 키를 관리해야 한다면? BST가 균형이 잘 맞았다고 해도 트리 깊이가 30 레벨 정도 됨. – 이럴 때 한 노드에 자식이 두 개가 아닌 여러 개가 붙을 수 있다면? 한 노드에 256개의 자식이 붙을 수 있으면 깊이가 5 정도 될 것임. • B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의 경우 디스크 접근 횟수를 줄인 것 – B-트리 == 외부 다진검색트리 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK

T

₀

key

₀

key

₁

key

₂

_…

key

_k-1

T

₁

T

₂

T

₃

…

T

_k

T

_i

key

_i-1

<

< key

_i

(21)

§

B-Tree는 균형 잡힌 다진검색트리로 다음의 성질을

만족

– 루트를 제외한 모든 노드는   ~ k 개의 키를 갖는다. • 분기 수를 최대한 늘리되 균형을 위해 최대 허용량의 반 이상은 채우자는 의미 – 모든 리프 노드는 같은 깊이를 가진다.

B-Tree

<key0, p0> <key1, p1>

…

<keyk-1, pk-1>

…

부모 노드의 페이지

(22)

숙명여자대학교 멀티미디어과학과 <key0, p0> … <keyi, pi> … 페이지 pi 키 keyi를 가진 record

B-트리를 통해 Record에 접근하는 과정

§ 노드의 여러 키 중 일치하는 것이 있는지 확인해야 함.

§ key

_i-1

< x < key

_i

인 두 키를 찾아 그 사이에 있는 따라

내려가며 찾아야 함.

(23)

B-Tree에서의 삽입 개요

BTreeInsert(t, x) { x를 삽입할 리프 노드 r을 찾는다; x를 r에 삽입한다; if(r에 오버플로우 발생)thenclearOverflow(r); } clearOverflow(r) { if(r의 형제 노드 중 여유가 있는 노드가 있음)then{r의 남는 키를 넘긴다}; else{ r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다; if(부모 노드 p에 오버플로우 발생) thenclearOverflow(p); } } ▷ t : 트리의 루트 노드 ▷ x : 삽입하고자 하는 키 IT COOKBOOK IT COOKBOOK 1 2 3 4 6 8 10 15 17 19 20 7 13 25 34 (a) 37 38 40 41 45 27 28 30 33 1 2 3 4 6 8 9 10 15 17 19 20 7 13 25 34 (b) 37 38 40 41 45 27 28 30 31 33 9, 31 삽입 5 삽입

B-Tree에서 삽입의 예(k=5 일 때)

(24)

숙명여자대학교 멀티미디어과학과 1 2 3 4 5 6 8 9 10 15 17 19 20 7 13 25 34 (c) 37 38 40 41 45 27 28 30 31 33 오버플로우! 1 2 3 4 5 7 8 9 10 15 17 19 20 6 13 25 34 37 38 40 41 45 27 28 30 31 33 39 삽입

§ 바로 오른쪽 형제 노드에 공간 여유가 있으니 키를 하나

넘긴다(재분배: redistribution).

• 맨 오른쪽의 6을 형제 노드에 바로 넘기면 B-트리 성질이 훼손됨. • 부모 노드에 있는 7을 넘기고 그 자리에 6을 놓는다. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 1 2 3 4 5 7 8 9 10 15 17 19 20 6 13 25 34 37 38 39 40 41 45 27 28 30 31 33 오버플로우! 39 삽입 (d) 1 2 3 4 5 7 8 9 10 15 17 19 20 6 13 25 34 40 37 38 39 27 28 30 31 33 41 45 분할! 23, 35, 36 삽입

§ 바로 옆 형제 노드에 공간 여유가 없음 è 분할해야 함

• 맨 가운데 키 40을 부모 노드로 넘기고 나머지를 분할함 • 노드가 늘어났으므로 부모 노드에 분기를 위한 키가 하나 더 필요하기 때문

(25)

숙명여자대학교 멀티미디어과학과 23, 35, 36 삽입 1 2 3 4 5 7 8 9 10 15 17 19 20 23 6 13 25 34 40 35 36 37 38 39 27 28 30 31 33 41 45 32 삽입 (e) IT COOKBOOK IT COOKBOOK 1 2 3 4 5 7 8 9 10 15 17 19 20 23 6 13 25 31 34 40 35 36 37 38 39 27 28 30 32 33 41 45 오버플로우! 1 2 3 4 5 7 8 9 10 15 17 19 20 23 6 13 25 35 36 37 38 39 27 28 30 32 33 41 45 분할! 34 40 31 32 삽입 1 2 3 4 5 7 8 9 10 15 17 19 20 23 35 36 37 38 39 41 45 오버플로우! (f) 6 13 25 34 40 27 28 30 31 32 33 분할!

(26)

B-Tree에서의 삭제

BTreeDelete(t, x, v) { if(v가 리프 노드 아님) then{ x의 직후원소 y를 가진 리프 노드를 찾는다; x와 y를 맞바꾼다; } 리프 노드에서 x를 제거하고 이 리프 노드를 r이라 한다; if(r에서 언더플로우 발생) thenclearUnderflow(r); } clearUnderflow(r) { if( r의 형제 노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있음) then{ r이 키를 넘겨받는다;} else{ r의 형제 노드와 r을 합병한다; if(부모 노드 p에 언더플로우 발생)thenclearUnderflow(p); } } ▷t : 트리의 루트 노드 ▷x : 삭제하고자 하는 키 ▷v : x를 갖고 있는 노드 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 15 1 2 3 5 6 7 9 10 16 18 20 21 24 25 26 19 22 4 8 7 삭제 (a) (b) 15 1 2 3 5 6 9 10 16 18 20 21 24 25 26 19 22 4 8 4 삭제

B-Tree에서 삭제의 예

(27)

숙명여자대학교 멀티미디어과학과 15 1 2 3 6 9 10 16 18 20 21 24 25 26 19 22 5 8 언더플로우! (c) 15 1 2 3 4 6 9 10 16 18 20 21 24 25 26 19 22 5 8 4 제거 4, 5 교환

§ 형제 노드 중 여분의 키를 내놓을 수 있는지 본다

• 왼쪽 노드가 여분이 있으므로 키 3을 가져온다. • 키 3을 바로 6 옆에 놓을 수 없으므로 부노 노드에 있는 5를 끌어내리고 그 자리에 3을 놓는다. IT COOKBOOK IT COOKBOOK 15 1 2 5 6 9 10 16 18 20 21 24 25 26 19 22 3 8 9 삭제 재분배 (c) 계속 15 1 2 5 6 10 16 18 20 21 24 25 26 19 22 3 8 (d) 언더플로우!

§ 형제 노드가 여분의 키가 없으므로 병합한다.

• 형제 노드의 내용과 부모 노드의 키 하나를 내려 받아 행함

(28)

숙명여자대학교 멀티미디어과학과 15 1 2 5 6 8 10 16 18 20 21 24 25 26 19 22 3 언더플로우! 병합! 1 2 5 6 8 10 16 18 20 21 24 25 26 3 15 19 22 병합!

§ 병합에 키 하나(8)를 내준 부모 노드에서 다시

언더플로우 발생

• 앞서 발생한 언더플로우와 같은 문제이므로 재귀적으로 처리한다. • 부모 노드가 루트 노드이고 키가 하나밖에 없으므로 루트 노드는 키를 넘겨주고 없어진다. 56 -IT COOKBOOK IT COOKBOOK 한빛미디어㈜

다차원 검색 트리

• 검색 키가 두 개 이상의 필드로 이루어진 검색

– 복수 개의 필드를 그대로 검색에 사용하는 트리

• 3개의 다차원 검색트리와 하나의 다차원 저장/

검색 방법 소개

– KD-트리

– KDB-트리

– R-트리

– 그리드 파일

(29)

- 57 - 한빛미디어㈜

KD-Tree

• 각 레벨에서 필드를 번갈아 가며 검색에 사용

한다.

– 트리의 한 레벨에서는 하나의 필드만 사용한다.

• 레벨 0(루트 노드)에서는 필드 0만으로 분기 • 레벨 i에서는 필드 i(mod k)만으로 분기

– 총 k 개의 필드를 사용하는 검색이라면, k 개의 레벨

을 내려가면 검색에 사용하는 필드가 일치한다.

a

₀

a

₁

… a

_k-1

b

₀

b

₁

… b

_k-1

c

₀

c

₁

… c

_k-1

d

₀

d

₁

d

₂

…

r

₀

r

₁

…

r

_k-1

e

0

e

1

e

2

…

x

0

x

1

… x

k-1

…

레벨 0 레벨 1 레벨 2 레벨 k-1 레벨 k

KD-Tree

(30)

50

50 10 70

80

85

25

20

40

85

70

85

10

60 A

B

C

D

E

F

G

• KD-Tree에서의 삽입 예

– 삽입순서: A(50, 50), B(10, 70), C(80, 85), D(25, 20),

E(40, 85), F(70, 85), G(10, 60)

– 키가 두 개 이므로 레벨 별로 번갈아 사용하여

삽입한다.

숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 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 C 8085 25 20 D E 40 85 10 60 G 70 85 F

• KD-Tree 상의 각 노드는 다차원 공간의 한 점에 해당

– 한 노드에서 필드 x를 사용해 분기하는 것 è 그 노드가 속한 다차원 공간에 대해 공간을 둘로 분할하는 효과 – 검색을 통해 내려간다는 것 è 다차원 공간에서 이렇게 나누어진 결과에 대해 공간의 범위를 점점 좁혀나가는 것

(31)

• KD-Tree에서의 검색과 삽입

– 이진탐색트리에서의 검색/삽입 방법을 단순 확장

• KD-Tree에서의 삭제

– 이진탐색트리에서의 삭제를 신중하게 확장해야 함. – 삭제 노드 r이 몇 개의 자식을 갖느냐에 따라 • 자식이 없는 경우 – BST와 마찬가지로 노드 r만 제거하면 됨 • 자식이 하나뿐인 경우 – BST처럼 노드 r의 부모가 노드 r의 자식을 가리키게 하면, 노드 r의 자식 서브트리들의 레벨이 하나씩 올라가므로 각 레벨에서 사용하는 키가 달라져 문제가 발생 è 자식이 둘인 경우와 같은 방법으로 삭제해야 함. • 자식이 둘인 경우 – 노드 r의 오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드 값이 가장 작은 노드를 찾아 삭제하고, 그 노드를 노드 r 자리로 이동한다. IT COOKBOOK IT COOKBOOK 50 50 A 55 70 C 3055 B 65 20 E F 60 85 61 60 G 40 85 D 70 60 H 75 55 J K 70 75 6580 I 76 78 M 68 72 L 루트 노드 A를 삭제하고자 한다. 키 값을 (x, y)라 하자.

(32)

숙명여자대학교 멀티미디어과학과 50 50 A 55 70 C 3055 B 65 20 E F 60 85 61 60 G 40 85 D 70 60 H 75 55 J K 70 75 6580 I 76 78 M 68 72 L • A의 오른쪽 서브트리에서 x 값이 가장 작은 노드를 찾는다. • 노드 C의 x 값이 가장 작다. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 50 50 A 55 70 C 3055 B 65 20 E F 60 85 61 60 G 40 85 D 70 60 H 75 55 J K 70 75 6580 I 76 78 M 68 72 L • 노드 A에 노드 C를 옮겨 놓는다. • 이제 노드 C를 삭제해야 한다. è 재귀적으로 처리할 수 있음.

(33)

숙명여자대학교 멀티미디어과학과 55 70 C 3055 B 65 20 E F 60 85 61 60 G 40 85 D 70 60 H 75 55 J K ₇₀₇₅ 6580 I 76 78 M 68 72 L • C가 있는 레벨은 분기를 위해 y 값을 사용 • C의 오른쪽 서브트리에서 y 값이 가장 작은 노드를 찾으면 노드 L 이다. IT COOKBOOK IT COOKBOOK 68 72 55 70 C 3055 B 65 20 E F 60 85 61 60 G 40 85 D 7060 H 75 55 J K ₇₀₇₅ 65 80 I 7678 M L • L을 C의 빈자리로 옮긴다.

(34)

숙명여자대학교 멀티미디어과학과 68 72 55 70 C 3055 B 65 20 E F 60 85 61 60 G 40 85 D 7060 H 75 55 J K 70 75 65 80 I 7678 M L • L은 리프 노드였으므로 L이 위로 옮겨감으로써 영향을 받는 자식이 없다. • L에 대한 부모 노드의 연결만 NIL로 바꾼다. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 50 50 A 55 70 C 30 55 B 65 20 E F 60 85 61 60 G 40 85 D 7060 H 75 55 J K 70 75 6580 I 7678 M 68 72 L • KD-Tree에서 x 또는 y 값이 가장 작은 노드 찾기 – 여러 키를 사용하므로 BST 같이 쉽지는 않다. • 예) A의 오른쪽 서브트리에서 x 값이 가장 작은 노드 찾는 과정 – AàC로 오면: C의 서브트리는 모두 다 내려가 봐야 함 • 노드 C는 y 값에 의해 분기했으므로 C의 후손들의 x 값을 짐작할 수 없기 때문 • E의 오른쪽 서브트리는 E의 x 값보다 큰 x 값을 가지므로 볼 필요가 없다. • E의 왼쪽 서브트리를 확인한 다음, 55 보다 더 작은 x 값 노드가 없으므로 F로 간다. • F의 오른쪽 서브트리도 볼 필요가 없다.

(35)

KDB-Tree

• KD-Tree와 B-Tree의 특성 결합

– KD-Tree의 특성 • 다차원 key – B-Tree의 특성 • 디스크의 한 페이지가 한 노드와 일치 • Balanced tree

• 각 레코드는 k차원 공간에서 하나의 점에 해당

– 자신이 속한 공간을 담당하는 색인 node들을 따라감 IT COOKBOOK IT COOKBOOK

KDB-Tree의 Node들

• Internal node 하나는 k차원 공간에서 한 영역을

담당한다

– 루트 노드는 k 차원 공간 전체를 커버 – 이하의 노드들은 k차원 공간의 부분 영역을 담당 – 같은 level에 있는 모든 노드들은 서로 겹치는 영역이 없다 – 같은 level에 있는 모든 노드들의 담당 영역을 합하면 k차원 공간 전체가 됨 – Internal node는 따라서영역 노드라고 할 수 있다.

• 리프 노드는 데이터 페이지 정보를 저장

– 따라서 모든 리프 노드는 키 노드라고 할 수 있다.

(36)

숙명여자대학교 멀티미디어과학과 : 제외된 영역 : 점 (하나의 레코드 포인트) • 공간은 3개로 나누어져 3 개의 페이지가 각각 커버한다. • 각 페이지는 다시 복수 개로 나누어져 자식 페이지들이 나누어 커버한다. • 맨 아래 리프 노드들은 각각 한 영역을 커버하는데, 해당 영역에 속하는 키들의 정보가 들어 있다. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK

…

Disk의 한 페이지

(37)

KDB-Tree에서의 검색

• 루트 노드부터 시작해 해당 키가 포함되는 영역을 따라

리프 노드까지 내려간다.

– 키는 (x0, x1, …, xk-1)로 표현됨 – 각 노드의 영역들은 서로 겹치는 부분이 없으므로 키에 의해 도달하는 리프는 유일함. – 리프 노드에 해당 키의 (키, 페이지번호) 정보가 있으면 해당 페이지로 가서 레코드를 가져옴. – 도달한 리프에 해당 키의 (키, 페이지 번호) 정보가 없으면 검색 실패

• 영역 검색도 가능

– 키는 (<min0, max0>, < min1, max1 >, …, < mink-1, maxk-1 >)로

표현됨. IT COOKBOOK IT COOKBOOK

KDB-Tree에서의 삽입

• 삽입 과정

– 삽입할 키가 속하는 리프 노드를 찾는다. – 해당 리프 노드가 키를 더 수용할 수 있는 공간이 있으면, (키, 페이지 번호) 쌍을 삽입하고 끝냄. – 그렇지 않으면, 형제 노드와 재분배할 수 있으면 재분배함. – 재분배 불가능 시 리프 노드를 분할하여 두 개로 만듦 – 이에 따라 부모 노드에 있는 한 영역이 두 개로 나누어지므로 (영역, 페이지 번호) 쌍이 하나 늘어난다. – 부모 노드가 (영역, 페이지 번호)를 하나 더 수용할 수 있으면 삽입은 끝. – 그렇지 않으면 부모 노드를 분할해야 함.

(38)

숙명여자대학교 멀티미디어과학과 x의 자식 노드에서 분할 (a) 분할 전 (b) 노드 x 분할 후 x • 이 분할이 노드 x에서 오버플로우를 유발하면 노드 x도 분할해야 함. • 분할 시 자식 노드에서 분할을 위해 사용된 차원의 분할선을 노드 x 전체에 적용하여 자른다. • x의 부모 노드에서 x를 가리키던 (영역, 페이지 번호)를 두 개로 나누어야 함. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK

KDB-Tree에서의 삭제

• 삭제 과정: B-트리와 유사

– 언더플로우가 생기지 않으면 삭제 완료 – 언더플로우가 생기면, 이웃 영역과 경계를 재조정해서 재분배 – 재분배가 불가능하면 병합을 시도 – 병합은 부모 노드에서 (영역, 페이지 번호) 쌍 두 개가 하나로 통합된다. – 이로 인해 부모 노드에서 또 언더플로우가 생기면 재귀적으로 처리한다.

(39)

R-Tree

• 다차원 검색을 다룰 수 있도록 B-트리를 확장한 것

• 균형 잡힌 검색 트리

• R-Tree의 성질

– 루트를 제외한 모든 내부 노드는   ~ k개의 영역을 갖는다. – 모든 리프 노드는 같은 깊이를 가진다. – 모든 레코드는 리프 노드에서만 가리킴

• 다차원 도형의 저장 가능

– 점, 선, 면, 폐공간, 각종 도형

– MBR(Minimum Bounding Rectangle)로 근사

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

• R-트리로 구성하고자 하는 레코드들의 이차원 키 예

(40)

숙명여자대학교 멀티미디어과학과 1 2 3 4 5 6 7 8 9 10 11 12 120 110 100 90 80 70 60 50 40 30 20 10 A B D J C H L F E G K I

• 이차원 키들의 레코드를 이차원 공간에 표시한 예

숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 1 2 3 4 5 6 7 8 9 10 11 12 120 110 100 90 80 70 60 50 40 30 20 10 A B D J C H L F E G K I R1 R2 R3 R4 R5 R6 R7 E K A I C G D H B F J L R1 R2 R4 R5 R3 R7 R6 x • k=5, 즉 루트를 제외한 모든 노드는 2개 ~ 5개의 영역을 가지는 R-Tree 임. • 검색 • R-Tree는 한 노드에 있는 영역들이 서로 겹칠 수 있음 • 검색의 경로가 유일하지 않을 수 있음. 예) 레코드 E는 R4와 R5에 동시에 속한다.

(41)

숙명여자대학교 멀티미디어과학과 1 2 3 4 5 6 7 8 9 10 11 12 120 110 100 90 80 70 60 50 40 30 20 10 A B D J C H L F E G K I R3 R4 R5 R6 R7 E K A I C G D H B F J L R1 R2 R4 R5 R3 R7 R6 M N M N 레코드 삽입 과정 • 레코드 M은 R7에 속하는데 문제 없이 삽입됨. • 역시 R7에 속하는 N을 삽입하려하면 오버플로우 발생 IT COOKBOOK IT COOKBOOK 120 110 100 90 80 70 60 50 40 30 20 10 A B D J C H L F E G K I R1 R2 R3 R4 R5 R6 R7 E K A I C G D H B M J N L F R1 R2 R4 R5 R3 R7 R6 M N 레코드 삽입 과정(계속) • R6과 R7의 영역을 조정함으로써 두 리프에 속하는 키들을 재분배 • 노드에서 R6와 R7은 같은 이름으로 표현되었지만 실제 영역의 내용은 바뀌었다.

(42)

숙명여자대학교 멀티미디어과학과 1 2 3 4 5 6 7 8 9 10 11 12 120 110 100 90 80 70 60 50 40 30 20 10 A B D J C H L F E G K I R1 R2 R3 R4 R5 R6 R7 E K A I C G D H B M P J N L F R1 R2 R4 R5 R3 R7 R6 M N O P O Q Q y 레코드 삽입 과정(계속) • R7에 속하는 레코드 O와 R6에 속하는 레코드 P는 별 문제 없이 삽입 성공 • 여기세 R6에 속하는 레코드 Q를 또 삽입하면 오버플로우 발생 • 재분배를 시도했으나 형제 노드에 빈 공간이 없다. 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK 1 2 3 4 5 6 7 8 9 10 11 12 120 110 100 90 80 70 60 50 40 30 20 10 A C E G K I R1 R2 R3 R4 R5 R6 J N L F O D H P Q R1 R4 R5 R3 B M R7 R8

…

B D J H L F R2 R7 R6 M N O P Q R8 레코드 삽입 과정(계속) • 재분배 불가이어서 영역 R6를 둘로 분할하여 R6와 R8로 나누었다. • 만약 부모 노드에서도 오버플로우가 발생했다면 재귀적으로 처리한다.

(43)

숙명여자대학교 멀티미디어과학과 100 60 0 0 a(10, 50) b(10, 10) c(80, 10) e(60, 40) d(85, 45) f(30, 45) g(55, 5) h(80, 35) k(55, 45) i(65, 35) j(40, 15) l(25, 25)

Grid File

• 검색 트리가 아닌 일종의 저장 시스템

• 키의 내용에 따라 레코드가 저장된 곳을 “단번에”

알아낼 수 있도록 설계된 다차원 저장/검색 수단

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

(44)

숙명여자대학교 멀티미디어과학과 100 60 50 0 0 a(10, 50) b(10, 10) c(80, 10) a b d(85, 45) c d P2 e(60, 40) e 30 60 0 a(10, 50) b(10, 10) c(80, 10) a b P1 d(85, 45) c d P2 e(60, 40) e f 30 f(30, 45) (c) (d) 숙명여자대학교 멀티미디어과학과 IT COOKBOOK IT COOKBOOK P2 d e g c P3 100 60 50 0 0 a(10, 50) b(10, 10) c(80, 10) a b P1 d(85, 45) e(60, 40) f g(55, 5) P2 d e g c P3 30 f(30, 45) 60 0 a(10, 50) b(10, 10) c(80, 10) a b P1 d(85, 45) e(60, 40) f g(55, 5) h 30 f(30, 45) h(80, 35) (e) (f)

(45)

숙명여자대학교 멀티미디어과학과 100 50 75 0 0 a(10, 50) b(10, 10) c(80, 10) a b d(85, 45) e(60, 40) f g(55, 5) c g P3 h d P4 P2 i e 30 f(30, 45) h(80, 35) i(65, 35) 60 0 a(10, 50) b(10, 10) c(80, 10) d(85, 45) e(60, 40) g(55, 5) j(40, 15) j b P5 P1 f a h d P4 P2 i e g c P3 30 f(30, 45) h(80, 35) i(65, 35) (h) IT COOKBOOK IT COOKBOOK 100 50 75 0 60 0 a(10, 50) b(10, 10) c(80, 10) d(85, 45) e(60, 40) g(55, 5) j(40, 15) l j b P5 P1 f a h d P4 P2 k i e g c P3 30 f(30, 45) h(80, 35) i(65, 35) l(25, 25) k(55, 45) (i)

(46)

숙명여자대학교 멀티미디어과학과 50 75 30 1 2 5 3 4 3

• 일차 스케일링 배열

• 그리드 배열

Grid Configuration

92 -IT COOKBOOK IT COOKBOOK 한빛미디어㈜