[알고리즘] 『B-트리 특성, 검색, 삽입, 삭제』 에 대하여

소개글

[알고리즘] 『B-트리 특성, 검색, 삽입, 삭제』 에 대하여에 대한 보고서 자료입니다.

목차

(1) B-트리 특성
(2) B-트리에서의 검색
(3) B-트리에서의 삽입
(4) B-트리에서의 삭제
(5) 실행화면

본문내용

개수
x <- root;
do {
i<-1;
n<-x.n;
while(i<=n && key > x.kKi) // 노드를 찾는 루프
i<-i+1;
if(i<=x.n && key = x.Ki)
then return Ai; // 레코드의 주소를 반환
}
while ( ( x<-x.Pi-1) != null ) //포인터의 값이 널이 아닐 때
return null; // key와 일치하는 rqkt이 트리에 없는 경우
end searchBT()
(3) B-트리에서의 삽입
B-트리에서 새로운 키 값은 항상 리프노드에 삽입된다. 하지만, 삽입해야 되는 리프 노드에 키 값을 삽입할 수 있는 여유 공간이 있느냐 없느냐에 따라 두 가지 경우가 발생한다.
가. 빈공간이 있는 경우
새로운 키 값을 단순히 순서에 맞게 삽입
나. 빈공간이 없는 경우
노드에서 오버플로우(Overflow)가 발생한 경우, 노드를 두 개의 노드로 분할한다. 해당 노드의 키 값에 새로운 키 값을 삽입했다고 가정하고 삽입 결과의 중간 키 값. 즉, (m/2)번째의 키 값을 중심으로 왼편 작은 키들은 해당 노드에 그대로 남겨 두고 오른 편 큰 키들은 새로운 노드에 저장한다. 그리고 중간 키 값은 분할된 노드의 부모 노드로 올라가 삽입된다.
- 삽입 알고리즘
/* 사용된 변수들
In-key : B-트리에 삽입될 키
Finished : 삽입이 완료되었음을 나타내는 flag
Found : B-트리에서 레코드가 발견되었음을 나타내는 flag
P : 노드에 대한 포인터
Bignode : 오버플로우 노드를 위한 변수
N : 키 카운터
*/
// 노드의 주소를 스택에 저장하면서 In-key가 삽입될 위치를 탐색한다.
Found = false;
read root; // 루트를 읽는다
do {
N = number of keys in current node; // 현재노드안의 키 숫자
if (n-key == key in current node) found true; // 중복삽입허용안됨,
// n키가 현재노드의 키일 때
else if (In-key < key1) P = Po;
else if (In-key < keyN) P = PN;
else P = Pi-1; // for some i where keyi-1 < In-key < keyi
if (P != null) {
push onto stack address of current node; // 단순삽입
read node pointed to by P;
}
while (!Found && P is not null); // 레코드가 발견되지 않고 포인터가 널이 아닐 때
if (Found) report In-key already in tree;
else { // In-key를 B-트리에 삽입한다
P=null;
Finished = false;
do { if (current node is not full)
{
put In-key in current node; // 노드 안에서 키 순서를 유지하도록 키를 정렬한다.
Finished = true;
} else { // 노드가 꽉 차있다면
copy current node to Bignode; // Bignode에 현재노드를 복사
insert In-key and P into Bignode;
In-key = center key of Bignode;
current node = 1st half of Bignode; // 분할
get space for new node, assign address to P; // 주소 할당
new node = 2nd half of Bingnode;
if (stack not empty) // 스택이 꽉차있지 않으면
{
pop top of stack;
read node pointed to;
} else // 트리의 레벨이 하나 증가한다
{ get space for new node;
new node = pointer to old root, In-key and P;
Finished = true;
}
}
} while (!Finished);
(4) B-트리에서의 삭제
먼저 삭제하려는 키 값이 들어 있는 노드를 탐색하는 것부터 시작한다. 삭제하려는 키 값이 내부노드에 있다면 리프 노드에 있는 키 값의 후행(successor) 키 값과 교환을 한 뒤에 리프 노드에서부터 삭제한다. 왜냐하면 리프 노드에서의 삭제연산이 훨씬 더 간단하기 때문이다. 만일 삭제 결과로 노드가 유지해야 될 최소 키 값 수(즉, (m/2)-1)보다 작게 되면 언더플로우(underflow)가 일어나게된다. 이 경우 재분배나 합병을 이용하여 최소 키 값 수를 유지해야 한다.
① 재분배
해당 노드의 오른쪽이나 왼쪽 형제 노드에 최소 키 값 수보다 많은 키 값들이 있는 노드를 선택하여 그 노드로부터 한 개의 키 값을 차출하여 이동시키는 방법
트리 구조를 변경시키니 않는다.
② 합병
재분배 방법이 불가능할 때, 형제 노드들이 최소의 키 값만을 가지고 있는 경우에 적용.
해당 노드에 오른쪽(또는 왼쪽) 형제 노드에 있는 키 값들과 이 두 노드를 분리시키는 부모 노드의 키 값을 모두 모으는 작업. 공백이 된 노드는 제거한다. 하지만, 트리의 구조가 변경
기존의 루트 노드까지 삭제되어 트리의 높이를 한 레벨 감소시킬 수도 있다.
- 삭제 알고리즘
/* 사용된 변수
Finished : 삭제가 완료되었음을 나타내는 flag
Tempnode : 재분배를 위해 사용되는 정상 노드보다 큰 노드
Sibling : 인접 형제 노드
D-key : B-트리에서 삭제될 키
*/
search tree for D-key forming stack of node addresses;
if (D-key is not in terminal node) { // 만약 삭제될 키가 마지막 노드 안이 아니면
serach for successor key of D-key at terminal level (stacking node addresses);
copy successor over D-key;
termianl node successor now becomes the D-key;
Finished = false; // 키를

키워드

B트리,   비트리,   B-트리,   비주얼베이직,   알고리즘,   프로그램소스,   B-tree,   Btree