프로그래밍 기초/알고리즘
B 트리 구현 및 테스트
niamdank
2021. 11. 11. 19:58
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 트리는 균형 잡힌 다진 검색 트리로 다음의 성질을 만족한다.
- 루트를 제외한 모든 노드는 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 트리에서의 삭제
입력된 값을 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 트리 작업 성능 분석
이진 검색 트리는 균형이 잘 맞을 경우 높이가 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
알고리즘 학습 및 예제 코드 작성을 위한 저장소. Contribute to NadanKim/Algorithm development by creating an account on GitHub.
github.com