[자료구조] B-Tree & Set ADT

기존 Binary Search Tree의 문제점

기존 BST는 균형이 맞는다는 가정 하에 logN의 시간에 탐색이 가능하다는 장점이 있었지만, 특정 조건 [ex) 일렬로 정렬된 경우]에서 O(n)의 시간복잡도를 갖게 되는 문제점이 발생하기도 한다. 

이를 해결하기 위한 Search Tree중 하나가 B-tree다.

 

B-Tree 규칙

B-tree는 아래의 규칙을 만족하여야 한다

 

1. root Node는 최소 하나의 요소를 갖을 수 있다. 이외 모든 다른 Node는 최소 MINIMUN의 요소를 갖어야 한다.

* MINIMUN : B-트리를 설계할 때 정해둔 최소 허용 요소 수를 의미하며, 보통 B-트리 차수(order) m에 대해 ⌈m/2⌉−1 또는 ⌈m/2⌉처럼 정의한다.

** 여기서 차수 M이라는 것은 한 Node안에 들어갈 수 있는 최대 요소의 수를 의미한다.

 

2. 하나의 노드가 가질 수 있는 최대 요소 수는 M개이다.

 

3. 각 B-Tree Node안의 요소들은 부분적으로 채워진 배열에 저장되며, 이 배열 안에서는 가장 작은 값부터 큰 값까지 순차적으로 정렬되어 있다.

 

4. Node 안에 K개의 요소가 저장되어 있으면, 그 Node에는 K+1개의 자식 포인터가 존재해야 한다.

 

5. 모든 non-leaf Node에 대해 다음 두 조건이 성립한다.

•    인덱스 i에 있는 요소는, 각 Node의 i번째 subtree에 있는 모든 요소들보다 크다.
•    인덱스 i에 있는 요소는, 각 Node의 (i+1)번째 subtree에 있는 모든 요소들보다 작다.

6. 모든 leaf node는 같은 깊이를 갖는다.

 

Set ADT with B-Tree

Set은 중복을 제외하는 자료 구조이다. 이를 B-Tree를 이용해서 구현하기 위해서는 아래와 같은 특징을 갖게 하면 된다.

• Set에 속하는 모든 원소들은 B-Tree 구조 안에 저장되며, B-Tree를 정의하는 여섯 가지 규칙을 모두 만족해야 한다
• 트리의 루트 Node(root) 에 들어있는 원소(key)의 개수는 dataCount라는 변수에 저장한다,
• 루트 Node 아래에 연결된 서브트리(child subtree)의 개수는 childCount라는 변수에 저장한다.
• 루트 Node의 요소는 실제로  data[0]부터 data[dataCount -1]까지 연속해서 저장한다.
• 자식 Node에 대한 포인터는 subset[0]부터 subset[childCount-1]까지 저장한다.

 

Element Search하기

B-Tree는 차수 M을 갖을 때 총 M+1개의 상태로 구분할 수 있다.

만약 상위 Node가 [a,b]로 이루어져 있다고 하면 찾는 목표 x는 (x<=a),(a<x<b),(b<=x) 세가지 상태로 관리할 수 있다.

BST의 경우처럼

만약 현재 node의 안에 target x가 존재하면 true를 반환하면 되고,

현재 node가 leaf node가 아닌데 존재하지 않는 경우에는 node 내부의 요소와 비교해서 상태와 맞는 자식 node로 이동하여 탐색을 진행한다.

만약 현재 node가 leaf node인데 존재하지 않는다면 false를 반환하면 된다.

 if (we found the target at data[i])
 	return true;
 else if (the root has no children)
 	return false;
 else
 	return subset[i].contains(target);

 

대략 이런식으로 의사코드를 작성할 수 있다.

시간복잡도의 경우 항상 모든 leaf node의 depth가 같으므로 O(logN)의 시간복잡도를 보장한다.

13을 찾는 예시

 

Element 추가하기

먼저 해당 요소를 삽입하고자 하는 요소의 위치를 위에서 설명한 Search를 통해 찾는다.

만약 중복되는 값이 없다면 탐색을 마친 위치에 값을 추가해준다.

만약 요소의 개수가 Node의 허용 범위를 넘어선다면 가운데를 기준으로 양쪽으로 분할하고, 가운데 노드는 상위 level로 승격시킨다.

11을 추가하는 예시

최종 Tree의 모습

Element 삭제하기

1. Leaf Node에서 삭제하고 재조정 할 필요가 없는 경우

그냥 삭제하면 끝이다.

 

2. leaf Node에서 삭제하고 재조정 해야 하는 경우

2-1) key 수가 여유 있는 형제의 지원을 받을 수 있는 경우

형제 노드의 하나를 부모 노드로 보내고 target을 제거하고 부모 Node로부터 하나를 내린다.

25를 제거하고 형제 노드에서 19을 지원받는 예시

 

2-2) key 수가 여유 있는 형제의 지원을 받을 수 없는 경우

형제의 지원을 받을 수 없는 경우 부모의 지원을 받고 형제와 합친다.

28을 제거하고 부모노드와 형제노드의 요소를 합치는 예시

 

2-3) 재조정 진행한 후 부모 노드에서도 문제가 발행하면 

2-3-1) 부모 Node가 Root Node가 아니라면

그 위치에서 다시 재조정 진행

2-3-2) 부모가 Root Node고 비어있다면

부모 Node를 삭제하고 직전에 합쳐진 Node를 Root Node로 만든다.

자식 Node를 제거하고 root Node가 되는 예시

3. 내부 Node에서 데이터를 삭제하는 경우

leaf Node에 있는 데이터와 위치를 바꾼 후 Case 2의 경우와 동일하게 진행한다.

내부 Node인 24를 제거하는 예시