알고리즘...78

B 트리 삭제 메서드 구현

언더 플로우 처리를 구현한다.

 

BTree

/// <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->prev != nullptr)
			{
				key->prev->right = mergeNode;
			}
			if (key->next != nullptr)
			{
				key->next->left = mergeNode;
			}

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

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

 

완료 후 삽입, 삭제 테스트 중 삽입에서 무한 루프에 빠지는 경우를 발견했다. 디버깅을 해 봐야 할 것 같다.