알고리즘...70

B 트리 삽입 메서드 구현 진행

적절한 노드를 검색 함수를 수정하여 다음과 같이 구현했다.

 

BTree::GetProperNodeToInsert(int data)

/// <summary>
/// 주어진 data를 삽입할 수 있는 적절한 노드를 찾아 반환한다.
/// </summary>
/// <param name="data">삽입할 값</param>
/// <returns>데이터를 삽입할 수 있는 노드</returns>
BTreeNode* BTree::GetProperNodeToInsert(int data)
{
	if (_root == nullptr)
	{
		_root = _nodeManager.Pop();
		return _root;
	}

	BTreeNode* node{ _root };
	BTreeNode* prevNode{ nullptr };

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

		BTreeNodeKey* key{ node->keyRoot };
		while (key != nullptr)
		{
			if (data < key->value)
			{
				prevNode = node;
				node = key->left;
				break;
			}
			else if (key->value < data)
			{
				if (key->next == nullptr || data < key->next->value)
				{
					prevNode = node;
					node = key->right;
					break;
				}
			}

			key = key->next;
		}
	}
	
	return prevNode;
}

 

이를 이용하면 기존 Insert 함수를 다음과 같이 단순화할 수 있다.

 

BTree:Insert

/// <summary>
/// 주어진 값을 B 트리에 삽입한다.
/// </summary>
/// <param name="data">삽입할 값</param>
void BTree::Insert(int data)
{
	if (Exists(data))
	{
		return;
	}

	BTreeNode* node{ GetProperNodeToInsert(data) };
	if (!node->Insert(data))
	{
		ClearOverflow(node, data);
	}
}

 

이를 위해 기존 BTreeNode 의 Insert 실패 조건을 삽입된 이후 크기가 제한 크기를 넘겼을 때로 변경했다.

 

BTreeNode::Insert

/// <summary>
/// 노드에 데이터를 삽입한다.
/// </summary>
/// <param name="data">삽입할 데이터</param>
bool BTreeNode::Insert(int data)
{
	if (keyRoot == nullptr)
	{
		keyRoot = keyManager->Pop();
		keyRoot->Set(data);
	}
	else
	{
		BTreeNodeKey* newKey{ keyManager->Pop() };
		newKey->Set(data);

		// 새 값이 노드에서 가장 작은 경우
		if (data < keyRoot->value)
		{
			keyRoot->AddKeyToPrev(newKey);
			keyRoot = newKey;
		}
		else
		{
			BTreeNodeKey* key{ keyRoot };
			BTreeNodeKey* prevKey{ nullptr };

			while (key != nullptr)
			{
				if (data < key->value)
				{
					prevKey = nullptr;
					key->AddKeyToPrev(newKey);
					break;
				}

				prevKey = key;
				key = key->next;
			}

			// 새 값이 노드에서 가장 큰 경우
			if (prevKey != nullptr)
			{
				prevKey->AddKeyToNext(newKey);
			}
		}
	}

	size++;

	return size <= TotalKeyCount;
}

 

이제 오버플로우가 발생하기 전 까지는 정상적으로 데이터 삽입이 가능해졌다.