쉽게 배우는 알고리즘

5장. 검색트리

5장. 검색트리

나는 보다 응용력 있는 유형의 수학이라는 이유 때문에 컴퓨터 과학을 하고 싶었다.

-로버트 타잔

학습목표

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

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

• 이진검색트리의 균형이 작업의 효율성에 미치는 영향 을 이해하고, 레드블랙트리의 삽입·삭제 작업의 원리 를 이해한다.

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

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

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

이해한다.

레코드 , 키, 검색트리

• 레코드 ^record

– 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위 – e.g., 사람의 레코드

• 주민번호, 이름, 집주소, 집 전화번호, 직장 전화번호, 휴대폰 번호, 최종 학력, 연소득, 가족 상황 등의 정보 포함

• 필드 ^field

– 레코드에서 각각의 정보를 나타내는 부분

– e.g., 위 사람의 레코드에서 각각의 정보를 나타내는 부분

• 검색키 search key 또는 키 key

– 다른 레코드와 중복되지 않도록 각 레코드를 대표할 수 있는 필드 – 키는 하나의 필드로 이루어질 수도 있고, 두 개 이상의 필드로

이루어질 수도 있다

• 검색트리 search tree

– 각 노드가 규칙에 맞도록 하나씩의 키를 갖고 있다 – 이를 통해 해당 레코드가 저장된 위치를 알 수 있다

Binary Search Tree (BST)

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

• 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식을 갖는다.

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

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

30

40 20

25

10 35 45

30

40

20

25 10

45

35

(a) (b)

BST의 예

30

40 20

25

10 35 45

20

25 10

40

45 35

(a)

(b) 노드 r의 왼쪽 서브트리

r

(c) 노드 r의 오른쪽 서브트리

BST에서의 검색

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: 검색하고자 하는 키

t

left[t] right[t]

검색에서 재귀적 관점

BST에서의 삽입

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;}

}

t : 트리의 루트 노드

x: 삽입하고자 하는 키

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에서의 삭제

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

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

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

t : 트리의 루트 노드

r: 삭제하고자 하는 노드

BST에서의 삭제

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 자리에 놓는다;

}

t : 트리의 루트 노드

r: 삭제하고자 하는 노드

BST에서의 삭제

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;

} }

t: 트리의 루트 노드 r: 삭제하고자 하는 노드 p: r의 부모 노드

55

28 8

15 60

90

48 30

18

38 3

50

(a) r의 자식이 없음 (b) 단순히 r을 제거한다

36

32 33

55

28 8

15 60

90

48 30

38 3

50

32 36 33

: Case 1

55

28 8

15 60

90

48 30 18

38 3

50

r

(a) r의 자식이 하나뿐임

55

28 8

15 60

90

18 48 3

50

(c)

자리에 r의 자식을 놓는다

36 32

33

38

32 36 33 55

8 28

60 15

90

48 18

38 3

50

(b) r

제거

32 36 33

삭제의 예 : Case 2

55

28 8

15 60

90

48

30

45 18

41

38 3

50

s

(a) r의 직후원소 s를 찾는다

36

32 33

55

30 8

15 60

90

48 45

18

41

38 3

s

50

(b) r을 없앤다

36

32 33

: Case 3

55

30 8

60 15

90

48 45

18

41 3

50

(d) s가 있던 자리에 s의 자식을 놓는다

38

36 32

33 55

30 8

60 15

90

48 45

18

41

38 3

50

(c) s를 r자리로 옮긴다

36

32

33

Red-Black Tree (RB Tree)

• BST의 모든 노드에 블랙 또는 레드의 색을 칠하되 다음의

레드블랙특성을 만족해야 한다

① 루트는 블랙이다

② 모든 리프는 블랙이다

③ 노드가 레드이면 그 노드의 자식은 반드시 블랙이다

④ 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다

 여기서 리프 노드는 일반적인 의미의 리프 노드와 다르다.

모든 NIL 포인터가 NIL이라는 리프 노드를 가리킨다고 가정한다.

NIL NIL

NIL 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가 레드인 경우만 고려하면 된다

RB Tree에서의 삽입

?

x

p s

p

주어진 조건: p is red

• p

와 x의 형제 노드는 반드시 블랙이다

• s의 색상에 따라 두 가지로 나눈다

– Case 1: s가 레드 – Case 2: s가 블랙

x

p s

x

p s

Case 1

^p

2

p

Case 1: s가 레드

: 색상이 바뀐 노드

 p

에서 방금과 같은 문제가 발생할 수 있다: recursive problem!

y

p

s p

x

x

p

1

s p

y

2

2

1

Case 2-1 Case 2-2로!

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

x

p s

x

p

s p

p

y y

Case 2-2

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

: 색상이 바뀐 노드

 삽입 완료!

RB Tree에서의 삭제

• 삭제 노드의 자식이 없거나 1개만을 가진 노드로 제한해도 된다

– 텍스트의 p.146의 첫 문단 참조 – 삭제 노드를 m이라 하자

• 삭제 노드가 레드이면 아무 문제 없다

• 삭제 노드가 블랙이라도 (유일한) 자식이 레드이면 문제 없다

x

x x

m x m

x m x

-1

?

x

-1

^?

s

? ?

l r

p

m 삭제 후 문제 발생

(레드블랙특성 ④ 위반) x의 주변 상황에 따라 처리 방법이 달라진다

p p

경로에서 블랙 노드의 수가 하나 모자람을 의미한다.

x

Case 1

-1

x

Case 2 -1

경우의 수 나누기

p is red p is black

x

s

l r

x

s

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

l r

Case 2-3

x

-1

s

p

l r

x

s

p Case 2-2

l r

Case 1-1

x

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

s

Case *-2 p

l r

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

Case 1-1 x

s

p

l r

x s

p

l r

각 경우에 따른 처리

 삭제 완료!

Case *-3 x

-1

s

p

l r

1

x

s

p

l

r

1 2 2

Case *-2로 1

x

-1

s

p

2 3

Case *-2

1

x

s

p

2 3

r

r

 삭제 완료!

x

-1

Case 2-4

s

l r x

-1

s

l

r

p

p Case 1-1, Case 1-2, Case 1-3 중의 하나로 p

x

-1

Case 2-1

s

l r

x

-1

s

l r

p

 p에서 방금과 같은 문제가 발생. Recursive problem.

재귀적으로 처리.

B-Trees

• 디스크의 접근 단위는 블록(페이지)

• 디스크에 한 번 접근하는 시간은 수십만 명령어의 처리 시간과 맞먹는다

• 검색트리가 디스크에 저장되어 있다면 트리의 높이를 최소화하는 것이 유리하다

• B-트리는 다진검색트리가 균형을 유지하도록 하여 최악의

경우 디스크 접근 횟수를 줄인 것이다

T ₀

key

key

key

… ^key

T ₁ T ₂ T ₃ … T _k

T _i

key _i-1 < < key _i

다진검색트리

B-Tree

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

– 루트를 제외한 모든 노드는 k/2 ~ k 개의 키를 갖는다

– 모든 리프 노드는 같은 깊이를 가진다

<key

, p

> <key

, p

> … ^<key

^{, p}

1

>

…

부모 노드의 페이지

B-트리의 노드 구조

<key

, p

> … <key

, p

> …

페이지 p_i

키 key_i를 가진 record

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

B-Tree에서의 삽입

BTreeInsert(t, x) {

x를 삽입할 리프 노드 r을 찾는다;

x를 r에 삽입한다;

if

then

}

clearOverflow(r) {

if

then

else

r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다;

if

} }

▷ t : 트리의 루트 노드

▷ x : 삽입하고자 하는 키

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에서 삽입의 예

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 삽입

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 삽입 분할!

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)

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

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

분할!

B-Tree에서의 삭제

BTreeDelete(t, x, v) {

if

x의 직후원소 y를 가진 리프 노드를 찾는다;

x와 y를 맞바꾼다;

}

리프 노드에서 x를 제거하고 이 리프 노드를 r이라 한다;

if

}

clearUnderflow(r) {

if

then

else

r의 형제 노드와 r을 합병한다;

if

then

} }

▷ t : 트리의 루트 노드

▷ x : 삭제하고자 하는 키

▷ v : x를 갖고 있는 노드

15

1 2 3 5 6 7 9 10 16 18 20 21 24 25 26 19 22

4 8

7 삭제

(a)

(b)

1 2 3 5 6 9 10 16 18 20 21 24 25 26 19 22

4 8

4 삭제

B-Tree에서 삭제의 예

15

1 2 3 6 9 10 16 18 20 21 24 25 26 19 22

5 8

언더플로우!

15

1 2 5 6 9 10 16 18 20 21 24 25 26 19 22

3 8

9 삭제

1 2 3 4 6 9 10 16 18 20 21 24 25 26 19 22

5 8

4 제거

재분배

15

1 2 5 6 10 16 18 20 21 24 25 26 19 22

3 8

(d)

언더플로우!

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

병합!

다차원 검색

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

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

– KD-트리 – KDB-트리 – R-트리

– 그리드 파일

KD-Tree

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

− 한 level에서는 하나의 필드만 사용한다

− 총 k 개의 필드를 사용하는 검색이라면, k 개의 level을

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

0

b

b ₁ … b

c

c ₁ … c

d

d

d ₂ …

r

r

… r _k-1

e

e

e ₂ …

… …

…

x ₀ x

… x

…

… …

레벨 1

레벨 2

레벨 k-1

레벨 k

KD-Tree

50 50

10 70 80 85

25 20 40 85 70 85

10 60

A

B C

D E F

G

A(50,50) B(10,70)

C(80,85)

D(25,20) E(40,85)

F(70,85)

G(10,60)

10 70

B C 80 85

25 20

D E 40 85

10 60 G

70 85

F

50 50 A

55 70 30 55 C

B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 68 72 M

L

50 50 A

55 70 30 55 C

B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 68 72 M

L

50 50 A

55 70 30 55 C

B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 68 72 M

L

50 50 A

55 70 C

30 55 B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 68 72 M

L

55 70 C

30 55 B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 68 72 M

L

68 72 55 70

C

30 55 B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 M

L

68 72 55 70

C

30 55 B

65 20

E F 60 85

61 60 G

40 85 D

70 60 H

75 55

J K 70 75

65 80 I

76 78 M

L

KDB-Tree

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

– KD-Tree의 특성

• 다차원 key

– B-Tree의 특성

• 디스크의 한 페이지가 한 노드와 일치

• Balanced tree

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

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

KDB-Tree의 Node들

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

– 루트 노드는 k 차원 공간 전체를 커버

– 이하의 노드들은 k차원 공간의 부분 영역을 담당

– 같은 level에 있는 모든 노드들은 서로 겹치는 영역이 없다 – 같은 level에 있는 모든 노드들의 담당 영역을 합하면 k차원

공간 전체가 됨

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

: 제외된 영역

: 점 (하나의 레코드 포인터)

x의 자식 노드에서 분할

(a) 분할 전

(b) 노드 x 분할 후

x

…

R-Tree

• B-트리의 다차원 확장

• 균형잡힌 검색트리

• 모든 레코드는 리프 노드에서만 가리킴

• 다차원 도형의 저장 가능

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

– MBR(Minimum Bounding Rectangle)로 근사

이름 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

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

D B

J C

H

L F

E G

K

I

120 110 100 90 80 70 60 50 40 30 20 10

A

D B

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

x

120 110 100 90 80 70 60 50 40 30 20 10

A

D B

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

120 110 100 90 80 70 60 50 40 30 20 10

A

D B

J C

H

L F

E G

K

I

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

120 110 100 90 80 70 60 50 40 30 20 10

A

D B

J C

H L

F

E G

K

I

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

O N

P

O Q

Q

y

120 110 100 90 80 70 60 50 40 30 20 10

A

C E

G

K

I

R3 R4 R5 R6

J N L F O

D H P Q

R1

R4

R5

R3

B M

R7 R8

…

D B J

H L

F R2

R7

R6 M

O N

P Q

R8

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

100 0

0

a(10, 50)

b(10, 10) c(80, 10)

30

60

0

a(10, 50)

b(10, 10) c(80, 10)

a b

P1

d(85, 45)

c d

P2

30

(b)

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)

P2 d

e

g c

P3 50 100

0

0

a(10, 50)

b(10, 10) c(80, 10)

d(85, 45) e(60, 40)

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)

(f)

50 75 100 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)

50 75 100 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)

50 75 30

1 2 5 3

4

3

Thank you