B-tree 삭제(Deletion) 알고리즘 (Redistribution/Merge 알고리즘)

※ 삭제(Deletion) 알고리즘

• (0) 삭제하고자 하는 key값을 가진 노드 탐색
• (1-1) 찾은 노드가 단말 노드라면 단말 노드에서 해당 레코드를 삭제
• (1-2) 찾은 노드가 단말 노드가 아니라면
•      ① 삭제될 record의 오른쪽 포인터가 가리키는 sub-트리에서 가장 작은 key값을 가지는 record를 찾음.
•      ② 삭제될 레코드의 key값과 찾은 record의 key값을 교환하고 단말노드로 옮김.
•      ③ 단말 노드에서 해당 record를 삭제
• (2) record 삭제 후 남아있는 record의 수가 노드가 유지될수 있는 최소한의 수(d개) 미달이면 underflow상황을 처리한다.
•    (2-1) Redistribution(재분배)가 가능(=최소 record 수 이상을 포함한 형제 노드에서 이동) (즉, fiil_cnt > d)
•    (2-2) Redistribution(재분배) 불가능 시 Merge(합병) 사용 (즉, fill_cnt <= d)
• (3) merge에 의해 루트 노드가 NULL이 되면 merge에 의해 새로 만들어긴 노드가 루트노드가 된다. (= Tree의 높이 감소)

▶항상 삭제가 이루어진 뒤 남아있는 record들은 shift를 통하여 노드의 왼쪽 빈공간부터 채워넣어 배열되어야 한다.

 

 

■Redistribution(재분배)

현재 curr 노드에서 rec 하나가 삭제된 후 underflow 상황 발생

curr노드의 형제노드의 record수가 (d+1)개로 Redistribution(재분배) 가능

Redistribution(재분배)을 실행할 때에도 삽입 때와 같이 big node를 사용해서 이루어진다.

big node의 curr노드의 record와 parent노드의 record, 형제 노드의 record를 넣고 center record는 parent 노드로 가고 left는 curr 노드로, right는 형제 노에 넣어준다.

 

 

※ Merge(합병)

 

key값이 삭제된 이후, 형제노드를 탐색해서 Retribution(재분배)을 할 수 없을 경우 Merge(합병)을 이용해야한다.

Merge(합병)을 통해서 curr 노드의 record와 parent노드의 record, 형제 노드의 record를 모두 curr 노드에 넣는다. 이후, 형제노드는 삭제한다.

[1] Merge(합병)을 사용해야 한다고 판단한다.

[2] parent노드의 해당 record를 curr 노드에 넣는다.

[3] 형제 노드의 record를 curr노드에 넣는다.

[4] parent노드에서 해당 record를 삭제하고 형제 노드를 삭제한다.

[5] shift를 통해 노드의 record들을 정리한다.

 

---

★code

1. 삭제

// B_tree_Deletion.c

#include "functions.h"

void B_tree_Deletion(nptr_pck package, char CompName[])
{
nodeptr* Root = package->Root;
nodeptr curr = *Root;

stack stk = NULL;
stack temp_stk = NULL;
stk_pck stk_SET = (stk_pck)malloc(sizeof(stk_pck_rec));

int rdst_cnt = 0;
int mrg_cnt = 0;

del_pck del_SET = (del_pck)malloc(sizeof(del_rec));

int del_node_loc = -1;

int i = 0;

stk_SET->stk = &stk;
stk_SET->temp_stk = &temp_stk;

del_SET->rdst_cnt = &rdst_cnt; //재배열 카운트
del_SET->mrg_cnt = &mrg_cnt; //합병 카운트

if (!curr) {
printf("\tB-tree가 비어있습니다.\n");
return;
}

del_node_loc = leaf_n_del_node_finding(&curr, CompName, stk_SET, 'd'); //탐색 함수 호출.

if (del_node_loc == FALSE) { //찾으려는 값이 존재하지 않을 경우
printf("\t%s 레코드가 존재하지 않습니다.\n", CompName);
return;
} // if ()

// Comes here when the key is found. It is in curr's node.
// curr node is not a leaf node
if (curr->ptr[0] != NULL) { //curr가 리프노드가 아닐 경우
// We need to find successor of out_key
del_node_loc = successor_node_finding(&curr, stk_SET, del_node_loc);

// s를 d가 있던 위치에 넣은 후이므로,

// s를 지우고 정리해야함
leaf_del_arranging(&curr, del_node_loc);
} // if (curr->ptr[0])

 

else {
leaf_del_arranging(&curr, del_node_loc); //삭제 함수 호출
} //else

balancing_after_del(package, &curr, stk_SET, del_SET);

free(stk_SET);
free(del_SET);

printf("\t%s 레코드 삭제를 완료하였습니다.\n", CompName);
printf("\t삭제 과정에서 redistribution %d번, merging %d번 일어났습니다.\n", rdst_cnt, mrg_cnt);

}