'ITPE > 자료구조' 카테고리의 다른 글

MST(Minimum Spanning Tree)  (0) 2021.04.08
B tree  (0) 2021.04.07

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

'ITPE > 자료구조' 카테고리의 다른 글

8-puzzle (A*)  (0) 2021.04.08
B tree  (0) 2021.04.07

 

 

 

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

+ Recent posts

티스토리툴바