数据结构之——B-树

   B-树是一种适合外查找的平衡搜索多叉树，一棵M阶(M>2)的B树，是一棵平衡的M路平衡搜索树，可以是空树或者满足一下性质：

1. 根节点至少有两个孩子；

2. 每个非根节点有[2/M,M]个孩子；

3. 每个非根节点有[2/M-1,M-1]个关键字，并且以升序排列；

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间；

5. 所有的叶子节点都在同一层；

这里要提的是，2/M要上取整，也就是当为偶数个进行除二的时候取上半部分的中间数；

下面是对于B-树的简单实现，最主要的是插入的过程：

#pragma once

#include <iostream>
using namespace std;

template <class K, int M = 3>
struct BTreeNode
{
	K _key[M];//存放关键值数组
	BTreeNode* _subs[M+1];//存放孩子结点的数组
	BTreeNode* _parent;//指向父节点的指针
	int _size;//表示当前结点的关键值个数

	BTreeNode()
		:_parent(NULL)
		,_size(0)
	{
		for(int i = 0; i < M; ++i)
			_key[i] = K();

		for(int i = 0; i < M+1; ++i)
			_subs[i] = NULL;
	}
};

template <class K, int M = 3>
struct mypair
{
	BTreeNode<K, M>* first;
	int second;

	mypair(BTreeNode<K, M>* f, int s)
		:first(f)
		,second(s)
	{}

	mypair<K, M>* operator->()
	{
		return this;
	}
};

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


	//插入关键值
	bool Insert(const K& key)
	{
		if(_root == NULL)//如果一个结点也没有，创建结点并将关键字放入，返回真
		{
			_root = new BTreeNode<K, M>;
			_root->_key[0] = key;
			_root->_size = 1;
			return true;
		}

		mypair<K, M> p = Find(key);
		if(p->second >= 0)//如果已有结点，则返回假
			return false;
		
		BTreeNode<K, M>* node = p->first;
		K newkey = key;
		BTreeNode<K, M>* sub = NULL;

		while(1)
		{
			int end = node->_size-1;
			while(end >= 0)//相当于用插入排序的方法将关键值插入合适的位置
			{
				if(newkey < node->_key[end])
				{
					node->_key[end+1] = node->_key[end];
					node->_subs[end+2] = node->_subs[end+1];
				}
				else
					break;
				--end;
			}
			++end;
			node->_key[end] = newkey;
			node->_subs[end+1] = sub;
			++(node->_size);

			if(node->_size >= M)//当一个结点中关键值个数等于空间大小时就要进行向上分裂
			{
				int mid = (M-1)/2;//首先上取整拿出中间数
				if(node == _root)//如果分裂到了根结点
				{
					BTreeNode<K, M>* tmp = new BTreeNode<K, M>;//重新new出一块空间存放右半边数据
					int index = 0;
					int i = mid+1;
					for(; i < node->_size; ++i)
					{
						tmp->_key[index] = node->_key[i];
						tmp->_subs[index] = node->_subs[i];//分裂移动数据的时候要将其子树一起移动
						++index;
						++(tmp->_size);
						node->_key[i] = K();//将分裂出去的数据的位置重新置位
						node->_subs[i] = NULL;
					}

					tmp->_subs[index] = node->_subs[i];
					node->_subs[i] = NULL;

					BTreeNode<K, M>* newroot = new BTreeNode<K, M>;//将中间数据向上提升作为新的根结点
					newroot->_key[0] = node->_key[mid];
					newroot->_subs[0] = node;
					newroot->_subs[1] = tmp;
					newroot->_size = 1;
					tmp->_parent = newroot;//更新父结点

					node->_key[mid] = K();
					node->_size = (node->_size) - (tmp->_size) - 1;
					node->_parent = newroot;
					_root = newroot;
					return true;
				}
				else
				{
					newkey = node->_key[mid];//因为不是根结点要向上插入中间结点，先保存
					BTreeNode<K, M>* tmp = new BTreeNode<K, M>;//重新new出一块空间存放右半边数据
					int index = 0;
					int i = mid+1;
					for(; i < node->_size; ++i)
					{
						tmp->_key[index] = node->_key[i];
						tmp->_subs[index] = node->_subs[i];
						++index;
						++(tmp->_size);
						node->_key[i] = K();//将分裂出去的数据的位置重新置位
						node->_subs[i] = NULL;
					}
					tmp->_subs[index] = node->_subs[i];//因为孩子比关键值要多一个，因此当循环出来时要记得
					node->_subs[i] = NULL;
					node->_key[mid] = K();
					tmp->_parent = node->_parent;
					node->_size = (node->_size) - (tmp->_size) - 1;

					sub = tmp;//将分裂复制完成的结点赋给下一步插入时要一块移动的变量保存
					node = node->_parent;//更新结点，向上其父结点进行插入
				}
			}
			else//如果插入结点后并没有满，则正确返回
				return true;
		}
	}

	//查找指定关键值
	mypair<K, M> Find(const K& key)
	{
		return _Find(_root, key);
	}

	//中序遍历打印B树
	void InOrder()
	{
		_InOrder(_root);
		cout<<endl;
	}

private:
	mypair<K, M> _Find(BTreeNode<K, M>* root, const K& key)
	{
		int i = 0;
		for(; i < root->_size; ++i)
		{
			if(root->_key[i] == key)//如果找到，返回
				return mypair<K, M>(root, i);
			else if(root->_key[i] > key)//如果要找的关键值小于当前关键值，则直接跳出去递归
				break;
			else//如果要找的关键值大，则继续向后查找
				continue;
		}
		
		if(root->_subs[i] == NULL)
			return mypair<K, M>(root, -1);//如果其孩子结点为NULL的时候一定找不到，就不用往下遍历了
		else
			return _Find(root->_subs[i], key);//如果不为空则继续遍历
	}

	//清除结点
	void _ClearBTree(BTreeNode<K, M>* root)
	{
		if(root == NULL)
			return;
		
		for(int i = 0; i <= root->_size; ++i)
		{
			_ClearBTree(root->_subs[i]);
		}//当遍历完一层所有的孩子之后，改层才能delete
		delete root;
	}

	//中序遍历
	void _InOrder(BTreeNode<K, M>* root)
	{
		if(root == NULL)
			return;
		
		int i = 0;
		for(; i < root->_size; ++i)
		{
			_InOrder(root->_subs[i]);//按照每一层的孩子去遍历
			cout<<root->_key[i]<<" ";//当遍历返回的时候往往就找到了当前子树的最左结点值
		}
		_InOrder(root->_subs[i]);//不要忘记比关键值多出来的一个子树
	}
private:
	BTreeNode<K, M>* _root;
};



//1.每一次插入结点的时候一定是在叶子结点进行插入
//2.每一次进行分裂将中间数向上提升插入的时候，其结点附带的孩子也一定是满的
void Test()
{
	BTree<int> bt;
	int arr[] = {53, 75, 139, 49, 145, 36, 101};
	for(int i = 0; i < sizeof(arr)/sizeof(arr[0]); ++i)
	{
		bt.Insert(arr[i]);
	}
	
	bt.InOrder();
}

运行结果：