1. 이진 검색 트리
1.1 특성
a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다.
b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다.
1.2 검색
루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다.
1.3 삽입
실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다.
이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달라진다. n개의 원소로 이진검색트리를 만들면 최악의 경우라 하더라도 검색시간은 Theta(log n) 이다.
1.4 삭제
다음의 세가지에 따라 다르게 처리해 준다.(r: 삭제하고자 하는 노드)
a. case 1: r이 리프노드인 경우
r을 제거하고 r의 부모 노드가 r을 가리키고 있던 부분은 NIL로 바꾸어준다.
b. case 2: r의 자식 노드가 하나인 경우
r을 제거하고 r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 바꾸어준다.
c. case 3: r의 자식 노드가 두 개인 경우
트리내에서 r의 자리에 대신 놓아도 괜찮은 원소는 크기 순으로 r의 직전 원소 또는 r의 다음 원소이다. 이 원소를 r의 자리에 옮겨 놓는다. 이렇게 하면 자리를 옮겨간 원소의 자리가 비게 되는데 이 원소는 두개의 원소를 가질 수 없다. 이 경우는 앞의 case 1과 case 2의 경우가 되므로 그에 맞는 삭제작업을 해주면 된다.
2. 레드블랙트리
- 균형잡인 이진검색트리
2.1 특성
a. 루트는 블랙이다.
b. 모든 리프(NIL)는 블랙이다.
c. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
d. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
리프노드: 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프노드라 부른다.
2.2 삽입
a. 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드(x)의 색상을 레드로 칠한다.
b. x의 부모노드(p)가 블랙이면 삽입은 완료.
c. p가 레드인 경우 p의 부모노드를 p2라 하면 p2는 블랙이고 x의 형제노드도 블랙이다. p의 형제 노드(s)는 레드일수도 있고 블랙일 수도 있다.
- s가 레드인경우
p와 s의 색상을 레드에서 블랙으로 바꾸고 p2의 색상을 블랙에서 레드로 바꾼다. 만약 p2가 루트이면 다시 p2의 색상을 블랙으로 바꾸고 끝낸다. p2가 루트가 아니면 재귀적으로 다시 c부터 확인한다.
- s가 블랙인 경우
x가 p의 오른쪽 자식인 경우와 왼쪽 자식인 경우 나뉜다.
- 오른쪽 자식인 경우
p를 중심으로 왼쪽으로 회전하면 아래의 왼쪽 자식인 경우로 치환된다.
- 왼쪽 자식인 경우
p2를 중심으로 오른쪽으로 회전하고 p와 p2의 색상을 맞바꾼다. -> 문제 해결
왼쪽 회전: p의 오른쪽 자식(x)을 p2의 자식으로 놓고 p를 x의 왼쪽 자식으로 놓는다. -> 원래 x의 왼쪽 자식을 p의 오른쪽 자식으로 놓는다.
오른쪽 회전: p2의 왼쪽 자식(p)을 p2의 부모 노드의 자식으로 놓고 p2를 p의 오른쪽 자식으로 놓는다. -> p의 원래 오른쪽 자식을 p2의 왼쪽 자식으로 놓는다.
새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 새 노드의 아래쪽은 문제가 생길 것이 없다. 따라서 위쪽에 문제가 생기는 지를 확인한다. 이를 위해 새 노드의 부모 노드부터 확인하면서 문제를 해결하고 루트로 올라간다.
2.3 삭제
임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 오른쪽 서브트리에서 최소원소(노드 d의 직후원소)를 가진 노드 m의 키를 노드 d로 옮긴 다음 노드 m을 삭제한다.(최소원소 m은 최대 1개의 자식만을 가질 수 있다.) -> 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방
- 아래와 같은 세가지 경우가 나오게 된다.
a. m이 레드이면 삭제 후 아무런 조치가 필요없다.
b. m이 블랙이고 자식(x)이 레드이면 삭제 후 x의 색상을 블랙으로 바꾸어 버리면 된다.
c. m과 x의 색상이 모두 블랙인 경우 다음과 같이 두가지로 나눌 수 있다.
- p가 레드이고 s가 블랙인 경우
- p가 블랙인 경우
c의 경우를 설명하기 전에 우선 각각의 노드를 다음과 같이 명명한다:
- x의 부모노드 : p
- p의 다른 자식 노드 : s
- s의 자식 노드: l과 r
각각의 경우를 살펴보자.
2.3.1 p가 레드이고 s가 블랙
l과 r의 색상에 따라 세가지로 나뉜다.
a. (l,r) : (블랙, 블랙)
p와 s의 색상을 바꾼다.
b. (l.r) : (레드, 레드) 또는 (블랙, 레드)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> r의 색상을 레드에서 블랙으로 바꾼다.
c. (l,r) : (레드, 블랙)
s를 중심으로 오른쪽으로 회전 -> l과 s의 색상을 바꾼다. -> b로 이동
2.3.2 p가 블랙
p가 블랙이면 s는 블랙 또는 레드가 가능하므로 다음과 같은 네가지로 나뉜다.
a. (s,l,r) : (블랙, 블랙, 블랙)
s의 색상을 블랙에서 레드로 바꾼다. -> p를 문제발생노드로 하여 재귀적으로 다시 시작
b. (s,l,r) : (블랙, 레드, 레드) 또는 (블랙, 블랙, 레드)
2.3.1의 b와 같다.
c. (s,l,r) : (블랙, 레드, 블랙)
2.3.1의 c와 같다.
d. (s,l,r) : (레드, 블랙, 블랙)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> 2.3.1에서의 경우로 이동
3. B-트리
3.1 특성
a. 루트를 제외한 모든 노드는 최대 k개의 키를, 최소 k의 반이상의 키를 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
3.2 검색
이진검색트리에서의 검색과 같다.
3.3 삽입
a. x를 삽입할 리프 노드 r을 찾는다.
b. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
c. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘겨주면 된다. 이때 키를 바로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 키를 넘기고 비게된 부모 노드의 자리에 노드 r에 있던 키를 놓는다.
d. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 이렇게 되면 부모 노드에 키가 하나 더 필요하게 되므로 분할 할 노드에 있는 키 중 하나를 부모 노드에 넘긴다. 이 때 부모 노드가 여유가 없으면 재귀적으로 다시 분할을 시도한다. 상황에 따라 루트까지 분할이 이루어 질 수도 있다.
3.4 삭제
a. x를 키로 가지고 있는 노드를 찾는다.
b. 이 노드가 리프 노드가 아니면 x의 직후원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
c. 리프 노드에서 x를 제거한다.
d. x 제거 후 노드에 키가 모자르면 형제 노드를 살펴 키를 내 놓을 수 있는 노드가 있으면 키를 받는다. 이때 실제로는 삽입의 c에서처럼 형제 노드의 키를 바로 받을 수는 없고 형제 노드의 키를 부모 노드로 보내고 부모 노드의 키를 받아온다.
e. 형제 노드가 키를 내 놓을 여유가 없으면 병합을 한다. 병합은 형제 노드의 내용과 부모 노드의 키를 내려받아 행한다. 만약 이렇게 함으로서 부모 노드에 다시 키가 모자르게 되면 재귀적으로 d를 다시 실시한다.
4. KD-트리
4.1 특성
이진검색트리를 확장한 것으로 k개(>=2)의 필드로 이루어지는 키를 사용한다.
레벨 i에서는 필드 i(mod k)만으로 분기를 한다. - 루트노드는 첫번째 필드만 사용해서 분기하고 그 다음 레벨은 두 번째 필드만 사용해 분기를 하고... 이런 식으로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기를 한다.
4.2 검색
이진검색트리와 같이 하면 된다. 위에서 설명한 분기 방식에 따라 분기하면서 찾는다.
4.3 삽입
이진검색트리와 같이 하면 된다. 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거기에서 왼쪽 또는 오른쪽에 달아 준다.
4.4 삭제
노드 r을 삭제한다고 할 때 아래의 세 가지 경우로 나누어 볼 수 있다.
a. 자식이 없는 경우
이진검색트리와 마찬가지로 노드 r만 제거
b. 자식이 하나뿐인 경우
이진검색트리에서는 노드 r의 부도가 바로 노드 r의 자식을 가리키도록 하면 끝나지만 KD-트리에서는 이렇게 하면 분기에 사용하는 필드가 달라지므로 이렇게 하면 안된다. 자식이 둘인 경우와 같은 방법으로 삭제를 해야 한다.
c. 자식이 둘인 경우
오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드(s)를 찾아 삭제하고 그 노드를 노드 r의 자리로 이동한다. -> 이것은 s를 삭제하는 것과 같은 재귀적 작업이 된다.
최적화: 가장 작은 노드를 찾을 때 모든 서브트리를 찾을 필요는 없다. 같은 필드를 가지고 분기를 하는 레벨인 경우 거기에서의 값에 따라 왼쪽 또는 오른쪽만 찾으면 된다.
5 KDB-트리
5.1 특성
B-트리(각 노드가 키에 의해 분기)를 확장한 것으로서 각 노드가 영역에 의해 분기한다.
다음의 두 종류가 있다.
a. 영역 노드
복수 개의 (영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드다.
b. 키 노드
복수 개의 (키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드다.
5.2 검색
a. 키 검색: 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려간다.
b. 영역 검색: 루트 노드로부터 시작해 검색 영역과 겹치는 부분이 있는 노드는 모두 방문해 확인한다.
5.3 삽입 및 삭제
B-트리에서와 유사하게 한다.
6. R-트리
- B-트리를 확장
- KDB-트리에서는 노드들이 전체 공간을 나누어 커버하는데 반해 R-트리는 키들을 포함하는 최소 영역만 노드에 있다.
- KDB-트리처럼 두 종류의 노드가 있다.
a. 영역 노드: 복수 개의(영역, 페이지 번호)쌍으로 구성된다. 모든 내부 노드는 영역노드다.
b. 키 노드: 복수 개의(키, 페이지 번호)쌍으로 구성된다. 모든 리프 노드는 키 노드다.
- 다음의 성질을 만족한다.
a. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
c. 모든 레코드는 리프 노드에서만 가리킨다.
- 한 노드에 있는 영역들이 서로 겹칠 수도 있다.
- 삽입, 삭제는 B-트리에서와 유사하게 일어난다: 책 참조
7. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조
댓글 없음:
댓글 쓰기