알고리즘...65

B 트리 삽입 처리 진행

삽입 처리 중 노드가 가득 찬 경우 새로운 노드를 만드는 코드 추가

 

BTreeNode

/// <summary>
/// 삽입 처리를 위한 적절한 노드를 반환한다.
/// </summary>
/// <param name="data">추가할 값</param>
/// <returns>적절한 노드</returns>
BTreeNode* BTreeNode::GetProperNodeToInsert(int data)
{
	for (int i = 0; i < size; i++)
	{
		if (data < keys[i].value)
		{
			return keys[i].left;
		}

		if (keys[i].value < data)
		{
			if (i == size)
			{
				return keys[i].right;
			}
			else if (data < keys[i + 1].value)
			{
				return keys[i].right;
			}
		}
	}
	return nullptr;
}

 

BTree::Insert

/// <summary>
/// 주어진 값을 B 트리에 삽입한다.
/// </summary>
/// <param name="data">삽입할 값</param>
void BTree::Insert(int data)
{
	if (_root == nullptr)
	{
		_root = _nodeManager.Pop();
		if (_root->Insert(data))
		{
			// 오버플로우 처리
			// 일반화
			return;
		}
		else
		{
			BTreeNode* node{ _root->GetProperNodeToInsert(data) };
			if (node == nullptr)
			{
				node = _nodeManager.Pop();
				node->parent = _root;
				// node에 대해서 재귀적 처리 진행
			}
		}
	}
}

 

이렇게 해 두고 보니 새로운 노드를 추가했을 때 루트 노드에 있는 값을 나눠서 새로운 노드에 넣어 키가 반 이상이 찰 수 있도록 수정해야 한다.