알고리즘...61

B 트리 구현을 위한 노드 구조 확인

일단 하드웨어에 맞추지 않고 적당한 크기로 만들어 구조와 동작을 확인하고자 한다.

키를 4개를 가지고 자식 링크를 5개, 부모 링크를 1개 가지는 노드를 구성하자.

 

BTreeNode

struct BTreeNode
{
	BTreeNode* parent;
	BTreeNode* child0;
	int key1;
	BTreeNode* child1;
	int key2;
	BTreeNode* child2;
	int key3;
	BTreeNode* child3;
	int key4;
	BTreeNode* child4;
};

 

단순한 나열로는 사용에 굉장한 불편이 따르게 될 것 같다. 해소를 위해 키와 자식을 가리키는 키 구조체를 만들어야 할 것 같다.

 

BTreeNodeKey와 BTreeNode

/// <summary>
/// B 트리의 노드에서 사용할 키
/// </summary>
class BTreeNodeKey
{
	BTreeNode* left;
	int value;
	BTreeNode* right;
};

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

	BTreeNode() : parent(nullptr)
	{
		keys = new BTreeNodeKey[TotalKeyCount];
	}
	~BTreeNode()
	{
		delete[] keys;
	}

	BTreeNode* parent;
	BTreeNodeKey* keys;
};