알고리즘...74

B 트리 삭제 처리

삽입 처리와 마찬가지로 일단 노드에서 키를 제거한 뒤 노드의 크기가 k / 2 보다 작아지면 언더플로우 처리를 진행한다.

 

먼저, 일반적인 삭제 연산을 구현한다.

 

BTreeNode

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

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

	size--;

	return size >= TotalKeyCount / 2;
}

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

 

BTree

/// <summary>
/// 주어진 값을 가지는 키를 B 트리에서 제거한다.
/// </summary>
/// <param name="data">제거할 값</param>
void BTree::Delete(int data)
{
	if (!Exists(data))
	{
		return;
	}

	BTreeNode* node{ GetContainsDataNode(data) };
	if (!node->Insert(data))
	{
		// Underflow 처리
	}
}

/// <summary>
/// 주어진 값 가지는 키를 포함하는 노드를 반환한다.
/// </summary>
/// <param name="data">가져올 값</param>
/// <returns>값을 가지는 키를 포함하는 노드</returns>
BTreeNode* BTree::GetContainsDataNode(int data)
{
	BTreeNode* node{ _root };

	while (node != nullptr)
	{
		if (node->IsContainsData(data))
		{
			return node;
		}

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

	return node;
}