B 트리 구현 및 테스트

  B 트리 

이진 검색 트리를 기반으로 노드에 Balance Factor(이후 BF)를 추가하여 BF의 상태에 따라 트리의 균형을 유지한다.

 

B 트리 개요

검색 트리가 방대하면 검색 트리를 메모리에 모두 올려두고 사용할 수 없게 되어 검색 트리가 디스크에 있는 상태에서 작업을 해야 한다. 이런 경우에 CPU 작업 효율성보다 디스크 접근 횟수가 효율을 좌우하게 된다.

 

B 트리는 디스크 환경에서 사용하기 적합한 외부 다진 검색 트리로 B 트리의 한 노드에는 최대 k개까지의 키가 크기 순으로 저장되어 있다.

 

※ 검색 트리가 디스크에 있는 상태로 사용되면 이를 외부 검색 트리라고 한다.

 

B 트리에 k개의 키가 존재하는 경우 k + 1 개의 자식을 가지게 된다.

이때, 주어진 키를 key 0 ~ key k - 1로 나타내고 자식 서브 트리를 각각 T 0 ~ T k 로 나타내면 다음의 관계가 성립한다.

 

---

T 0 의 모든 노드의 값 < key 0 < T 1의 모든 노드의 값 < key 1 < ... < key k - 1 < T k 의 모든 노드의 값

---

 

쉽게 배우는 알고리즘 B 트리 그림 5-17

 

B 트리는 균형 잡힌 다진 검색 트리로 다음의 성질을 만족한다.

• 루트를 제외한 모든 노드는 k / 2 ~ k 개의 키를 갖는다.
• 모든 리프 노드는 같은 깊이를 가진다.

 

※ B 트리는 최대 효율을 위해 디스크의 블록의 크기에 따라 가질 수 있는 최대 키의 개수가 정해진다.

 

---

디스크의 한 블록의 크기가 4,096 byte 일 때, 키의 크기가 16 byte 페이지 번호가 4 byte를 차지하는 경우

 

B 트리가 가질 수 있는 최대 키의 개수는 디스크의 한 블록의 크기 / 키와 페이지 번호를 나타내는데 필요한 크기 이므로

4,096 / (4 + 16 + 4) ≒ 170.6

 

최대 170개의 키 값을 가질 수 있다.

 

※ 구현을 위해서 키는 왼쪽 자식과 오른쪽 자식을 모두 가져야 하므로 페이지 번호를 두 개 저장한다.

---

 

B 트리에서의 검색

기본적으로 이진 검색 트리와 동일한 방법으로 검색을 진행한다. 단, B 트리는 n 개의 키를 가지므로 다음과 같은 조건을 만족하는 분기를 찾아 진행하게 된다.

 

---

x < key i

또는 key i - 1 < x < key i

또는 key i < x

---

 

※ B 트리의 검색도 이진 검색 트리처럼 재귀적으로 처리할 수 있다.

 

B 트리에서의 삽입

입력된 값을 x라 할 때, x를 삽입하는 방법은 다음과 같다.

• x를 삽입할 리프 노드를 찾는다.
• 리프 노드에 여유가 있으면 키를 삽입하고 종료한다.
• 리프 노드에 여유가 없으면
  • 형제 노드에 여유가 있으면 형제 노드에 키를 하나 넘기고 종료한다.
  • 형제 노드에 여유가 없으면 노드를 두 개로 분리한다.
• 부모 노드에 오버플로우 발생 시 부모 노드를 문제 노드로 하여 이상을 반복한다.

 

- B 트리 삽입 알고리즘

새로운 키를 삽입한 뒤 오버플로우에 대한 처리를 진행한다.

 

B 트리 삽입 알고리즘

BTreeInsert(t, x)
{
    x를 삽입할 리프 노드 r을 찾는다;
    x를 r에 삽입한다;
    if (r에 오버플로우 발생) then
    {
        clearOverflow(r);
    }
}

clearOverflow(r)
{
    if (r의 형제 노드 중 여유가 있는 노드가 있음) then
    {
        r의 남는 키를 넘긴다;
    }
    else
    {
        r을 둘로 분할하고 가운데 키를 부모 노드로 넘긴다;
        if (부모 노드 p에 오버플로우 발생) then
        {
            clearOverflow(p);
        }
    }
}

 

- B 트리 삽입 예제

B 트리에 새로운 노드를 삽입할 때 발생한 오버플로우에 대한 처리를 보여준다.

 

쉽게 배우는 알고리즘 B 트리 그림5-19

 

B 트리에서의 삭제

입력된 값을 x라 할 때, x를 삽입하는 방법은 다음과 같다.

• x를 갖고 있는 노드를 찾는다.
• 이 노드가 리프 노다가 아니면 x의 직후 원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
• 리프 노드에서 x를 제거한다.
• x 제거 후 노드에 언더플로우가 발생하면
  • 키를 가져올 수 있는 형제 노드가 있으면 해당 키를 가져온다.
  • 키를 가져올 수 있는 형제 노드가 없으면 형제 노드와 병합한다. 
• 부모 노드에 언더플로우 발생 시 부모 노드를 문제 노드로 하여 이상을 반복한다.

 

- B 트리 삭제 알고리즘

주어진 키를 삭제한 뒤 언더플로우에 대한 처리를 진행한다.

 

B 트리 삭제 알고리즘

BTreeDelete(t, x, v)
{
    if (v가 리프 노드가 아님) then
    {
    	x의 직후 원소 y를 가진 리프 노드를 찾는다;
        x와 y를 맞바꾼다;
    }
    리프 노드에서 x를 제거하고 이 리프 노드를 r이라 한다;
    if (r에서 언더플로우 발생) then
    {
    	clearUnderflow(r);
    }
}

clearUnderflow(r)
{
    if (r의 형제 노드 중 키를 하나 내놓을 수 있는 여분을 가진 노드가 있음) then
    {
        r이 키를 넘겨받는다;
    }
    else
    {
        r의 형제 노드와 r을 병합한다;
        if (부모 노드 p에 언더플로우 발생) then
        {
        	clearUnderflow(p);
        }
    }
}

 

- B 트리 삭제 예제

B 트리에 주어진 노드를 삭제할 때 발생한 언더플로우에 대한 처리를 보여준다.

쉽게 배우는 알고리즘 B 트리 그림 5-20

 

B 트리 작업 성능 분석

이진 검색 트리는 균형이 잘 맞을 경우 높이가 log_2-n 에 근접할 수 있다. 마찬가지로 d진 검색 트리가 균형이 잘 맞으면 높이가 log_d-n에 근접할 수 있다. 또한 B 트리는 루트를 제외한 노드는 최소 └d/2┘개의 자식을 가져야 하므로 B 트리의 깊이는 최악의 경우에도 대략 log_d/2-n 보다 깊을 수 없다.

 

---

B 트리의 깊이는 다음의 범위에서 결정된다.

[log_d-n, log_d/2-n]

---

 

B 트리의 작업 수행시간은 디스크 접근 횟수를 기준으로 하며 B 트리의 모든 작업의 시간 복잡도는 점근적으로 Ο(logn)이 된다.

 

※ 노드를 메모리에 올린 이후 작업 시간이 디스크 접근 시간에 비하면 무시할 수 있을 정도로 작기 때문에 디스크 접근 횟수를 기준으로 한다.

 

B 트리 구현

다진 검색 트리인 B 트리를 구현한다.

 

BTree.h

#pragma once
#include "../Common.h"
#include <queue>

using std::queue;

struct BTreeNode;
class BTreeNodeKeyManager;

/// <summary>
/// B 트리의 노드에서 사용할 키
/// </summary>
struct BTreeNodeKey
{
	BTreeNodeKey() : prev(nullptr), left(nullptr), value(0), right(nullptr), next(nullptr) {}

	void Clear();
	void Set(int data);

	void AddKeyToPrev(BTreeNodeKey* newKey);
	void AddKeyToNext(BTreeNodeKey* newKey);

	void SwapValue(BTreeNodeKey* other);

	BTreeNodeKey* prev;
	BTreeNode* left;
	int value;
	BTreeNode* right;
	BTreeNodeKey* next;
};

/// <summary>
/// B 트리에 사용할 노드
/// </summary>
struct BTreeNode
{
	static const size_t TotalKeyCount{ 3 };

	~BTreeNode();

	void Clear();
	bool Insert(int data);
	bool Insert(BTreeNodeKey* newKey);

	bool Delete(int data);
	bool Delete(BTreeNodeKey* deleteKey);

	bool IsAbleToInsert();
	bool IsContainsData(int data);
	bool IsAbleToWithdraw();

	BTreeNodeKey* GetSmallestKey();
	BTreeNodeKey* GetBiggestKey();
	BTreeNodeKey* GetMiddleKey();

	BTreeNodeKey* GetKey(int data);

	BTreeNode* parent;
	BTreeNodeKey* keyRoot;
	size_t size;

	BTreeNodeKeyManager* keyManager;
};

/// <summary>
/// B 트리에서 노드의 재활용을 위한 매니저
/// </summary>
class BTreeNodeManager
{
public:
	BTreeNodeManager();
	~BTreeNodeManager();

	void Push(BTreeNode* node);
	BTreeNode* Pop();

private:
	BTreeNode* nodes;
	BTreeNodeKeyManager* keyManager;
};

/// <summary>
/// B 트리에서 노드의 키를 재활용 하기위한 매니저
/// </summary>
class BTreeNodeKeyManager
{
public:
	~BTreeNodeKeyManager();

	void Push(BTreeNodeKey* node);
	BTreeNodeKey* Pop();

private:
	BTreeNodeKey* keys;
};

/// <summary>
/// 연결 자료구조를 이용한 B 트리
/// </summary>
class BTree
{
public:
	BTree();
	~BTree();

	bool Exists(int data);
	void Insert(int data);
	void Delete(int data);

	void PrintTree();

private:
	void ClearOverflow(BTreeNode* node);
	void ClearUnderflow(BTreeNode* node);

	BTreeNode* SplitNodeWithKey(BTreeNode* node, BTreeNodeKey* key);
	BTreeNode* MergeNodeWithKey(BTreeNode* node, BTreeNodeKey* lsKey, BTreeNodeKey* rsKey);

private: // For Util Methods
	BTreeNode* GetProperNodeToInsert(int data);
	BTreeNode* GetProperNodeToDelete(int data);

private:
	BTreeNode* _root;
	BTreeNodeManager _nodeManager;
	queue<BTreeNode*> _queue;
};

 

BTree.cpp

#include "BTree.h"

#pragma region 노드
/// <summary>
/// 노드의 키를 초기화한다.
/// </summary>
void BTreeNodeKey::Clear()
{
	prev = nullptr;
	left = nullptr;
	value = 0;
	right = nullptr;
	next = nullptr;
}

/// <summary>
/// 주어진 값을 키에 저장한다.
/// </summary>
/// <param name="data">저장할 값</param>
void BTreeNodeKey::Set(int data)
{
	value = data;
}

/// <summary>
/// 새 키를 기존 키의 왼쪽에 삽입한다.
/// </summary>
/// <param name="newKey">삽입할 키</param>
void BTreeNodeKey::AddKeyToPrev(BTreeNodeKey* newKey)
{
	BTreeNodeKey* prevKey{ prev };
	if (prevKey != nullptr)
	{
		prevKey->next = newKey;
		newKey->prev = prevKey;
		prevKey->right = newKey->left;
	}
	newKey->next = this;
	prev = newKey;

	left = newKey->right;
}

/// <summary>
/// 새 키를 기존 키의 오른쪽에 삽입한다.
/// </summary>
/// <param name="newKey">삽입할 키</param>
void BTreeNodeKey::AddKeyToNext(BTreeNodeKey* newKey)
{
	BTreeNodeKey* nextKey{ next };
	if (nextKey != nullptr)
	{
		nextKey->prev = newKey;
		newKey->next = nextKey;
		nextKey->left = newKey->right;
	}
	newKey->prev = this;
	next = newKey;

	right = newKey->left;
}

/// <summary>
/// 다른 키와 value를 교환한다.
/// </summary>
/// <param name="other">다른 키</param>
void BTreeNodeKey::SwapValue(BTreeNodeKey* other)
{
	int temp{ value };
	value = other->value;
	other->value = temp;
}

/// <summary>
/// B 트리 소멸자, 생성했던 키를 제거한다.
/// </summary>
BTreeNode::~BTreeNode()
{
	Clear();
}

/// <summary>
/// 노드를 초기화한다.
/// </summary>
void BTreeNode::Clear()
{
	parent = nullptr;
	size = 0;

	while (keyRoot != nullptr)
	{
		BTreeNodeKey* key{ keyRoot };
		keyRoot = key->next;
		key->Clear();
		keyManager->Push(key);
	}
}

/// <summary>
/// 노드에 데이터를 삽입한다.
/// </summary>
/// <param name="data">삽입할 데이터</param>
/// <returns>성공 여부</returns>
bool BTreeNode::Insert(int data)
{
	BTreeNodeKey* newKey{ keyManager->Pop() };
	newKey->Set(data);

	return Insert(newKey);
}

/// <summary>
/// 주어진 키를 노드의 키에 삽입한다.
/// </summary>
/// <param name="key">삽입할 키</param>
/// <returns>성공 여부</returns>
bool BTreeNode::Insert(BTreeNodeKey* newKey)
{
	if (keyRoot == nullptr)
	{
		keyRoot = newKey;
	}
	else
	{
		// 새 값이 노드에서 가장 작은 경우
		if (newKey->value < keyRoot->value)
		{
			keyRoot->AddKeyToPrev(newKey);
			keyRoot = newKey;
		}
		else
		{
			BTreeNodeKey* key{ keyRoot };
			BTreeNodeKey* prevKey{ nullptr };

			while (key != nullptr)
			{
				if (newKey->value < key->value)
				{
					prevKey = nullptr;
					key->AddKeyToPrev(newKey);
					break;
				}

				prevKey = key;
				key = key->next;
			}

			// 새 값이 노드에서 가장 큰 경우
			if (prevKey != nullptr)
			{
				prevKey->AddKeyToNext(newKey);
			}
		}
	}

	size++;

	return size <= TotalKeyCount;
}

/// <summary>
/// 주어진 데이터를 포함하는 키를 노드에서 제거한다.
/// </summary>
/// <param name="data">제거할 값</param>
/// <returns>성공 여부</returns>
bool BTreeNode::Delete(int data)
{
	BTreeNodeKey* key{ keyRoot };

	while (key != nullptr)
	{
		if (key->value == data)
		{
			return Delete(key);
		}
		key = key->next;
	}

	return false;
}

/// <summary>
/// 주어진 키를 노드에서 제거한다.
/// </summary>
/// <param name="deleteKey">제거할 키</param>
/// <returns>성공 여부</returns>
bool BTreeNode::Delete(BTreeNodeKey* deleteKey)
{
	BTreeNodeKey* prevKey{ deleteKey->prev };
	BTreeNodeKey* nextKey{ deleteKey->next };

	if (prevKey != nullptr)
	{
		prevKey->next = nextKey;
	}
	if (nextKey != nullptr)
	{
		nextKey->prev = prevKey;
	}

	if (deleteKey == keyRoot)
	{
		keyRoot = nextKey;
	}

	keyManager->Push(deleteKey);

	size--;

	return size >= TotalKeyCount / 2;
}

/// <summary>
/// 노드에 여유가 있는지 여부를 반환한다.
/// </summary>
/// <returns>삽입 가능한지 여부</returns>
bool BTreeNode::IsAbleToInsert()
{
	return size < TotalKeyCount;
}

/// <summary>
/// 현재 노드가 주어진 값을 포함하는지 여부를 반환한다.
/// </summary>
/// <param name="data">확인할 값</param>
/// <returns>값 포함 여부</returns>
bool BTreeNode::IsContainsData(int data)
{
	BTreeNodeKey* key{ keyRoot };
	while (key != nullptr)
	{
		if (key->value == data)
		{
			return true;
		}
		key = key->next;
	}
	return false;
}

/// <summary>
/// 이 노드에서 키를 인출해도 안정적인지 여부를 반환한다.
/// </summary>
/// <returns>키를 인출해도 안정적인지 여부</returns>
bool BTreeNode::IsAbleToWithdraw()
{
	return size > TotalKeyCount / 2;
}

/// <summary>
/// 가장 작은 키를 노드에서 떼어내 반환한다.
/// </summary>
/// <returns>가장 작은 키</returns>
BTreeNodeKey* BTreeNode::GetSmallestKey()
{
	BTreeNodeKey* key{ nullptr };
	if (keyRoot != nullptr)
	{
		key = keyRoot;
		keyRoot = keyRoot->next;
		keyRoot->prev = nullptr;
		key->next = nullptr;
	}
	size--;
	return key;
}

/// <summary>
/// 가장 큰 키를 노드에서 떼어내 반환한다.
/// </summary>
/// <returns>가장 큰 키</returns>
BTreeNodeKey* BTreeNode::GetBiggestKey()
{
	BTreeNodeKey* key{ nullptr };
	if (keyRoot != nullptr)
	{
		key = keyRoot;
		while (key->next != nullptr)
		{
			key = key->next;
		}

		if (key == keyRoot)
		{
			keyRoot = nullptr;
		}

		BTreeNodeKey* prev{ key->prev };
		if (prev != nullptr)
		{
			prev->next = nullptr;
			key->prev = nullptr;
		}
	}
	size--;
	return key;
}

/// <summary>
/// 노드의 키 중 중간 값을 가진 키를 떼어내 반환한다.
/// </summary>
/// <returns>중간 키</returns>
BTreeNodeKey* BTreeNode::GetMiddleKey()
{
	size_t midIdx = TotalKeyCount / 2;

	BTreeNodeKey* key{ nullptr };
	if (keyRoot != nullptr)
	{
		key = keyRoot;
		while (key->next != nullptr && midIdx > 0)
		{
			key = key->next;
			midIdx--;
		}

		if (key == keyRoot)
		{
			keyRoot = keyRoot->next;
		}

		BTreeNodeKey* prev{ key->prev };
		BTreeNodeKey* next{ key->next };
		if (prev != nullptr)
		{
			prev->next = next;
			key->prev = nullptr;
		}
		if (next != nullptr)
		{
			next->prev = prev;
			key->next = nullptr;
		}
	}
	size--;
	return key;
}

/// <summary>
/// 주어진 값을 가지는 키를 반환한다.
/// </summary>
/// <param name="data">찾을 값</param>
/// <returns>값을 가지는 키</returns>
BTreeNodeKey* BTreeNode::GetKey(int data)
{
	BTreeNodeKey* key{ keyRoot };
	while (key != nullptr)
	{
		if (key->value == data)
		{
			break;
		}
		key = key->next;
	}
	return key;
}
#pragma endregion

#pragma region 노드 매니저
/// <summary>
/// 노드 매니저 및 키 매니저를 초기화한다.
/// </summary>
BTreeNodeManager::BTreeNodeManager()
	: nodes(nullptr)
{
	keyManager = new BTreeNodeKeyManager();
}

/// <summary>
/// 가지고 있던 노드를 모두 안전하게 제거한다.
/// </summary>
BTreeNodeManager::~BTreeNodeManager()
{
	while (nodes != nullptr)
	{
		BTreeNode* node{ nodes };
		nodes = nodes->parent;
		delete node;
	}

	delete keyManager;
}

/// <summary>
/// 사용 완료한 노드를 저장한다.
/// </summary>
/// <param name="node">사용 완료한 노드</param>
void BTreeNodeManager::Push(BTreeNode* node)
{
	node->parent = nodes;
	nodes = node;
}

/// <summary>
/// 사용할 노드를 인출한다.
/// </summary>
/// <returns>사용할 노드</returns>
BTreeNode* BTreeNodeManager::Pop()
{
	BTreeNode* node{ nodes };

	if (node != nullptr)
	{
		nodes = node->parent;
		node->Clear();
	}
	else
	{
		node = new BTreeNode();
	}
	node->keyManager = keyManager;

	return node;
}

/// <summary>
/// 가지고 있던 키를 모두 안전하게 제거한다.
/// </summary>
BTreeNodeKeyManager::~BTreeNodeKeyManager()
{
	while (keys != nullptr)
	{
		BTreeNodeKey* node{ keys };
		keys = keys->next;
		delete node;
	}
}

/// <summary>
/// 사용 완료한 키를 반환한다.
/// </summary>
/// <param name="node">사용 완료한 키</param>
void BTreeNodeKeyManager::Push(BTreeNodeKey* key)
{
	key->next = keys;
	keys = key;
}

/// <summary>
/// 사용할 키를 인출한다.
/// </summary>
/// <returns>사용할 키</returns>
BTreeNodeKey* BTreeNodeKeyManager::Pop()
{
	BTreeNodeKey* node{ keys };

	if (node != nullptr)
	{
		keys = node->next;
		node->Clear();
	}
	else
	{
		node = new BTreeNodeKey();
	}

	return node;
}
#pragma endregion

#pragma region BTree Public Methods
/// <summary>
/// 필요한 값들을 생성한다.
/// </summary>
BTree::BTree()
	: _root(nullptr)
{
}

/// <summary>
/// B 트리가 제거될 때 사용한 모든 노드를 반환한다.
/// </summary>
BTree::~BTree()
{
}

/// <summary>
/// B 트리를 확인하여 주어진 값이 트리에 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="data">확인할 값</param>
/// <returns>존재 여부</returns>
bool BTree::Exists(int data)
{
	BTreeNode* node{ _root };
	while (node != nullptr)
	{
		BTreeNodeKey* key{ node->keyRoot };
		while (key != nullptr)
		{
			if (key->value == data)
			{
				return true;
			}

			if (data < key->value)
			{
				node = key->left;
				break;
			}
			else if (key->value < data)
			{
				if (key->next == nullptr || data < key->next->value)
				{
					node = key->right;
					break;
				}
			}
			
			key = key->next;
		}
	}
	
	return false;
}

/// <summary>
/// 주어진 값을 B 트리에 삽입한다.
/// </summary>
/// <param name="data">삽입할 값</param>
void BTree::Insert(int data)
{
	if (Exists(data))
	{
		return;
	}

	BTreeNode* node{ GetProperNodeToInsert(data) };
	if (!node->Insert(data))
	{
		ClearOverflow(node);
	}
}

/// <summary>
/// 주어진 값을 가지는 키를 B 트리에서 제거한다.
/// </summary>
/// <param name="data">제거할 값</param>
void BTree::Delete(int data)
{
	if (!Exists(data))
	{
		return;
	}

	BTreeNode* node{ GetProperNodeToDelete(data) };
	if (!node->Delete(data))
	{
		ClearUnderflow(node);
	}
}

/// <summary>
/// 트리를 텍스트로 출력한다.
/// </summary>
void BTree::PrintTree()
{
	std::cout << "\n--------------------\n";

	if (_root == nullptr)
	{
		std::cout << "EMPTY TREE";
	}
	else
	{
		int depth{ 0 };
		int nodeCount{ 1 };
		int counter{ 0 };

		_queue.push(_root);
		while (!_queue.empty())
		{
			BTreeNode* node{ _queue.front() };
			_queue.pop();

			if (counter == nodeCount)
			{
				depth++;
				counter = 0;
				nodeCount = depth * BTreeNode::TotalKeyCount + 1;
				std::cout << '\n';
			}

			BTreeNodeKey* key{ node->keyRoot };
			if (key->left != nullptr)
			{
				_queue.push(key->left);
			}

			std::cout << '[';
			while (key != nullptr)
			{
				if (key->right != nullptr)
				{
					_queue.push(key->right);
				}
				std::cout << key->value << (key->next != nullptr ? ", " : "");
				key = key->next;
			}
			std::cout << ']';

			counter++;
		}
	}

	std::cout << "\n--------------------\n";
}
#pragma endregion

#pragma region BTree Private Methods
/// <summary>
/// 오버플로우 발생한 노드를 정리한다.
/// </summary>
/// <param name="node">오버 플로우가 발생한 노드</param>
void BTree::ClearOverflow(BTreeNode* node)
{
	bool isDone{ false };

	BTreeNode* parent{ node->parent };
	// 루트 노드가 아닌 경우
	if (parent != nullptr)
	{
		BTreeNodeKey* lsKey{ nullptr };
		BTreeNodeKey* rsKey{ parent->keyRoot };
		while (rsKey != nullptr)
		{
			if (rsKey->left == node)
			{
				break;
			}
			lsKey = rsKey;
			rsKey = rsKey->next;
		}

		// 왼쪽 형제가 존재하고 삽입 가능한 경우
		if (lsKey != nullptr && lsKey->left != nullptr
			&& lsKey->left->IsAbleToInsert())
		{
			BTreeNodeKey* key{ node->GetSmallestKey() };
			lsKey->SwapValue(key);
			lsKey->left->Insert(key);
			isDone = true;
		}
		// 오른쪽 형제가 존재하고 삽입 가능한 경우
		else if (rsKey != nullptr && rsKey->right != nullptr
			&& rsKey->right->IsAbleToInsert())
		{
			BTreeNodeKey* key{ node->GetBiggestKey() };
			rsKey->SwapValue(key);
			rsKey->right->Insert(key);
			isDone = true;
		}
	}

	// 삽입 가능한 형제가 없는 경우
	if (!isDone)
	{
		BTreeNodeKey* key{ node->GetMiddleKey() };
		BTreeNode* newNode{ SplitNodeWithKey(node, key) };
		key->left = node;
		key->right = newNode;

		if (node == _root)
		{
			BTreeNode* newRootNode{ _nodeManager.Pop() };
			newRootNode->Insert(key);
			node->parent = newNode->parent = newRootNode;
			_root = newRootNode;
		}
		else if (!parent->Insert(key))
		{
			ClearOverflow(parent);
		}
	}
}

/// <summary>
/// 언더플로우가 발생한 노드를 정리한다.
/// </summary>
/// <param name="node">언더 플로우가 발생한 노드</param>
void BTree::ClearUnderflow(BTreeNode* node)
{
	// 노드가 루트인 경우
	if (node == _root)
	{
		if (node->size == 0)
		{
			_nodeManager.Push(node);
			_root = nullptr;
		}
	}
	else
	{
		bool isDone{ false };

		BTreeNode* parent{ node->parent };
		BTreeNodeKey* lsKey{ nullptr };
		BTreeNodeKey* rsKey{ parent->keyRoot };
		while (rsKey != nullptr)
		{
			if (rsKey->left == node)
			{
				break;
			}
			lsKey = rsKey;
			rsKey = rsKey->next;
		}

		// 왼쪽 형제가 존재하고 키 인출 가능한 경우
		if (lsKey != nullptr && lsKey->left != nullptr
			&& lsKey->left->IsAbleToWithdraw())
		{
			BTreeNodeKey* key{ lsKey->left->GetBiggestKey() };
			lsKey->SwapValue(key);
			node->Insert(key);
			isDone = true;
		}
		// 오른쪽 형제가 존재하고 키 인출 가능한 경우
		else if (rsKey != nullptr && rsKey->right != nullptr
			&& rsKey->right->IsAbleToWithdraw())
		{
			BTreeNodeKey* key{ rsKey->right->GetSmallestKey() };
			rsKey->SwapValue(key);
			node->Insert(key);
			isDone = true;
		}

		// 인출 가능한 형제가 없는 경우
		if (!isDone)
		{
			BTreeNodeKey* key{ rsKey != nullptr ? rsKey : lsKey };
			BTreeNode* mergeNode{ MergeNodeWithKey(node, lsKey, rsKey) };

			if (key != nullptr)
			{
				if (key->prev != nullptr)
				{
					key->prev->right = mergeNode;
				}
				if (key->next != nullptr)
				{
					key->next->left = mergeNode;
				}

				if (parent == _root && _root->size == 1)
				{
					parent->Delete(key);
					_nodeManager.Push(parent);
					_root = mergeNode;
				}
				else if (!parent->Delete(key))
				{
					ClearUnderflow(parent);
				}
			}
		}
	}
}

/// <summary>
/// 노드를 주어진 키를 기준으로 분할하고 새로 생성된 노드를 반환한다.
/// </summary>
/// <param name="node">분할할 노드</param>
/// <param name="key">기준 키</param>
/// <returns>분할된 새 노드</returns>
BTreeNode* BTree::SplitNodeWithKey(BTreeNode* node, BTreeNodeKey* key)
{
	BTreeNode* newNode{ _nodeManager.Pop() };
	newNode->parent = node->parent;

	while (true)
	{
		BTreeNodeKey* targetKey{ node->GetBiggestKey() };
		if (targetKey->value < key->value)
		{
			node->Insert(targetKey);
			break;
		}

		newNode->Insert(targetKey);
	}

	return newNode;
}

/// <summary>
/// 주어진 키를 기준으로 노드를 병합한다.
/// </summary>
/// <param name="node">병합할 노드</param>
/// <param name="lsKey">왼쪽 부모키</param>
/// <param name="rsKey">오른쪽 부모키</param>
/// <returns>병합된 노드</returns>
BTreeNode* BTree::MergeNodeWithKey(BTreeNode* node, BTreeNodeKey* lsKey, BTreeNodeKey* rsKey)
{
	BTreeNodeKey* mergeKey{ nullptr };
	BTreeNode* mergeNode{ nullptr };

	if (rsKey != nullptr)
	{
		mergeKey = rsKey;
		mergeNode = rsKey->right;
	}
	else
	{
		mergeKey = lsKey;
		mergeNode = lsKey->left;
	}

	while (node->size > 0)
	{
		BTreeNodeKey* key{ node->GetSmallestKey() };
		mergeNode->Insert(key);
	}
	mergeNode->Insert(mergeKey->value);

	_nodeManager.Push(node);

	return mergeNode;
}
#pragma endregion

#pragma region BTree Util Methods
/// <summary>
/// 주어진 data를 삽입할 수 있는 적절한 노드를 찾아 반환한다.
/// </summary>
/// <param name="data">삽입할 값</param>
/// <returns>데이터를 삽입할 수 있는 노드</returns>
BTreeNode* BTree::GetProperNodeToInsert(int data)
{
	if (_root == nullptr)
	{
		_root = _nodeManager.Pop();
		return _root;
	}

	BTreeNode* node{ _root };
	BTreeNode* prevNode{ node };

	while (node != nullptr)
	{
		BTreeNodeKey* key{ node->keyRoot };
		while (key != nullptr)
		{
			if (data < key->value)
			{
				prevNode = node;
				node = key->left;
				break;
			}
			else if (key->value < data)
			{
				if (key->next == nullptr || data < key->next->value)
				{
					prevNode = node;
					node = key->right;
					break;
				}
			}

			key = key->next;
		}
	}
	
	return prevNode;
}

/// <summary>
/// 주어진 값을 카진 키를 제거하기 위해 적절한 노드를 찾아 반환한다.
/// </summary>
/// <param name="data">제거할 값</param>
/// <returns>삭제를 위한 노드</returns>
BTreeNode* BTree::GetProperNodeToDelete(int data)
{
	BTreeNode* node{ _root };
	BTreeNode* leafNode{ nullptr };

	while (node != nullptr)
	{
		if (node->IsContainsData(data))
		{
			BTreeNodeKey* key{ node->GetKey(data) };
			leafNode = node;
			while (key->right != nullptr)
			{
				leafNode = key->right;
				key = leafNode->keyRoot;
			}
			break;
		}

		BTreeNodeKey* key{ node->keyRoot };
		while (key != nullptr)
		{
			if (data < key->value)
			{
				node = key->left;
				break;
			}
			else if (key->value < data)
			{
				if (key->next == nullptr || data < key->next->value)
				{
					node = key->right;
					break;
				}
			}

			key = key->next;
		}
	}

	if (leafNode != nullptr && leafNode != node)
	{
		BTreeNodeKey* key{ node->GetKey(data) };
		BTreeNodeKey* leafKey{ leafNode->keyRoot };
		key->SwapValue(leafKey);
		node = leafNode;
	}

	return leafNode;
}
#pragma endregion

 

main.cpp

#include "Common.h"
#include "검색트리/BTree.h"

int main()
{
	int n = 9;
	int* arr;

	// 동작 테스트를 위한 값
	arr = new int[n]{ 10, 5, 20, 3, 7, 15, 25, 1, 4 };

	BTree tree;
	for (int i = 0; i < n; i++)
	{
		tree.Insert(arr[i]);
		tree.PrintTree();
	}

	tree.Delete(5);
	tree.PrintTree();

	tree.Delete(10);
	tree.PrintTree();

	tree.Delete(15);
	tree.PrintTree();

	tree.Delete(1);
	tree.PrintTree();

	tree.Delete(3);
	tree.PrintTree();

	tree.Delete(20);
	tree.PrintTree();

	tree.Delete(7);
	tree.PrintTree();

	tree.Delete(4);
	tree.PrintTree();

	tree.Delete(25);
	tree.PrintTree();

	delete[] arr;
}

 

실행결과

--------------------
[10]
--------------------

--------------------
[5, 10]
--------------------

--------------------
[5, 10, 20]
--------------------

--------------------
[5]
[3][10, 20]
--------------------

--------------------
[5]
[3][7, 10, 20]
--------------------

--------------------
[7]
[3, 5][10, 15, 20]
--------------------

--------------------
[10]
[3, 5, 7][15, 20, 25]
--------------------

--------------------
[3, 10]
[1][5, 7][15, 20, 25]
--------------------

--------------------
[3, 10]
[1][4, 5, 7][15, 20, 25]
--------------------

--------------------
[3, 10]
[1][4, 7][15, 20, 25]
--------------------

--------------------
[3, 15]
[1][4, 7][20, 25]
--------------------

--------------------
[3, 20]
[1][4, 7][25]
--------------------

--------------------
[4, 20]
[3][7][25]
--------------------

--------------------
[20]
[4, 7][25]
--------------------

--------------------
[7]
[4][25]
--------------------

--------------------
[4, 25]
--------------------

--------------------
[25]
--------------------

--------------------
EMPTY TREE
--------------------

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘