알고리즘...69

B 트리 삽입 함수 구현 진행

노드에 키를 삽입하기 위해 여러 확인이 필요한데 우선 단순히 키를 삽입하는 함수를 구현했다.

 

BTree::Insert

/// <summary>
/// 새 키를 기존 키의 왼쪽에 삽입한다.
/// </summary>
/// <param name="newKey">삽입할 키</param>
void BTreeNodeKey::AddKeyToPrev(BTreeNodeKey* newKey)
{
	BTreeNodeKey* prevKey{ prev };
	if (prevKey != nullptr)
	{
		prevKey->next = newKey;
		newKey->prev = prevKey;
	}
	newKey->next = this;
	prev = newKey;
}

/// <summary>
/// 새 키를 기존 키의 오른쪽에 삽입한다.
/// </summary>
/// <param name="newKey">삽입할 키</param>
void BTreeNodeKey::AddKeyToNext(BTreeNodeKey* newKey)
{
	BTreeNodeKey* nextKey{ next };
	if (nextKey != nullptr)
	{
		nextKey->prev = newKey;
		newKey->next = nextKey;
	}
	newKey->prev = this;
	next = newKey;
}

/// <summary>
/// 노드에 데이터를 삽입한다.
/// </summary>
/// <param name="data">삽입할 데이터</param>
bool BTreeNode::Insert(int data)
{
	if (size == TotalKeyCount)
	{
		return false;
	}

	if (keyRoot == nullptr)
	{
		keyRoot = keyManager->Pop();
		keyRoot->Set(data);
		size++;
		return true;
	}

	BTreeNodeKey* newKey{ keyManager->Pop() };
	newKey->value = data;

	// 현재 키 중 가장 작은 값인 경우
	if (data < keyRoot->value)
	{
		keyRoot->AddKeyToPrev(newKey);
		keyRoot = newKey;
		size++;
		return true;
	}

	BTreeNodeKey* key{ keyRoot };
	while (key->next != nullptr)
	{
		if (data < key->value)
		{
			key->AddKeyToPrev(newKey);
			size++;
			return true;
		}

		key = key->next;
	}

	key->AddKeyToNext(newKey);
	size++;

	return true;
}

 

그런데 단순히 이 함수만을 이용해 작업하기에는 다른 노드를 가져와 처리하도록 하는 게 쉽지가 않다.

 

루트 노드에서 삽입 가능한 노드를 문의해 최적 노드를 반환하도록 하는 함수를 만들고 해당 노드에 삽입 처리 후 사이즈 문제로 실패한 경우 오버플로우 처리로 넘어가도록 해야 할 것 같다.