알고리즘...73

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;
}