Btree(B-樹)---C++

一棵M階(M>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足一下性質：

1. 根節點至少有兩個孩子

2. 每個非根節點有[ ,M]個孩子

3. 每個非根節點有[ -1,M-1]個關鍵字，并且以升序排列

4. key[i]和key[i+1]之間的孩子節點的值介于key[i]、key[i+1]之間

5. 所有的葉子節點都在同一層

ps： 是向上取整

#pragma once

template<class K, int M = 3>
struct BTreeNode
{
	K _keys[M];					// 關鍵字數組
	BTreeNode<K, M>* _subs[M + 1];	// 孩子數組
	size_t _size;				// 關鍵字的個數

	BTreeNode<K, M>* _parent;	// 父親

	BTreeNode()
		:_size(0)
		, _parent(NULL)
	{
		for (size_t i = 0; i < M + 1; ++i)
		{
			_subs[i] = NULL;
		}
	}
};

template<class K, class V>
struct Pair
{
	K _first;
	V _second;

	Pair(const K& k = K(), const V& v = V())
		:_first(k)
		, _second(v)
	{}
};

template<class K, int M = 3>
class BTree
{
	typedef BTreeNode<K, M> Node;
public:
	BTree()
		:_root(NULL)
	{}

	Pair<Node*, int> Find(const K& key)
	{
		Node* parent = NULL;
		Node* cur = _root;
		while (cur)
		{
			int i = 0;
			while (i < cur->_size && cur->_keys[i] < key)
			{
				++i;
			}

			if (cur->_keys[i] == key)
			{
				return Pair<Node*, int>(cur, i);
			}

			parent = cur;
			cur = cur->_subs[i];
		}

		return Pair<Node*, int>(parent, -1);
	}

	bool Insert(const K& key)
	{
		if (_root == NULL)
		{
			_root = new Node;
			_root->_keys[0] = key;
			++_root->_size;

			return true;
		}

		Pair<Node*, int> ret = Find(key);
		if (ret._second != -1)
		{
			return false;
		}

		K k = key;
		Node* cur = ret._first;
		Node* sub = NULL;

		// 在cur節點插入一個k
		while (1)
		{
			_InsertKey(cur, k, sub);
			if (cur->_size < M)
			{
				return true;
			}

			// 分裂
			int boundary = M / 2;

			Node* tmp = new Node;
			size_t index = 0;
			size_t size = cur->_size;

			// 拷貝key
			for (int i = boundary + 1; i < size; ++i)
			{
				tmp->_keys[index++] = cur->_keys[i];
				tmp->_size++;
				cur->_size--;
			}
			// 拷貝子節點
			index = 0;
			for (int i = boundary + 1; i <= size; ++i)
			{
				tmp->_subs[index] = cur->_subs[i];
				if (tmp->_subs[index])
					tmp->_subs[index]->_parent = tmp;

				++index;
			}

			k = cur->_keys[boundary];
			cur->_size--;

			// 沒有父親
			if (cur->_parent == NULL)
			{
				_root = new Node;
				_root->_keys[0] = k;
				_root->_subs[0] = cur;
				_root->_subs[1] = tmp;
				_root->_size = 1;

				tmp->_parent = _root;
				cur->_parent = _root;

				return true;
			}

			cur = cur->_parent;
			sub = tmp;
		}
	}

	void _InsertKey(Node* cur, const K& k, Node* sub)
	{
		int i = cur->_size - 1;
		while (i >= 0)
		{
			if (cur->_keys[i] > k)
			{
				cur->_keys[i + 1] = cur->_keys[i];
				cur->_subs[i + 2] = cur->_subs[i + 1];

				--i;
			}
			else
			{
				break;
			}
		}

		cur->_keys[i + 1] = k;
		cur->_subs[i + 2] = sub;
		if (sub)
		{
			sub->_parent = cur;
		}

		cur->_size++;
	}

	void InOrder()
	{
		_InOrder(_root);
		cout << endl;
	}

	void _InOrder(Node* root)
	{
		if (root == NULL)
		{
			return;
		}

		for (size_t i = 0; i < root->_size; ++i)
		{
			_InOrder(root->_subs[i]);
			cout << root->_keys[i] << " ";
		}

		_InOrder(root->_subs[root->_size]);
	}

protected:
	Node* _root;
};

void TestBTree1()
{
	BTree<int, 1024> t1;
	int a[] = { 53, 75, 139, 49, 145, 36, 101 };
	for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
	{
		t1.Insert(a[i]);
	}

	t1.InOrder();
}