數據結構之——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();
}

運行結果：