일지
알고리즘...73
niamdank
2021. 10. 20. 14:47
B 트리 삽입 메서드 오버플로우 처리
오버 플로우 처리 시 필요한 노드를 분할하는 함수 추가했으며 기존 키 삽입 시 좌우 자식을 적절하게 넘겨주는 처리를 추가했다.
BTreeNodeKey
/// <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;
}
BTree
/// <summary>
/// 오버플로우 발생한 노드를 정리한다.
/// </summary>
/// <param name="node">오버 플로우가 발생한 노드</param>
void BTree::ClearOverflow(BTreeNode* node)
{
bool isDone{ false };
BTreeNode* p{ node->parent };
// 루트 노드가 아닌 경우
if (p != nullptr)
{
BTreeNodeKey* lsKey{ nullptr };
BTreeNodeKey* rsKey{ p->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);
_root = node;
}
else if (!node->parent->Insert(key))
{
ClearOverflow(node->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;
}