알고리즘...76

삭제 알고리즘 수정

기존 삭제 시 단순히 해당 값을 포함하는 노드를 반환했다면 이번에는 적절한 처리를 위해 해당 노드가 자식 노드가 있으면 오른쪽 서브 트리에서 가장 작은 값을 가진 키의 값과 교환하여 리프 노드에서 삭제가 일어나도록 수정했다.

 

BTreeNodeKey

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

 

BTree

/// <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>
/// <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) };
			while (key->right != nullptr)
			{
				leafNode = key->right;
				key = leafNode->GetSmallestKey();
			}
			break;
		}
	}

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

	return leafNode;
}

 

이제 적절하게 삭제가 진행될 수 있으며 언더플로우 처리에도 버그가 발생하지 않을 것이다.