지난 4주간 아래에 해당하는 문제를 150문제 이상 풀었다.
나는 여기 오기 전까지 알고리즘 문제를 풀어본 적이 없어서, 개념들을 다 집어 넣으면서 문제를 풀다보니 쉽지 않았다. 아직 개념도, 구현도 많이 부족하지만 알고리즘과 친해지는 시간이었다. 이번 5주차 주제는 'B-tree 및 B+tree 프로젝트'인데, c언어도 한 번도 경험해보지 못한 상태에서 1주일 만에 구현하는 것이 가능할까.. 생각했지만 B-tree는 계획대로 구현을 성공했다! (정말 유섭이와 정서에게 큰 감사를...)
팀원들을 잘만나서 순항하고 있지만 아직 c언어랑도 친하지 않아서 B-tree에 대해 100% 이해했다고 보기 힘들다. 다시 한 번 여기 정리하면서, 개념을 탄탄히 해보자.
B-tree는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다. 다른 여러 트리구조가 있지만, 다음과 같은 특성 덕분에 디스크 접근 횟수를 줄여서 연산 속도를 빠르게 할 수 있다.
- B-tree 노드의 키(key) 개수는 수백, 수천 개까지 가질 수 있다.
- B-tree 노드의 자식노드는 부모의 키(key) 개수 +1이다.
- 모든 리프(leaf)노드는 깊이가 같다.
* 리프(leaf)노드 : 자식이 없는 노드
연산의 속도를 크게 좌지우지하는 디스크 접근 횟수를 최소화 하기 위해, 노드의 키 개수와 자식 개수를 크게 만들어 활용한다고 생각할 수 있다.
보통 루트(root) 노드는 메인메모리(ram)에 있고, 그 아래 노드들에 접근하기 위해 디스크 접근을 한다고 생각해라.
B-tree의 각 노드에는 키(key)정보와 그 자식노드를 가리키는 포인터 정보가 들어있다. 또, leaf노드 정보도 들어있다.
B-tree인 T는 아래와 같은 특징이 있고, T.root를 루트 노드로 가진다.
- 모든 노드 안에 키는 오름차순으로 정렬돼있다.
- 노드의 각 키는 서브 트리(자식 노드들)에 저장되는 키들의 범위를 분할한다. 즉, 아래와 같은 의미인데 그림으로 보면 이해가 쉬울 것이다.
- 노드의 키 개수는 t-1개 이상, 2t-1개 이하이다. 즉 최소 t-1개, 최대 2t-1개의 키 개수를 갖는다.
우리는 Introduction to algorithms 책을 기반으로 구현 했다.
검색 : 아래 의사코드를 통해 구현했는데, 검색은 x노드에 있는지 없는지 확인하고 있으면 해당 값들을 리턴해주면 된다.
삽입 : 삽입은 여러 단계에 걸쳐 일어난다고 이해해야 한다.
2-1. 빈 트리 생성 : 아무 것도 없는 상태에서 첫 원소(?)를 삽입하기 전에 빈 트리를 생성한다.
2-2. 삽입하기(Main 함수) : 이 때, 루트(root) 노드가 꽉 찼는지 유무에 따라 2-3과 2-4를 실행한다.
2-3. 꽉 찬 노드 쪼개주기 : 삽입하려는 곳의 노드가 꽉 차 있을 경우(키의 개수가 2t-1)에 이 함수를 실행한다.
2-4. 꽉 차지 않은 리프(leaf)노드에 원소 삽입하기 : 2-2와 2-3에 의해, 꽉 차지 않은 노드가 확보된 경우에 바로 원소를 삽입한다.
책에 삽입에 대한 의사코드가 나와 있어, 비교적 수월(?)하게 할 수 있었다.
(유섭이가 삽입에 대한 개념을 정리하며 설명해준 기록)
삭제 : 문제는 삭제였는데, 책에 의사코드가 없어서 설명을 토대로 구현을 시도해보았다.
아래에서 'k'는 지우고자 하는 값, 'x'는 노드이다. 'i'는 'k'와 연관된 index라고 생각하면 된다.
3-1. x가 root노드가 leaf노드 일 때와 아닐 때를 나누어 생각 : x가 leaf노드이면, 쉽게 삭제하거나 삭제할 값이 없다고 리턴하면 된다. x가 leaf노드가 아닐 경우에는 x의 키 개수를 생각해줘야 한다.
3-1-1. x의 키 개수가 1이 아닐 때 : 이 때는 3-2나 3-3에서 해결할 수 있게 재귀함수를 활용해준다.
3-1-2. x의 키 개수가 1일 때 : 이 때, 유의해야 하는데 x의 키 개수가 1이면서 x[i]의 자식 2개 모두 빈곤(키 개수 t-1)할 경우 큰 변화가 일어난다.(루트 노드 변화, 양 자식들 합치기 등)
3-2. k가 x에 있을 때 삭제 : x[i]의 자식노드 2개를 확인한다.
3-2-1. 둘 중 하나라도 빈곤(키 개수 t-1)하지 않으면 그 쪽으로 내려가서 삭제할 값을 찾는다.
3-2-2. 둘 다 빈곤할 경우, 왼쪽 노드에 오른쪽 노드를 합친다. 그 사이에는 k가 들어간다.
3-3. k가 x에 없을 때 삭제 : 이 때는, k가 있는 쪽으로 x.c[i]를 정한다.
3-3-1. x.c[i]가 빈곤하지 않을 때, 재귀함수 활용하여 삭제한다.
3-3-2. x.c[i]가 빈곤한데, 형제노드(x.c[i-1] or x.c[i+1])가 빈곤하지 않을 때는 빈곤하지 않은 형제에서 키를 빌려온다. 빌려올 때는, 부모의 관련 키가 내려오고 형제노드의 키는 부모노드로 올라간다.
3-3-2. x.c[i]가 빈곤한데, 형제노드들도 다 빈곤하면 형제노드 중 하나와 병합한다. 이 때, 부모에 있던 관련 키는 병합한 노드의 중앙값이 된다.
위처럼 길게 말로, 설명해봤다. 위의 말들을 팀원들과 직접 손으로 짜보면서 코드를 짜봤다. 색다른 경험이었다. 팀원들이 많이 설명해줘서 그나마 따라가고 있다. 정말 고맙다....
내 멋대로의 언어로 정리한 것이고 틀린 부분이 있을 수 있다. 그렇지만 미래의 나를 위해 남겨본다..
아래는 우리 팀이 짠 코드이다.
/*
* Btree example
*
*
* 20210109, youseop, jeongseo, gojae
*
*
*/
/*
*
* 1. 모든 리프노드는 트리 높이(h)와 같은 깊이에 있다.
* 2. t-1 <= 키의 개수 <= 2t-1
* 2-1 루트 노드의 키의 개수는 t-1개 보다 적을 수 있다.
* 3. 리프 노드가 아닐 경우, 키의 개수 +1개 = 자식의 개수 <= 2t
*
*/
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define DEGREE 2 /*The degree of the tree.*/
typedef struct node
{
int key[2 * DEGREE - 1];
struct node* child[2 * DEGREE];
int leaf;
int n; //Length
}
node;
typedef struct B_Tree
{
node* root;
}B_Tree;
void B_Tree_Create(B_Tree* T);
void B_Tree_Insert(B_Tree* T, int k);
void B_Tree_Insert_Nonfull(node* x, int k);
int B_Tree_Search(B_Tree* T, int k);
int B_Tree_Search_Main(node* x, int k);
void B_Tree_Split_Child(node* x, int i);
void B_Tree_Display(B_Tree* T);
void B_Tree_Display_Main(node* x, int h);
void B_Tree_Delete(B_Tree* T, int k);
void B_Tree_Delete_main(node* x, int k);
int Find_Successor(node* x);
int Find_Predecessor(node* x);
void B_Tree_insert_items(B_Tree* T, int x, int y);
int main()
{
B_Tree* T = malloc(sizeof(B_Tree));
B_Tree_Create(T);
// node* xx = malloc(sizeof(node));
// xx->key[0] = 2;
// xx->n = 1;
// xx->leaf = 0;
// T->root = xx;
// node* yy = malloc(sizeof(node));
// node* z = malloc(sizeof(node));
// yy->key[0] = 1;
// yy->n = 1;
// yy->leaf = 1;
// z->key[0] = 3;
// z->n = 1;
// z->leaf = 1;
// xx->child[0] = yy;4
// xx->child[1] = z;
int command, x, y;
printf("##########################\n\n $ B_TREE Project $ \n\nproduced by \n\n@jeongseo \n@youseop \n@gojae\n\n##########################\n\n");
while (1) {
printf("\n1: insert one item\n2: insert items (x~y)\n3: delete item\n4: display\ncommad: ");
scanf("%d",&command);
if (command == 1) {
printf("insert item: ");
getchar();
scanf("%d", &x);
B_Tree_Insert(T, x);
B_Tree_Display(T);
}
else if (command == 2) {
printf("\ninsert x & y\n (y should be bigger than x)\nx: ");
getchar();
scanf("%d", &x);
printf("y: ");
getchar();
scanf("%d", &y);
B_Tree_insert_items(T, x, y);
}
else if(command == 3) {
printf("\ninsert a number you wanna delete.\nk : ");
getchar();
scanf("%d", &x);
B_Tree_Delete(T, x);
B_Tree_Display(T);
}
else if (command == 4) {
B_Tree_Display(T);
}
else if (command == 0) {
break;
}
getchar();
}
free(T);
}
void B_Tree_insert_items(B_Tree* T, int x, int y) {
for (int i = x; i < y+1; i++) {
B_Tree_Insert(T, i);
}
B_Tree_Display(T);
}
void B_Tree_Create(B_Tree* T)
{
node* x = malloc(sizeof(node));
if (x == NULL) {
printf("memory allocation falied");
return;
}
x->leaf = TRUE;
x->n = 0;
T->root = x;
}
void B_Tree_Insert(B_Tree* T, int k)
{
node* r = T->root;
if (r->n == 2 * DEGREE - 1)
{
node* s = malloc(sizeof(node));
if (s == NULL) {
printf("memory allocation falied");
return;
}
T->root = s;
s->leaf = FALSE;
s->n = 0;
s->child[0] = r;
B_Tree_Split_Child(s, 0);
B_Tree_Insert_Nonfull(s, k);
//printf("insert %d\n", k);
}
else
{
B_Tree_Insert_Nonfull(r, k);
}
}
void B_Tree_Insert_Nonfull(node* x, int k)
{
int i = x->n;
if (x->leaf)
{
i--;
while (i >= 0 && k < x->key[i])
{
x->key[i + 1] = x->key[i];
i--;
}
x->key[i + 1] = k;
x->n = x->n + 1;
}
else {
while (i >= 1 && k < x->key[i - 1])
{
i--;
}
if ((x->child[i])->n == 2 * DEGREE - 1)
{
B_Tree_Split_Child(x, i);
if (k > x->key[i]) {
i++;
}
}
//printf("child#: %d k: %d\n", i, k);
B_Tree_Insert_Nonfull(x->child[i], k);
}
}
int B_Tree_Search(B_Tree* T, int k)
{
node* r = T->root;
return B_Tree_Search_Main(r, k);
}
//함수 수정 필요!
int B_Tree_Search_Main(node* x, int k)
{
if (x->leaf)
{
int i = x->n - 1;
while (i >= 0 && k < x->key[i])
{
i--;
}
if (x->key[i] == k)
{
printf("There is data\n");
return TRUE;
}
else
{
printf("No data\n");
return FALSE;
}
}
return 0; // error 발생해서.. 넣었음(non-void function does not return a value in all control paths [-Wreturn-type])
}
void B_Tree_Split_Child(node* x, int i)
{
node* z = malloc(sizeof(node));
if (z == NULL)
{
printf("memory allocation falied");
return;
}
node* y = x->child[i]; // 0 <= i
z->leaf = y->leaf;
z->n = DEGREE - 1;
for (int j = 0; j < DEGREE - 1; j++)
{
z->key[j] = y->key[j + DEGREE];
}
if (y->leaf == FALSE)
{
for (int j = 0; j < DEGREE; j++)
{
z->child[j] = y->child[j + DEGREE];
}
}
y->n = DEGREE - 1;
for (int j = x->n; j > i; j--)
{
x->child[j + 1] = x->child[j];
}
x->child[i + 1] = z;
for (int j = x->n - 1; j > i - 1; j--)
{
x->key[j + 1] = x->key[j];
}
x->key[i] = y->key[DEGREE - 1];
x->n = x->n + 1;
}
void B_Tree_Display(B_Tree* T)
{
node* r = T->root;
B_Tree_Display_Main(r, 1);
}
void B_Tree_Display_Main(node* x, int h)
{
printf("%d : ", h);
for (int i = 0; i < x->n; i++)
{
printf("%d ", x->key[i]);
}
printf("\n");
if (x->leaf == 0)
{
for (int i = 0; i < x->n + 1; i++)
{
B_Tree_Display_Main(x->child[i], h + 1);
}
}
}
void B_Tree_Delete(B_Tree* T, int k)
{
node* r = T->root;
int i = r->n - 1;
if (r->leaf == 1)
{
while (i >= 0 && r->key[i] > k)
{
i--;
}
if (i >= 0 && r->key[i] == k) {
for (int j = i + 1; j < r->n; j++)
{
r->key[j - 1] = r->key[j];
}
r->n--;
printf("delete success\n");
}
else {
printf("no data");
}
return;
}
else {
if (r->n > 1) {
B_Tree_Delete_main(r, k);
}
else {
node* left_c = r->child[0];
node* right_c = r->child[1];
if (left_c->n == DEGREE - 1 && right_c->n == DEGREE - 1) {
left_c->key[DEGREE - 1] = r->key[0];
for (int j = 0; j < DEGREE - 1; j++) {
left_c->key[DEGREE + j] = right_c->key[j];
}
if (left_c->leaf == FALSE) {
for (int j = 0; j < DEGREE; j++) {
left_c->child[DEGREE + j] = right_c->child[j];
}
}
left_c->n = DEGREE * 2 - 1;
free(right_c);
T->root = left_c;
free(r);
B_Tree_Delete_main(left_c, k);
}
else {
B_Tree_Delete_main(r, k);
}
}
}
}
void B_Tree_Delete_main(node* x, int k) {
int i = x->n;
while (i > 0 && x->key[i - 1] >= k) {
i--;
}
if (i < x->n && x->key[i] == k) {
if (x->leaf == 1) {
for (int j = i; j < x->n - 1; j++) {
x->key[j] = x->key[j + 1];
}
x->n--;
return;
}
else {
node* left_c = x->child[i];
node* right_c = x->child[i + 1];
if (left_c->n > DEGREE - 1) {
int pre_k = Find_Predecessor(left_c);
x->key[i] = pre_k;
B_Tree_Delete_main(left_c, pre_k);
}
else if (right_c->n > DEGREE - 1) {
int su_k = Find_Successor(right_c);
x->key[i] = su_k;
B_Tree_Delete_main(right_c, su_k);
}
else {
left_c->key[DEGREE - 1] = k;
for (int j = 0; j < DEGREE - 1; j++)
{
left_c->key[DEGREE + j] = right_c->key[j];
}
for (int j = 0; j < DEGREE; j++) {
left_c->child[DEGREE + j] = right_c->child[j];
}
left_c->n = 2 * DEGREE - 1;
for (int j = i; j < x->n - 1; j++) {
x->key[j] = x->key[j + 1];
}
for (int j = i+1; j < x->n; j++) {
x->child[j] = x->child[j + 1];
}
x->n--;
free(right_c);
B_Tree_Delete_main(left_c, k);
}
}
}
else
{
node* my_way_c = x->child[i];
if (my_way_c->n > DEGREE - 1)
{
B_Tree_Delete_main(my_way_c, k);
}
else
{
if (i != 0 && (x->child[i - 1])->n > DEGREE - 1)
{
node* left_c = x->child[i - 1];
for (int j = DEGREE - 2; j >= 0; j--) {
left_c->key[j + 1] = left_c->key[j];
}
if (left_c->leaf == FALSE)
{
for (int j = DEGREE - 1; j >= 0; j--) {
left_c->child[j + 1] = left_c->child[j];
}
}
my_way_c->key[0] = x->key[i - 1];
my_way_c->child[0] = left_c->child[left_c->n];
my_way_c->n++;
x->key[i - 1] = left_c->key[left_c->n - 1];
left_c->n--;
}
else if(i!=x->n && (x->child[i+1])->n > DEGREE - 1)
{
node* right_c = x->child[i + 1];
my_way_c->key[DEGREE - 1] = x->key[i];
my_way_c->child[DEGREE] = right_c->child[0];
my_way_c->n++;
x->key[i] = right_c->key[0];
for(int j =0; j< right_c->n - 1; j++)
{
right_c->key[j] = right_c->key[j + 1];
}
for (int j = 0; j < right_c->n; j++) {
right_c->child[j] = right_c->child[j + 1];
}
right_c->n--;
}
else {//x에 k가 없고, 풍족한 형제가 없을때!!!
if (i == 0) {
node* right_c = x->child[i + 1];
for (int j = 0; j < DEGREE - 1; j++) {
right_c->key[j + DEGREE] = right_c->key[j];
right_c->key[j] = my_way_c->key[j];
}
if (right_c->leaf == 0) {
for (int j = 0; j < DEGREE; j++) {
right_c->child[j + DEGREE] = right_c->child[j];
right_c->child[j] = my_way_c->child[j];
}
}
right_c->key[DEGREE - 1] = x->key[i];
right_c->n = DEGREE * 2 - 1;
for (int j = 0; j < x->n - 1; j++) {
x->key[j] = x->key[j + 1];
}
for (int j = 0; j < x->n; j++)
{
x->child[j] = x->child[j + 1];
}
free(my_way_c);
my_way_c = right_c;
x->n--;
}
else {
node* left_c = x->child[i - 1];
left_c->key[DEGREE - 1] = x->key[i - 1];
for (int j = 0; j < DEGREE - 1; j++) {
left_c->key[j + DEGREE] = my_way_c->key[j];
}
if (left_c->leaf == 0) {
for (int j = 0; j < DEGREE; j++) {
left_c->child[j + DEGREE] = my_way_c->child[j];
}
}
left_c->n = 2 * DEGREE - 1;
for (int j = i - 1; j < x->n - 1; j++) {
x->key[j] = x->key[j + 1];
}
for (int j = i; j < x->n; j++) {
x->child[j] = x->child[j + 1];
}
free(my_way_c);
my_way_c = left_c;
x->n--;
}
}
B_Tree_Delete_main(my_way_c, k);
}
}
return;
}
int Find_Predecessor(node* x) {
while (x->leaf == 0) {
x = x->child[x->n];
}
return x->key[x->n - 1];
}
int Find_Successor(node* x) {
while (x->leaf == 0) {
x = x->child[0];
}
return x->key[0];
}
우와... 진짜 감동이당 팀원들이랑 유섭쓰! 최고당
알고리즘씨는 앞으로 좀 더 우리 재헌이랑 친하게 지내주구! 우리 재헌이 화이팅이에요❤️❤️