I. B-Tree의 개념
가. B-Tree의 정의
- 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 이진트리의 확장형 트리구조
나. B-Tree의 개념도 및 설명
| 구 분 | 항 목 | 설 명 |
| 개념도 |  |
|
| 구조 | Root node | 최소 2개의 자식노드 보유, 최소 한 개의 값 보유 |
| Internal node | 최대 m개의 자식노드 보유(차수가 m일 경우) | |
| Leaf node | 최하위 노드는 동일레벨로 구현 | |
| 특징 | 자식노드 수 | 리프, 루트를 제외한 노드는 최소 m/2개의 자료 보유 |
| 균등 탐색 속도 | 최악의 경우가 존재하지 않아 시간복잡도는 O(logN)으로 일정 | |
| 효율성 | 자식노드를 많이 보유하여 트리의 높이가 줄어들어 효율성 확보 | |
| 정렬상태 | 각 노드에 입력된 자료는 정렬된 상태로 존재 | |
| 유형 | B+ Tree | 인덱스 세트(index set)와 순차세트(sequence set)로 구성된 트리 |
| B* Tree | 리프, 루트를 제외한 노드가 최소한 2/3가 채워지도록 제한한 트리 | |
- 중복된 자료는 입력 불가하며, 데이터 추가 및 삭제시 항상 Leaf노드에서 수행
II. B-Tree의 삽입 연산 설명 및 삽입과정 설명
가. B-tree의 삽입 연산 설명
| 구 분 | 항 목 | 설 명 |
| 기본연산 | Insert | 새로운 값은 항상 Leaf노드에 삽입 |
| 하향 탐색 | 새로운 값 추가시, 하향탐색하며 꽉찬 노드는 분할하며 진행 | |
| 분할연산 (Split) |
분할노드가 Root인 경우 |
Left child, Right child 생성후, 중앙값은 Root에, 나머지 값들은 자식노드에 분할하여 배치 |
| 분할노드가 Root가 아닌경우 |
- 왼쪽 노드는 이미 있는 노드이므로, 오른쪽 노드만 생성 - 이후, 중앙값을 부모에 삽입하고, 왼쪽과 오른쪽 노드로 분할 배치 |
- 분할해야할 경우를 Overflow라고 하며, 분할결과 부모노드도 Overflow발생시 분할 반복수행
나. 1, 2, 3, 4, 5, 6 순서대로 삽입되는 과정 설명
- Overflow 발생시 분할하여 부모노드에 배치
III. B-Tree의 삭제 연산 설명 및 삭제과정 설명
가. B-tree의 삭제 연산 설명
| 구 분 | 항 목 | 설 명 |
| 삭제 원칙 | 자료수 보장 | 삭제후 자료수가 M/2 이상이 되도록 보장해야하는 원칙 |
| Borrow node | - 형제노드가 M/2보다 많은 자료를 가지고 있을경우 빌려오기 수행 - 부모노드에서 빌려오고, 형제노드에서 부모노드로 이동 |
|
| Bind node | 형제노드에게서 빌려오기 불가시, 병합 수행 | |
| 삭제 연산 | 내부노드 삭제 | - 대체키를 찾아 Swap 연산 수행 - 대체키는 Left subtree중 가장 큰값이나, Right subtree중 가장 작은값을 이용 - 이후 대체된 값을 Leaf에서 삭제 수행 |
| Leaf노드 삭제 | 자료 삭제후, Balance를 위해 borrow 및 bind 연산 수행 |
- M/2보다 자료가 적을 경우를 underflow라고 하며, 이럴경우 balance 유지를 위한 연산 수행 필요
나. 3, 4, 5 순서대로 삭제되는 과정 설명
- 해당 과정에서는 Swap시 Right Subtree의 최소값을 이용
'ITPE > 자료구조' 카테고리의 다른 글
| 8-puzzle (A*) (0) | 2021.04.08 |
|---|---|
| MST(Minimum Spanning Tree) (0) | 2021.04.08 |