알고리즘...64

B 트리 삽입 함수 구현 시작

먼저 삽입 처리를 수월하게 하기 위해 노드에 삽입 함수를 구현하고 삽입된 키의 개수를 수월하게 관리하기 위해 노드에 현재 키의 개수를 도입한다.

 

BTree.h

/// <summary>
/// B 트리의 노드에서 사용할 키
/// </summary>
struct BTreeNodeKey
{
	BTreeNodeKey() : left(nullptr), value(0), right(nullptr) {}

	void Clear();
	void Set(int data);

	BTreeNode* left;
	int value;
	BTreeNode* right;
};

/// <summary>
/// B 트리에 사용할 노드
/// </summary>
struct BTreeNode
{
	static const size_t TotalKeyCount{ 4 };

	BTreeNode();
	~BTreeNode();

	void Clear();

	bool Insert(int data);

	BTreeNode* parent;
	BTreeNodeKey* keys;
	size_t size;
};

 

BTree.cpp

/// <summary>
/// 노드의 키를 초기화한다.
/// </summary>
void BTreeNodeKey::Clear()
{
	left = nullptr;
	value = 0;
	right = nullptr;
}

/// <summary>
/// 주어진 값을 키에 저장한다.
/// </summary>
/// <param name="data">저장할 값</param>
void BTreeNodeKey::Set(int data)
{
	value = data;
}

/// <summary>
/// B 트리 노드 생성자, key를 정해진 개수만큼 생성한다.
/// </summary>
BTreeNode::BTreeNode()
	: parent(nullptr), size(0)
{
	keys = new BTreeNodeKey[TotalKeyCount];
}

/// <summary>
/// B 트리 소멸자, 생성했던 키를 제거한다.
/// </summary>
BTreeNode::~BTreeNode()
{
	delete[] keys;
}

/// <summary>
/// 노드를 초기화한다.
/// </summary>
void BTreeNode::Clear()
{
	parent = nullptr;
	for (int i = 0; i < TotalKeyCount; i++)
	{
		keys[i].Clear();
	}
}

/// <summary>
/// 노드에 값을 삽입할 수 있으면 삽입하고 true를 반환하고 아니면 false를 반환한다.
/// </summary>
/// <param name="data"></param>
/// <returns>성공 여부</returns>
bool BTreeNode::Insert(int data)
{
	if (TotalKeyCount <= size)
	{
		return false;
	}

	keys[size++].Set(data);

	return true;
}

 

이 과정에서 기존 검색 함수를 조금 더 최적화 할 수 있었다.

 

BTree::Exists

/// <summary>
/// B 트리를 확인하여 주어진 값이 트리에 존재하는지 여부를 반환한다.
/// </summary>
/// <param name="data">확인할 값</param>
/// <returns>존재 여부</returns>
bool BTree::Exists(int data)
{
	BTreeNode* node{ _root };
	while (node != nullptr)
	{
		for (int i = 0; i < node->size; i++)
		{
			if (node->keys[i].value == data)
			{
				return true;
			}

			if (data < node->keys[i].value)
			{
				node = node->keys[i].left;
				break;
			}

			if (node->keys[i].value < data)
			{
				if (i == node->size)
				{
					node = node->keys[i].right;
					break;
				}
				else if(data < node->keys[i + 1].value)
				{
					node = node->keys[i].right;
					break;
				}
			}
		}
	}
	
	return false;
}

 

현재 임시로 루트에 삽입을 하도록 만들었고 이를 일반화한 뒤 오버플로우에 대한 처리를 추가해야 한다.

 

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