210111 개발일지(35일차) - B-tree프로젝트 : B-tree에 대한 이해 및 c언어로 구현하기

지난 4주간 아래에 해당하는 문제를 150문제 이상 풀었다.
나는 여기 오기 전까지 알고리즘 문제를 풀어본 적이 없어서, 개념들을 다 집어 넣으면서 문제를 풀다보니 쉽지 않았다. 아직 개념도, 구현도 많이 부족하지만 알고리즘과 친해지는 시간이었다. 이번 5주차 주제는 'B-tree 및 B+tree 프로젝트'인데, c언어도 한 번도 경험해보지 못한 상태에서 1주일 만에 구현하는 것이 가능할까.. 생각했지만 B-tree는 계획대로 구현을 성공했다! (정말 유섭이와 정서에게 큰 감사를...)
팀원들을 잘만나서 순항하고 있지만 아직 c언어랑도 친하지 않아서 B-tree에 대해 100% 이해했다고 보기 힘들다. 다시 한 번 여기 정리하면서, 개념을 탄탄히 해보자.

컴퓨터 시스템 측면에서 B-tree

B-tree는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종이다. 다른 여러 트리구조가 있지만, 다음과 같은 특성 덕분에 디스크 접근 횟수를 줄여서 연산 속도를 빠르게 할 수 있다.

1. B-tree 노드의 키(key) 개수는 수백, 수천 개까지 가질 수 있다.
2. B-tree 노드의 자식노드는 부모의 키(key) 개수 +1이다.
3. 모든 리프(leaf)노드는 깊이가 같다.
   * 리프(leaf)노드 : 자식이 없는 노드

연산의 속도를 크게 좌지우지하는 디스크 접근 횟수를 최소화 하기 위해, 노드의 키 개수와 자식 개수를 크게 만들어 활용한다고 생각할 수 있다.
보통 루트(root) 노드는 메인메모리(ram)에 있고, 그 아래 노드들에 접근하기 위해 디스크 접근을 한다고 생각해라.

구조 및 자료구조 측면에서 B-tree

B-tree의 각 노드에는 키(key)정보와 그 자식노드를 가리키는 포인터 정보가 들어있다. 또, leaf노드 정보도 들어있다.

B-tree인 T는 아래와 같은 특징이 있고, T.root를 루트 노드로 가진다.

1. 모든 노드 안에 키는 오름차순으로 정렬돼있다.
2. 노드의 각 키는 서브 트리(자식 노드들)에 저장되는 키들의 범위를 분할한다. 즉, 아래와 같은 의미인데 그림으로 보면 이해가 쉬울 것이다.
   
3. 노드의 키 개수는 t-1개 이상, 2t-1개 이하이다. 즉 최소 t-1개, 최대 2t-1개의 키 개수를 갖는다.

B-tree 구현하기(검색, 삽입, 삭제)

우리는 Introduction to algorithms 책을 기반으로 구현 했다.

1. 검색 : 아래 의사코드를 통해 구현했는데, 검색은 x노드에 있는지 없는지 확인하고 있으면 해당 값들을 리턴해주면 된다.
   

2. 삽입 : 삽입은 여러 단계에 걸쳐 일어난다고 이해해야 한다.
   2-1. 빈 트리 생성 : 아무 것도 없는 상태에서 첫 원소(?)를 삽입하기 전에 빈 트리를 생성한다.
   2-2. 삽입하기(Main 함수) : 이 때, 루트(root) 노드가 꽉 찼는지 유무에 따라 2-3과 2-4를 실행한다.
   2-3. 꽉 찬 노드 쪼개주기 : 삽입하려는 곳의 노드가 꽉 차 있을 경우(키의 개수가 2t-1)에 이 함수를 실행한다.
   2-4. 꽉 차지 않은 리프(leaf)노드에 원소 삽입하기 : 2-2와 2-3에 의해, 꽉 차지 않은 노드가 확보된 경우에 바로 원소를 삽입한다.

책에 삽입에 대한 의사코드가 나와 있어, 비교적 수월(?)하게 할 수 있었다.

(유섭이가 삽입에 대한 개념을 정리하며 설명해준 기록)

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];
}