[자료구조] 알아야 할 자료구조 B-Tree

B-Tree

B-Tree는 AVL 트리나 레드 블랙트리와 같이 자가 균형 트리의 종류이다. B-Tree의 사용은 가상 메모리 시스템에서 페이징 기법과 연관이 있는데 페이징이란 디스크 공간을 일정 크기만큼 분할하여 일정 공간 크기를 한 번에 접근할 수 있는 페이지 번호를 매긴다. 디스크에 접근 시 페이지 번호를 참조하여 대략적인 블록 주소를 찾고 정확한 주소는 페이지 번호와 오프셋 정보를 이용하여 접근한다. 페이지의 크기는 8K ~ 16K로 보통 디스크가 한 블록 사이즈로 읽고 쓰므로 디스크 블록 사이즈와 일치한다.

 

B-Tree는 검색 시 페이지 번호를 의미하는 리프 노드까지의 도달 시간을 줄이기 위해 검색 트리의 높이를 낮추는 것에 목적을 둔다. 트리의 높이를 낮추기 위해 B-Tree는 각 노드의 자식 노드의 수를 늘려 "fat"한 검색 트리를 형성하게 된다. 

 

각 노드는 분기하여 다음 노드를 검색할 수 있는 key를 가지고 크기순으로 정렬하여 관리한다. k 개의 키를 가지고 있다면, 키를 기점으로 다음 노드, 즉 서브 트리의 루트를 탐사가능하다. k개의 키로 분기되는 서브 트리 갯수는 k+1개가 되며 그 이유는 서브 트리에 속하는 키가 다음 성질을 만족하기 때문이다.

 

$key_{i-1} < \{key_j \ | \ key_j \in T_{i} \} < key_{i}$

$T_0 < key_0$

$key_{k-1} < T_k$

 

key 값으로 분기되어 탐사된 다음 서브 트리의 루트 노드는 다음 서브트리로 분기할 또 다른 키 값들을 가지고 있다. 최 하단의 리프 노드들까지 도달하는 데 걸리는 탐색 시간은 트리의 높이에 비례한다. 모든 노드의 수를 N, 각 노드에서 최대 M개의 키를 가진다고 했을 때, 균형이 거의 완벽한 경우 $log_M(N)$의 시간이 걸린다. B-Tree는 디스크 블록 사이즈를 반영하여 한 노드에서 적절한 수의 키를 기본으로 보유하며 루트를 제외한 모든 노드는 키의 수를 최소 t개만큼 가지도록 유지하도록 한다.

 

B-Tree 구현

한 노드에서 가지는 키 배열과 자식들에 대한 포인터 배열

각 노드는 자신이 관리하는 데이터에 대한 키와 서브 트리를 탐사할 수 있는 child 노드의 포인터들을 관리한다.

• t라는 파라미터를 받아 B-Tree의 노드는 루트를 제외하고 최소 t 개의 키 수를 유지해야하며 최대 2*t개의 child 노드를 탐사할 수 있도록한다.
• 한 노드에서 child 노드는 최대 2*t개를 가지기 때문에 최대 키 수는 2*t -1이 된다.
• 키는 반드시 오름차순으로 정렬되어 있어야하며 정수 i로 인덱싱되는 키 값, keys[i]을 기준으로 자식 서브트리 children[i]에 속하는 키는 keys[i]보다 작은 값을 가져야 한다. 반대로 children[i+1]의 키들은 keys[i] 키 값보다 항상 큰 값을 가진다.

$children[i].keys < keys[i] \ and\  children[i+1].keys > keys[i]$

 

• 다른 말로 children[i+1] 키들은 keys[i]와 keys[i+1] 사이의 값을 가진다.

$keys[i] < children[i+1].keys < keys[i+1]$

 

• 맨 우측 서브트리는 현재 키 수를 numOfKeys라고 할 때, children[numOfKeys]로 인덱스 된다.
• B-Tree는 이진 트리와 다르게 상향식으로 자라는 트리이다.

class BTreeNode
{
	friend class BTree;
private:
	vector<int> keys; // 키가 저장되어 있는 배열
	int t; // 최소 차수, 모든 노드는 최대 2 * degree - 1 키를 가질 수 있다.
	vector<BTreeNode*> children; // 자식들에 대한 포인터 배열
	int numOfKeys; // 현재 키 수
	bool leaf; // 참 일 경우 노드가 리프 노드
    //...
public:
	BTreeNode(int degree_in, bool _leaf); // 생성자
}

BTreeNode::BTreeNode(int degree_in, bool _leaf)
    :
    t(degree_in),
    numOfKeys(0),
    leaf(_leaf)
{
    keys.resize(t * 2 - 1, 0);
    children.resize(t * 2, nullptr);
    //keys = new int[t * 2 - 1];
    //children = new BTreeNode*[t * 2];
}

 

검색 Search

임의의 수 k를 B-Tree에서 찾는 연산이다.

BTreeNode* BTreeNode::Search(int k)
{
    if (numOfKeys > 0)
    {
        // 내부 키 중 k를 가지고 있을 것 같은 노드를 찾는다.
        int i = 0;
        while (i < numOfKeys && k > keys[i])
        {
            ++i;
        }

        // 가지고 있는 키라면 반환
        if (i < numOfKeys && keys[i] == k)
        {
            return this;
        }
            
        // 후보 노드에서 다시 탐색
        if (children[i])
        {
            return children[i]->Search(k);
        }
        // 리프 노드 였음
        else return nullptr;
    }

    return nullptr;
}

메인 로직은 다음과 같다.

• 해당 노드에서 k가 있을 key위치를 찾는다.
• 그 위치의 key값이 k와 일치하면 검색된 것이다.
• 없다면 자식 노드에서 검색하는데, 자식 노드가 없다면 해당 노드는 리프 노드이고 없는 값을 탐색한 실패 경우이다.

삽입 Insertion

 

삽입은 키를 삽입하는 과정에서 해당 노드가 Full인지 판별하고 꽉 찬 상태라면, 상향식으로 트리가 자랄수 있도록 SplitChild() 함수를 정의한다.

https://www.geeksforgeeks.org/insert-operation-in-b-tree/

SplitChild(int idx, BTreeNode* left)

key_idx를 가지고 있는 부모 노드를 기준으로 새로운 키를 삽입해야할 자식 노드 T_left (= children[idx])가 꽉 찬 상태라면 먼저 두개로 분리하는 작업을 해준다. 꽉 찬 상태의 노드는 2*t-1 키를 가지고 있는 데 이를 두 개로 분리하고 가운데 키를 부모 노드에 삽입한다.

void BTreeNode::SplitChild(int idx, BTreeNode* left)
{
    BTreeNode* right = new BTreeNode(t, left->leaf);

    left->numOfKeys = t - 1;
    right->numOfKeys = t - 1;

    /*
    키 = 2 x t - 1
       -> 자식 키 : t -1
       -> 본인 키 : 1
    */

    // 키 복사
    for (int i = 0; i < t-1; ++i)
    {
        right->keys[i] = left->keys[i + t];
        left->keys[i + t] = 0;
    }

    // 자식들 복사
    if (!left->leaf)
    {
        for (int i = 0; i < t; ++i)
        {
            right->children[i] = left->children[i + t];
        }
    }

    // right를 삽입하기 위해 기존 자식들과 키를 뒤로 민다.
    for (int i = numOfKeys; i > idx; --i)
    {
        keys[i] = keys[i - 1];
        children[i + 1] = children[i];
    }
    
    // 분리하는 자식의 가운데 키를 삽입하고 오른쪽 자식을 삽입한다.
    keys[idx] = left->keys[t-1];
    left->keys[t - 1] = 0;
    children[idx + 1] = right;
    
    // 키 수 증가
    ++numOfKeys;
}

• 추가할 right 트리를 생성한다.
• 마지막 t-1개에 해당하는 키와 자식 포인터까지 복사한다.
• 부모 노드에 키 하나를 삽입하기 위해 한 칸씩 뒤로 민다.
• left 트리의 가운데 키를 idx위치에 삽입한다.
• children[idx+1]에 right 트리를 연결한다.

 

Insert 삽입 함수

현재 노드가 리프 노드라면 꽉 찬 상태일 리가 없다. 현재 구현은 B-Tree의 루트에서 시작해서 아래방향으로 삽입할 노드를 찾는데, SplitChild 함수에 의하여 다음 자식 노드가 꽉 찬 상태라면 분리하고 자식 노드로 재귀하기 때문이다.

따라서 적절한 key 위치만 찾아서 삽입하면 된다.

현재 노드가 리프가 아니라면 속해야하는 child 노드가 꽉 찬 상태인지 확인하고 다음 자식 노드로 재귀할 수 있도록 한다.

void BTreeNode::Insert(int k)
{
    // 리프 노드일 경우
    if (leaf)
    {
        // 자리를 찾는다
        int i = numOfKeys - 1;
        while (i >= 0 && keys[i] > k)
        {
            // 키를 뒤로 민다.
            keys[i + 1] = keys[i];
            --i;
        }

        // 키를 삽입한다.
        keys[i + 1] = k;
        ++numOfKeys;
    }
    
    // 리프 노드가 아닐 경우
    else 
    {
        // 자리를 찾는다
        int i = numOfKeys - 1;
        while (i >= 0 && keys[i] > k)
        {
            --i;
        }

        // 삽입할 자식이 꽉 찬 상태라면
        if (children[i + 1]->IsFull())
        {
            // 분리한다.
            SplitChild(i + 1, children[i + 1]);

            // i+1에 있는 key는 새로 삽입된 키
            // 이 키보다 큰 지 확인한다.
            if (keys[i + 1] < k)
                ++i;
        }
        children[i + 1]->Insert(k);
    }
}

 

삭제 Deletion

삭제는 삽입보다 복잡하다. 삭제하는 노드가 내부 노드(internal)일 수 도 있고 리프 노드 일 수도 있다. 또한 삭제 후에 관리되는 키 수가 t 보다 작은 경우 모든 노드가 최소 키 수 t를 가질 수 있도록 다른 형제 노드에서 키를 가져오거나 다른 형제 노드와 합병을 할 수도 있다.

 

모든 삭제를 위한 보조 함수의 원형은 다음과 같다.

private:
	// k보다 크거나 같은 키를 갖는 인덱스를 찾는다.
	int FindKey(int k) const;

	// 리프 노드일 때 keys[idx]를 지우는 방법 
	void RemoveFromLeaf(int idx);

	// 리프노드가 아닐 떄 keys[idx]를 지우는 방법
	void RemoveFromNonLeaf(int idx);

	// 전임자를 가져온다.
	int GetPred(int idx);

	// 후임자를 가져온다.
	int GetSucc(int idx);

	// 현재 노드의 키를 보충한다.
	void Fill(int idx);

	// 왼쪽에서 보충한다.
	void BorrowFromPrev(int idx);

	// 오른쪽에서 보충한다.
	void BorrowFromNext(int idx);

	// children[idx]와 chilren[idx+1]를 병합한다.
	void Merge(int idx);

 

• FindKey: 현재 노드에서 지워야하는 키의 인덱스나 키에 없다면 후보 서브트리의 인덱스를 가져온다.
• RemoveFromLeaf: 현재 노드에서 지워야하는 키가 있을 때 그리고 현재 노드가 리프 노드일 때 지우는 함수이다.
• RemoveFromNonLeaf:  현재 노드에서 지워야하는 키가 있을 때 그리고 현재 노드가 리프 노드가 아닐 때 지우는 함수이다.
• GetPred: keys[idx]를 기준으로 그 다음으로 작은 키를 왼쪽 서브트리에서 탐색해온다.
• GetSucc: keys[idx]를 기준으로 그 다음으로 큰 키를 오른쪽 서브트리에서 탐색해온다.
• Fill: 현재 노드의 키 수가 불충분하므로 키를 보충한다.
• BorrowFromPrev: 왼쪽 서브트리에서 빌려와 키를 보충한다.
• BorrowFromNext: 오른쪽 서브트리에서 빌려와 키를 보충한다.
• Merge: keys[idx]에서 분기되는 children[idx]와 children[idx+1]를 병합한다.

 

삭제 로직

1. 현재 노드를 기준으로 삭제하려는 키가 관리하는 키 배열에 있다면, 두가지 경우로 계산한다. 

// 이 노드를 루트로 하는 서브트리에서 k를 삭제한다.
void BTreeNode::Remove(int k)
{
    int idx = FindKey(k);

    // 만약 지워야할 인덱스가 현재 노드에 있다면,
    if (idx < numOfKeys && keys[idx] == k)
    {
        // 리프 노드인지에 따라 다른 연산을 수행한다.
        leaf ? RemoveFromLeaf(idx) : RemoveFromNonLeaf(idx);
    }
    // 현재 노드에 없다면
    else

 

RemoveFromLeaf

가장 간단한 경우로 해당 키 위치에 뒤 키 값들을 한 칸씩 땡겨와 덮어쓴다.

void BTreeNode::RemoveFromLeaf(int idx)
{
    // 키를 앞쪽으로 민다.
    for (int i = idx + 1; i < numOfKeys; ++i)
        keys[i - 1] = keys[i];

    keys[numOfKeys - 1] = 0;
    --numOfKeys;
}

 

RemoveFromNonLeaf(idx)

삭제할 노드가 리프가 아니므로 해당 keys[idx]에 치환할 수 있는 값을 찾아야한다. 바로 왼쪽 서브 트리 children[idx]가 충분한 키를 가지고 있다면, 왼쪽 서브트리에서 제일 큰 키를 가져와 keys[idx]에 치환한다. 그리고 왼쪽 서브트리에서 가져온 값을 삭제하도록 재귀한다. 왼쪽 서브트리가 충분하지 않다면 오른쪽 트리를 검사한다.

둘 다 충분하지 않다면, 두 서브 트리의 key 갯수는 t보다 작으므로 두 자식노드를 병합하여 2*t-1를 만들고 삭제할 값을 다시 찾는다.

void BTreeNode::RemoveFromNonLeaf(int idx)
{
    int k = keys[idx];
    /*
        만약 k보다 작은 키를 갖는 자식노드 children[idx]가 t 키 이상을 갖고 있다면,
        children[idx]를 루트로 하는 서브 트리에서 k의 predecessor 인덱스를 구한다.
        k를 pred로 치환하고 children[idx]에서 pred를 삭제한다. 
    */
    // 키 수가 최소 숫자를 만족함
    if (children[idx]->IsEnough())
    {
        int pred = GetPred(idx);
        keys[idx] = pred;
        children[idx]->Remove(pred);
    }
    /*
        만약 k보다 작은 키를 갖는 자식노드 children[idx]가 t 보다 적은 키를 갖고 있다면,
        children[idx+1]를 루트로 하는 서브 트리에서 k의 successor 인덱스를 구한다.
        k를 succ로 치환하고 children[idx+1]에서 succ를 삭제한다.
   */
    else if (children[idx + 1]->IsEnough())
    {
        int succ = GetSucc(idx);
        keys[idx] = succ;
        children[idx + 1]->Remove(succ);
    }

    /*
        children[idx]와 children[idx+1]가 t보다는 적은 키를 가지고 있다면,
        k와 children[idx+1]를 children[idx]에 병합한다.
        이제 children[idx]는 2*t-1 키를 가지고 있다.
        children[idx+1]를 지우고 children[idx]에서 k를 지운다.
    */
    else
    {
        Merge(idx);
        children[idx]->Remove(k);
    }
}

2. 현재 노드에 삭제할 키가 없다면 자식 노드에서 키를 찾아야한다.

키가 있어야할 자식 노드가 충분한 키를 가지고 있지 않다면 삽입과 반대로 키를 보충해야한다.

키를 보충하는 방식은 형제 노드 즉, 왼쪽이나 오른쪽에서 키를 가져오고 그렇지 못 할 경우(충분하지 않거나 맨 왼쪽 혹은 오른쪽 트리일 때) 형제 노드와 병합을 하도록 한다.

// children[idx]가 충분한 키를 가지고 있지 않은 경우 보충한다.
void BTreeNode::Fill(int idx)
{
    // 왼쪽이 키 수가 충분히 많다면 왼쪽에서 빌려온다.
    if (idx != 0 && children[idx - 1]->IsEnough())
    {
        BorrowFromPrev(idx);
    }

    // 오른쪽 키 수가 충분히 많다면 오른쪽에서 빌려온다.
    else if (idx != numOfKeys && children[idx + 1]->IsEnough())
    {
        BorrowFromNext(idx);
    }

    // 가져올 수 없는 경우 children[idx]를 형제 노드와 병합한다.
    else
    {
        idx == numOfKeys ? Merge(idx - 1) : Merge(idx);
    }
}

BorrowFromPrev(idx)

그 중 하나인 BorrowFromPrev 연산을 보면,

children[idx]의 키를 보충하기 위해 children[idx-1]에서 가져와야 한다. 이를 위해 key[idx]를 child(children[idx])의 맨 왼쪽에 추가하고 그 자리에 형제 노드의 키 중 가장 큰 값을 부모 노드의 key[idx]로 올린다.

또한 형제 노드에 맨 오른쪽에 달린 서브트리가 있다면 자식 노드의 맨 왼쪽에 붙이는 것도 해주도록한다.

이 결과로 자식 노드의 키 수는 하나 증가하고 형제 노드의 키 수는 하나 감소한다.

// children[idx-1] 에서 key를 빌려와 children[idx]에 삽입하는 방식이다
void BTreeNode::BorrowFromPrev(int idx)
{
    BTreeNode* child = children[idx];
    BTreeNode* sibling = children[idx - 1];

   /*
    children[idx-1] 에서 맨 오른쪽에 있는 키를 빌려와 key[idx-1]에 넣고
    기존 key[idx-1]를 children[idx]의 맨 왼쪽에 넣는 방식이다.
    형제는 키 하나를 잃고 자식은 키 하나를 얻는다
   */

    // children[idx]에 있는 키를 한 칸 민다.
    for (int i = child->numOfKeys - 1; i >= 0; --i)
        child->keys[i + 1] = child->keys[i];

    if (!child->leaf)
    {
        // 자식 노드도 마찬가지
        for (int i = child->numOfKeys; i >= 0; --i)
            child->children[i + 1] = child->children[i];
    }

    // child의 첫번째 키를 key[idx-1]로 치환한다.
    child->keys[0] = keys[idx - 1];

    // 자식도 같이 움직인다.
    if (!child->leaf)
    {
        child->children[0] = sibling->children[sibling->numOfKeys];
    }

    // sibling의 마지막 키를 key[idx-1]로 치환한다.
    keys[idx - 1] = sibling->keys[sibling->numOfKeys - 1];

    // 자식과 형제 키 수를 조정한다.
    ++child->numOfKeys;
    --sibling->numOfKeys;
}

 

Merge(idx)

children[idx] 키 수가 부족한 상황에 빌려오는 것도 불가능하면 오른쪽 형제 노드와 병합을 실행한다. 이 때 key[idx]도 같이 병합하여 최대 키 수가 2*t - 1을 가질 수 있도록 한다.

// children[idx] 와 children[idx+1]를 합치는 연산
// children[idx+1]은 연산 후에 삭제됩니다.
void BTreeNode::Merge(int idx)
{
    // 전제 조건
    // children[idx]와 children[idx+1]은 t보다 작은 수의 키를 가지고 있다.
    // 따라서 키 하나와 두 자식 노드를 합치려고 하는 것이다.
    BTreeNode* child = children[idx];
    BTreeNode* sibling = children[idx + 1];

    // 키를 왼쪽 자식에 밀어 넣는다.
    int childEnd = child->numOfKeys;
    child->keys[childEnd] = keys[idx];

    // 형제 키를 복사하여 넣는다.
    ++childEnd;
    for (int i = 0; i < sibling->numOfKeys; ++i)
        child->keys[i + childEnd] = sibling->keys[i];

    // 형제 자식노드를 복사하여 넣는다.
    if (!child->leaf)
    {
        for (int i = 0; i <= sibling->numOfKeys; ++i)
            child->children[i + childEnd] = sibling->children[i];
    }

    // 기존 키 하나를 뺏으므로 기존 키 배열을 조정한다.
    for (int i = idx + 1; i < numOfKeys; ++i)
        keys[i - 1] = keys[i];

    // children[idx+1]을 삭제할 것이므로 자식 노드도 움직인다.
    for (int i = idx + 2; i <= numOfKeys; ++i)
        children[i - 1] = children[i];

    // 자식과 현재 노드의 키 수를 업데이트 한다.
    child->numOfKeys += (sibling->numOfKeys + 1);
    --numOfKeys;

    delete sibling;
}

 

전체 코드

BTree.h

#pragma once
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;

class BTreeNode
{
	friend class BTree;
private:
	vector<int> keys; // 키가 저장되어 있는 배열
	int t; // 최소 차수, 모든 노드는 최대 2 * degree - 1 키를 가질 수 있다.
	vector<BTreeNode*> children; // 자식들에 대한 포인터 배열
	int numOfKeys; // 현재 키 수
	bool leaf; // 참 일 경우 노드가 리프 노드
private:
	bool IsFull() const;
	bool IsEnough() const;
public:
	BTreeNode(int degree_in, bool _leaf); // 생성자

	void Traverse(); // 모든 서브 트리를 순회하는 방법

	BTreeNode* Search(int k); // if k is not present, return NULL

	void Insert(int key);

	void SplitChild(int idx, BTreeNode* left);

	void Remove(int k);
private:
	// k보다 크거나 같은 키를 갖는 인덱스를 찾는다.
	int FindKey(int k) const;

	// 리프 노드일 때 keys[idx]를 지우는 방법 
	void RemoveFromLeaf(int idx);

	// 리프노드가 아닐 떄 keys[idx]를 지우는 방법
	void RemoveFromNonLeaf(int idx);

	// 전임자를 가져온다.
	int GetPred(int idx);

	// 후임자를 가져온다.
	int GetSucc(int idx);

	// 현재 노드의 키를 보충한다.
	void Fill(int idx);

	// 왼쪽에서 보충한다.
	void BorrowFromPrev(int idx);

	// 오른쪽에서 보충한다.
	void BorrowFromNext(int idx);

	// children[idx]와 chilren[idx+1]를 병합한다.
	void Merge(int idx);

	int GetHeight() const;
};

class BTree
{
private:
	BTreeNode* root;
	int degree; // 최수 차수
public:
	// 생성자
	BTree(int degree_in)
		:
		root(nullptr),
		degree(degree_in)
	{
	}

	// 소멸자
	~BTree()
	{
		vector<BTreeNode*> visit;
		if (root)
		{
			visit.push_back(root);
			while (!visit.empty())
			{
				BTreeNode* cur = visit.back();
	
				bool allVisited = true;
				for (int i = 0; i <= cur->numOfKeys; ++i)
				{
					if (cur->children[i] == nullptr)
						continue;

					if (cur->children[i]->leaf)
					{
						delete cur->children[i];
						cur->children[i] = nullptr;
					}
					else
					{
						visit.push_back(cur->children[i]);
						allVisited = false;
						break;
					}
				}

				if (allVisited)
				{
					cur->leaf = true;
					visit.pop_back();
				}
			}

			delete root;
		}
	}

	// 트리를 순회하는 함수
	void Traverse()
	{
		if (root)
		{
			root->Traverse();
		}
		cout << endl;
	}

	BTreeNode* Search(int k)
	{
		return (root == nullptr) ? nullptr : root->Search(k);
	}

	void Insert(int k)
	{
		if (!root)
		{
			root = new BTreeNode(degree, true);
		}

		if (root->IsFull())
		{
			BTreeNode* newRoot = new BTreeNode(degree, false);

			// 새로운 루트의 자식은 기존 루트로 설정
			newRoot->children[0] = root;

			// 기존 루트를 분리한다.
			newRoot->SplitChild(0, root);

			// 왼쪽인지 오른쪽인지 체크한다.
			int i = newRoot->keys[0] < k ? 1 : 0;
			newRoot->children[i]->Insert(k);

			// 새로운 루트 설정
			root = newRoot;
		}
		else root->Insert(k);
	}

	void Remove(int k)
	{
		if (!root)
		{
			cout << "The tree is empty \n";
			return;
		}

		root->Remove(k);

		// 루트가 0 키를 가질 때 체크해야한다.
		if (root->numOfKeys == 0)
		{
			BTreeNode* tmp = root;
			if (root->leaf)
				root = nullptr;
			else
				root = root->children[0];

			// free the old root
			delete tmp;
		}
	}

	int GetHeight() const
	{
		if (!root) return 0;
		return root->GetHeight();
	}
};

BTree.cpp

#include "BTree.h"

BTreeNode::BTreeNode(int degree_in, bool _leaf)
    :
    t(degree_in),
    numOfKeys(0),
    leaf(_leaf)
{
    keys.resize(t * 2 - 1, 0);
    children.resize(t * 2, nullptr);
    //keys = new int[t * 2 - 1];
    //children = new BTreeNode*[t * 2];
}

void BTreeNode::Traverse()
{
    for (int i = 0; i < numOfKeys; ++i)
    {
        if (!leaf)
        {
            children[i]->Traverse();
        }
        std::cout << " " << keys[i];
    }

    if (!leaf)
    {
        children[numOfKeys]->Traverse();
    }
}

BTreeNode* BTreeNode::Search(int k)
{
    if (numOfKeys > 0)
    {
        // 내부 키 중 k를 가지고 있을 것 같은 노드를 찾는다.
        int i = 0;
        while (i < numOfKeys && k > keys[i])
        {
            ++i;
        }

        // 가지고 있는 키라면 반환
        if (i < numOfKeys && keys[i] == k)
        {
            return this;
        }
            
        // 후보 노드에서 다시 탐색
        if (children[i])
        {
            return children[i]->Search(k);
        }
        // 리프 노드 였음
        else return nullptr;
    }

    return nullptr;
}

void BTreeNode::Insert(int k)
{
    // 리프 노드일 경우
    if (leaf)
    {
        // 자리를 찾는다
        int i = numOfKeys - 1;
        while (i >= 0 && keys[i] > k)
        {
            // 키를 뒤로 민다.
            keys[i + 1] = keys[i];
            --i;
        }

        // 키를 삽입한다.
        keys[i + 1] = k;
        ++numOfKeys;
    }
    
    // 리프 노드가 아닐 경우
    else 
    {
        // 자리를 찾는다
        int i = numOfKeys - 1;
        while (i >= 0 && keys[i] > k)
        {
            --i;
        }

        // 삽입할 자식이 꽉 찬 상태라면
        if (children[i + 1]->IsFull())
        {
            // 분리한다.
            SplitChild(i + 1, children[i + 1]);

            // i+1에 있는 key는 새로 삽입된 키
            // 이 키보다 큰 지 확인한다.
            if (keys[i + 1] < k)
                ++i;
        }
        children[i + 1]->Insert(k);
    }
}

bool BTreeNode::IsFull() const
{
    return numOfKeys == 2 * t - 1;
}

void BTreeNode::SplitChild(int idx, BTreeNode* left)
{
    BTreeNode* right = new BTreeNode(t, left->leaf);

    left->numOfKeys = t - 1;
    right->numOfKeys = t - 1;

    /*
    키 = 2 x t - 1
       -> 자식 키 : t -1
       -> 본인 키 : 1
    */

    // 키 복사
    for (int i = 0; i < t-1; ++i)
    {
        right->keys[i] = left->keys[i + t];
        left->keys[i + t] = 0;
    }

    // 자식들 복사
    if (!left->leaf)
    {
        for (int i = 0; i < t; ++i)
        {
            right->children[i] = left->children[i + t];
        }
    }

    // right를 삽입하기 위해 기존 자식들과 키를 뒤로 민다.
    for (int i = numOfKeys; i > idx; --i)
    {
        keys[i] = keys[i - 1];
        children[i + 1] = children[i];
    }
    
    // 분리하는 자식의 가운데 키를 삽입하고 오른쪽 자식을 삽입한다.
    keys[idx] = left->keys[t-1];
    left->keys[t - 1] = 0;
    children[idx + 1] = right;
    
    // 키 수 증가
    ++numOfKeys;
}

int BTreeNode::GetHeight() const
{
    if (leaf)
        return 1;
    
    int max_height = 0;
    for (int i = 0; i <= numOfKeys; ++i)
    {
        max_height = max(max_height, 1 + children[i]->GetHeight());
    }
    return max_height;
}

bool BTreeNode::IsEnough() const
{
    return numOfKeys >= t;
}

int BTreeNode::FindKey(int k) const
{
    int i = 0;
    while (i < numOfKeys && keys[i] < k)
    {
        ++i;
    }
    return i;
}


// 이 노드를 루트로 하는 서브트리에서 k를 삭제한다.
void BTreeNode::Remove(int k)
{
    int idx = FindKey(k);

    // 만약 지워야할 인덱스가 현재 노드에 있다면,
    if (idx < numOfKeys && keys[idx] == k)
    {
        // 리프 노드인지에 따라 다른 연산을 수행한다.
        leaf ? RemoveFromLeaf(idx) : RemoveFromNonLeaf(idx);
    }
    // 현재 노드에 없다면
    else
    {
        // 리프 노드 이나 키가 없다면 지울 수 없다.
        if (leaf)
        {
            cout << "The key " << k << "does not exist in tree" << endl;
            return;
        }

        // 키가 마지막 자식 노드의 서브트리에 있는지 확인
        bool isLast = (idx == numOfKeys);

        // 만약 키가 있어야하는 자식 노드가 최소 키 수 t(t)보다 작은 수를 가지고 있다면,
        // 그 자식 노드의 키를 채운다.
        if (!children[idx]->IsEnough())
        {
            Fill(idx);
        }

        // 마지막 자식 노드가 병합한 상태라면, 그 이전 자식노드와 병합해서 만들어 진 것이다
        // 따라서 (idx-1) 자식노드에 재귀를 진행한다.
        // 아니라면, (idx) 자식 노드는 최소 t 키를 가지고 있으므로 재귀한다.
        if (isLast && idx > numOfKeys)
            children[idx - 1]->Remove(k);
        else
            children[idx]->Remove(k);
    }
}

void BTreeNode::RemoveFromLeaf(int idx)
{
    // 키를 앞쪽으로 민다.
    for (int i = idx + 1; i < numOfKeys; ++i)
        keys[i - 1] = keys[i];

    keys[numOfKeys - 1] = 0;
    --numOfKeys;
}

int BTreeNode::GetPred(int idx)
{
    BTreeNode* cur = children[idx];
    while (!cur->leaf)
        cur = cur->children[cur->numOfKeys];

    // 최하단 우측의 키를 반환
    return cur->keys[cur->numOfKeys - 1];
}

int BTreeNode::GetSucc(int idx)
{
    BTreeNode* cur = children[idx+1];
    while (!cur->leaf)
        cur = cur->children[0];

    // 최하단좌측 키를 반환
    return cur->keys[0];
}

void BTreeNode::RemoveFromNonLeaf(int idx)
{
    int k = keys[idx];
    /*
        만약 k보다 작은 키를 갖는 자식노드 children[idx]가 t 키 이상을 갖고 있다면,
        children[idx]를 루트로 하는 서브 트리에서 k의 predecessor 인덱스를 구한다.
        k를 pred로 치환하고 children[idx]에서 pred를 삭제한다. 
    */
    // 키 수가 최소 숫자를 만족함
    if (children[idx]->IsEnough())
    {
        int pred = GetPred(idx);
        keys[idx] = pred;
        children[idx]->Remove(pred);
    }
    /*
        만약 k보다 작은 키를 갖는 자식노드 children[idx]가 t 보다 적은 키를 갖고 있다면,
        children[idx+1]를 루트로 하는 서브 트리에서 k의 successor 인덱스를 구한다.
        k를 succ로 치환하고 children[idx+1]에서 succ를 삭제한다.
   */
    else if (children[idx + 1]->IsEnough())
    {
        int succ = GetSucc(idx);
        keys[idx] = succ;
        children[idx + 1]->Remove(succ);
    }

    /*
        children[idx]와 children[idx+1]가 t보다는 적은 키를 가지고 있다면,
        k와 children[idx+1]를 children[idx]에 병합한다.
        이제 children[idx]는 2*t-1 키를 가지고 있다.
        children[idx+1]를 지우고 children[idx]에서 k를 지운다.
    */
    else
    {
        Merge(idx);
        children[idx]->Remove(k);
    }
}

// children[idx] 와 children[idx+1]를 합치는 연산
// children[idx+1]은 연산 후에 삭제됩니다.
void BTreeNode::Merge(int idx)
{
    // 전제 조건
    // children[idx]와 children[idx+1]은 t보다 작은 수의 키를 가지고 있다.
    // 따라서 키 하나와 두 자식 노드를 합치려고 하는 것이다.
    BTreeNode* child = children[idx];
    BTreeNode* sibling = children[idx + 1];

    // 키를 왼쪽 자식에 밀어 넣는다.
    int childEnd = child->numOfKeys;
    child->keys[childEnd] = keys[idx];

    // 형제 키를 복사하여 넣는다.
    ++childEnd;
    for (int i = 0; i < sibling->numOfKeys; ++i)
        child->keys[i + childEnd] = sibling->keys[i];

    // 형제 자식노드를 복사하여 넣는다.
    if (!child->leaf)
    {
        for (int i = 0; i <= sibling->numOfKeys; ++i)
            child->children[i + childEnd] = sibling->children[i];
    }

    // 기존 키 하나를 뺏으므로 기존 키 배열을 조정한다.
    for (int i = idx + 1; i < numOfKeys; ++i)
        keys[i - 1] = keys[i];

    // children[idx+1]을 삭제할 것이므로 자식 노드도 움직인다.
    for (int i = idx + 2; i <= numOfKeys; ++i)
        children[i - 1] = children[i];

    // 자식과 현재 노드의 키 수를 업데이트 한다.
    child->numOfKeys += (sibling->numOfKeys + 1);
    --numOfKeys;

    delete sibling;
}

// children[idx]가 충분한 키를 가지고 있지 않은 경우 보충한다.
void BTreeNode::Fill(int idx)
{
    // 왼쪽이 키 수가 충분히 많다면 왼쪽에서 빌려온다.
    if (idx != 0 && children[idx - 1]->IsEnough())
    {
        BorrowFromPrev(idx);
    }

    // 오른쪽 키 수가 충분히 많다면 오른쪽에서 빌려온다.
    else if (idx != numOfKeys && children[idx + 1]->IsEnough())
    {
        BorrowFromNext(idx);
    }

    // 가져올 수 없는 경우 children[idx]를 형제 노드와 병합한다.
    else
    {
        idx == numOfKeys ? Merge(idx - 1) : Merge(idx);
    }
}

// children[idx-1] 에서 key를 빌려와 children[idx]에 삽입하는 방식이다
void BTreeNode::BorrowFromPrev(int idx)
{
    BTreeNode* child = children[idx];
    BTreeNode* sibling = children[idx - 1];

   /*
    children[idx-1] 에서 맨 오른쪽에 있는 키를 빌려와 key[idx-1]에 넣고
    기존 key[idx-1]를 children[idx]의 맨 왼쪽에 넣는 방식이다.
    형제는 키 하나를 잃고 자식은 키 하나를 얻는다
   */

    // children[idx]에 있는 키를 한 칸 민다.
    for (int i = child->numOfKeys - 1; i >= 0; --i)
        child->keys[i + 1] = child->keys[i];

    if (!child->leaf)
    {
        // 자식 노드도 마찬가지
        for (int i = child->numOfKeys; i >= 0; --i)
            child->children[i + 1] = child->children[i];
    }

    // child의 첫번째 키를 key[idx-1]로 치환한다.
    child->keys[0] = keys[idx - 1];

    // 자식도 같이 움직인다.
    if (!child->leaf)
    {
        child->children[0] = sibling->children[sibling->numOfKeys];
    }

    // sibling의 마지막 키를 key[idx-1]로 치환한다.
    keys[idx - 1] = sibling->keys[sibling->numOfKeys - 1];

    // 자식과 형제 키 수를 조정한다.
    ++child->numOfKeys;
    --sibling->numOfKeys;
}

// children[idx+1]에서 키를 빌려와 children[idx]에 배치시키는 방법이다.
void BTreeNode::BorrowFromNext(int idx)
{
    BTreeNode* child = children[idx];
    BTreeNode* sibling = children[idx + 1];

    // keys[idx]는 children[idx]의 마지막 키로 삽입된다.
    child->keys[child->numOfKeys] = keys[idx];

    // child의 마지막 children에 형제의 첫번쨰 자식노드를 붙인다.
    if (!child->leaf)
        child->children[child->numOfKeys + 1] = sibling->children[0];

    // keys[idx]에 형제 키 중 가장 첫번째 것을 가져온다.
    keys[idx] = sibling->keys[0];

    // 형제의 첫번째 키를 뺏으므로 한 칸 당겨온다.
    for (int i = 1; i < sibling->numOfKeys; ++i)
        sibling->keys[i - 1] = sibling->keys[i];

    if (!sibling->leaf)
    {
        // 형제의 자식노드도 한 칸 당겨온다.
        for (int i = 1; i <= sibling->numOfKeys; ++i)
            sibling->children[i - 1] = sibling->children[i];
    }

    // child는 키가 증가, sibling은 키가 감소
    ++child->numOfKeys;
    --sibling->numOfKeys;
}

 

테스트 코드

#include "BTree.h"
#include <crtdbg.h>

int main()
{
    _CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
    int num = 20;
    int block_size = 3;
    srand((unsigned int)time(NULL));
	BTree t(block_size);

    vector<int> arr(num);
    for (int i = 0; i < num; ++i)
    {
        arr[i] = i + 1;
    }

    for (int i = 0; i < 1000; ++i)
    {
        int p = rand() % num;
        int q = rand() % num;
        std::swap(arr[p], arr[q]);
    }

    for (int i = 0; i < num; ++i)
    {
        t.Insert(arr[i]);
    }

    cout << "Element Num(N): " << num << " / min key num(M) : " << block_size << endl;
    cout << "(Max Height) log_M(N) is " << log(num) / log(block_size);
    cout << " Tree Height is " << t.GetHeight() << endl;

    cout << "=====================================" << endl;
    cout << "Traversal of the constucted tree is ";
    t.Traverse();

    int k = 6;
    (t.Search(k)) ? cout << "\nPresent" : cout << "\nNot Present";

    k = 15;
    (t.Search(k)) ? cout << "\nPresent" : cout << "\nNot Present";
    cout << endl << endl;

    for (int i = 0; i < num; ++i)
    {
        t.Remove(i + 1);
        cout << "After Remove Traversal of the constucted tree is " << endl;
        t.Traverse();
    }
 
    return 0;
}

 

실행 결과