[알고리즘] B 트리

기본개념

B-트리(B-tree)는 데이터베이스와 파일 시스템에서 널리 사용되는 트리 자료구조의 일종으로, 이진 트리를 확장해 하나의 노드가 가질 수 있는 자식 노드의 최대 숫자가 2보다 큰 트리 구조이다. 쉽게 말해서 키를 다수 보유하고 있는 트리라고 할 수 있다.

 

B-트리의 조건

1. 모든 단말노드는 동일한 높이를 가진다.
2. 각 내부노드의 자식노드는 M/2 이상 M 이하이다.  (M은 2보다 큰 정수로서 트리노드의 최대 자식 수)
3. 루트의 자식 수는 두개 이상이다. 

우리는 트리의 높이를 최소화 하기 위해 자가균형트리를 배웠다. (레드블랙트리, AVL 트리) B트리는 키의 갯수를 증가시켜 트리의 좌우를 넓히는 방법으로 높이를 낮췄다고 생각하면 도움이 될것이다.

탐색

B트리는 이진트리와 마찬가지로 중위순회로 탐색을 하면 됩니다. 

 

삽입

B트리는 차수에 따라 알고리즘이 다르기 때문에 3차(홀수) B트리를 예시로 들겠습니다.

초기 삽입시에는 root 노드를 생성합니다.

중위순회를 통해서 데이터 탐색을 한후 leef 노드에 데이터를 삽입하게 됩니다. 주의해야 하는 경우는 한 노드에 데이터가 초과해서 over flow 가 발생하는 경우입니다. 이 경우 해당 노드의 중앙값을 부모로 올리고 두개의 노드로 분리합니다.

 

삭제

Leef Node 인 경우 1 )

 

차수가 2인 B트리에서 10을 삭제해도 해당 노드는 1개의 키를 갖고 있으므로 언더플로우가 발생하지 않는다. 

 

 

Leef Node 인 경우 2 )

 

1을 삭제한 후 과정2를 보면 5의 자식이 하나인 걸 알 수있다. 이렇게 되면 B트리의 조건이 깨지기 때문에 1의 부모와 형제노드를 결합합니다. 이 과정을 조건이 root 로 올라가며 조건이 성립할때 까지 반복합니다.

 

Leef Node 가 아닌경우 1 )

 

 

현재 18이 포함된 노드에는 자식이 존재합니다. 이때 18의 왼쪽 서브트리의 가장 큰 데이터와 18을 교체합니다. 그리고 Leef Node가 된 18을 삭제합니다. 그리고 이전 상황처럼 부모와 형제의 데이터를 결합하여 가져오는 과정을 반복합니다.

 

 

Leef Node 가 아닌 경우 2 )

 

 

 

상황 3 까지는 이전 과정과 동일하게 부모와 교체후 형제와 부모를 결합한다. 이 과정을 root 까지 반복한다.

 

코드

#include <iostream> 
#define M 5
using namespace std;

// BTree의 노드 구조체를 선언합니다. 
struct BTreeNode // Public과 동일한 구조체 선언입니다. 
{
 int *data; // 노드에 들어갈 자료의 배열입니다. 
 BTreeNode **childPtr; // 노드 포인트의 배열입니다. 
 bool leaf; // 리프 노드인지 확인합니다. 
 int n; // 자료의 개수를 의미합니다. 
}*root = NULL, *np = NULL, *x = NULL;

// 노드를 초기화하는 함수입니다. 
BTreeNode * init()
{
 int i;
 np = new BTreeNode; // 객체를 할당합니다.
 np->data = new int[M]; // M개까지의 데이터를 가질 수 있습니다.
 np->childPtr = new BTreeNode *[6]; // M + 1개의 자식 노드입니다. 
 np->leaf = true; // 기본적으로 리프 노드입니다. 
 np->n = 0; // 자료의 개수는 0개입니다.
 for(i = 0; i < 6; i++)
 {
  np->childPtr[i] = NULL; // 각각의 자식 노드를 초기화해줍니다. 
 } 
 return np;
}

// 현재 트리를 보여주는 순회 함수입니다. 
void traverse(BTreeNode * p)
{
 cout << endl;
 int i;
 // 즉, 첫번째 자식 노드부터 가장 마지막 자식 노드까지 전부 밑으로 내려가는 것입니다. 
 for(i = 0; i < p->n; i++)
 {
  // 리프 노드가 아니라면 더 밑으로 내려갑니다. 
  if(p->leaf == false)
  {
   traverse(p->childPtr[i]);
  }
  // 데이터를 출력합니다. 
  cout << " " << p->data[i];
 }
 // 리프 노드가 아니라면 더 밑으로 내려갑니다. 
 if(p->leaf == false)
 {
  traverse(p->childPtr[i]);
 }
 cout << endl;
}

// n개 존재하는 데이터 배열 데이터를 정렬하는 함수입니다. 
void sort(int *p, int n)
{
 int i, j, temp;
 for(i = 0; i < n; i++)
 {
  for(j = i; j <= n; j++)
  {
   if(p[i] > p[j])
   {
    temp = p[i];
    p[i] = p[j];
    p[j] = temp;
   }
  }
 }
}

// 자식을 분할하는 함수입니다.
int splitChild(BTreeNode *x, int i)
{

 // x노드를 분할하여 np1과 np3을 할당합니다. 
 int j, mid;
 BTreeNode *np1, *np3, *y;

 /*
  분할된 형태는 다음과 같습니다.
  x -> 왼쪽으로 가고
  np3 -> 그 오른쪽으로 가고
  np1 -> x와 np3의 부모 노드가 됩니다. 
 */ 

 np3 = init();
 np3->leaf = true;

 // x의 부모 노드가 없어 새롭게 부모 노드를 만들어주는 경우입니다. 
 if(i == -1)
 {

  // M의 중간값을 기준으로 분할합니다. 
  mid = x->data[M / 2];
  x->data[M / 2] = 0;
  x->n--;
  np1 = init();

  // np1는 부모노드이므로 리프 노드가 아닙니다. 
  np1->leaf = false;
  x->leaf = true;
  for(j = M / 2 + 1; j < M; j++)
  {

   // np3는 x의 오른쪽 부분 노드를 가져갑니다. 
   np3->data[j - (M / 2 + 1)] = x->data[j];
   np3->childPtr[j - (M / 2 + 1)] = x->childPtr[j];
   np3->n++;

   // x는 반 쪼개서 왼쪽 부분 노드만 가지고 갑니다. 
   x->data[j] = 0;
   x->n--;
  }

  // x의 모든 자식 노드를 NULL로 만듭니다. 
  for(j = 0; j < M + 1; j++)
  {
   x->childPtr[j] = NULL;
  }
  np1->data[0] = mid;
  np1->childPtr[np1->n] = x;
  np1->childPtr[np1->n + 1] = np3;
  np1->n++;

  // 루트 노드로 설정해줍니다. 
  root = np1;
 }

 // 이미 부모 노드가 있는 경우입니다. 
 else
 {
  y = x->childPtr[i];
  mid = y->data[M / 2];
  y->data[M / 2] = 0;
  y->n--;
  for(j = M / 2 + 1; j < M; j++)
  {

   // np3은 x의 오른쪽 자식 부분만 가져갑니다. 
   np3->data[j - (M / 2 + 1)] = y->data[j];
   np3->n++;
   y->data[j] = 0;
   y->n--;
  }
  x->childPtr[i + 1] = y;
  x->childPtr[i + 1] = np3; 
 }
 return mid;
} 

// a라는 원소를 삽입하는 함수입니다. 
void insert(int a)
{
 int i, temp;
 x = root;

 // 만약에 루트 노드가 NULL이라면 
 if(x == NULL)
 {
  root = init();
  x = root;
 }

 // 루트 노드가 NULL이 아니라면 
 else
 {

  // 현재 리프노드이고 크기가 꽉찼다면 
  if(x->leaf == true && x->n == M)
  {
   temp = splitChild(x, -1);
   x = root;

   // 값을 이동하며 삽입될 자리를 찾습니다. 
   for(i = 0; i < (x->n); i++)
   {
    if((a > x->data[i]) && (a < x->data[i + 1]))
    {
     i++;
     break;
    }
    else if(a < x->data[0])
    {
     break;
    }
    else
    {
     continue;
    }
   }
   x = x->childPtr[i];
  }

  // 리프노드가 아닐 때입니다. 
  else
  {

   // 리프 노드까지 이동합니다. 
   while(x->leaf == false)
   {
    for(i = 0; i < (x->n); i++)
    {
     if((a > x->data[i]) && (a < x->data[i + 1]))
     {
      i++;
      break;
     }
     else if(a < x->data[0])
     {
      break;
     }
     else
     {
      continue;
     }
    }

    // 리프 노드 위에서도 만약에 최대치를 넘으면 분할해줍니다. 
    if((x->childPtr[i])->n == M)
    {
     temp = splitChild(x, i);
     x->data[x->n] = temp;
     x->n++;
     continue;
    }
    else
    {
     x = x->childPtr[i];
    }
   }
  }
 }
 x->data[x->n] = a;
 sort(x->data, x->n);
 x->n++;
}

int main(void)
{
 int i, n, t;
 cout << "삽입할 원소의 개수를 입력하세요 : ";
 cin >> n;
 for(i = 0; i < n; i++)
 {
  cout << "원소를 입력하세요 : ";
  cin >> t;
  insert(t);
 } 
 cout << "트리를 순회합니다." << endl;
 traverse(root);
 return 0;
}