數(shù)據(jù)結(jié)構(gòu)之——B-樹

   B-樹是一種適合外查找的平衡搜索多叉樹，一棵M階(M>2)的B樹，是一棵平衡的M路平衡搜索樹，可以是空樹或者滿足一下性質(zhì)：

1. 根節(jié)點(diǎn)至少有兩個(gè)孩子；

2. 每個(gè)非根節(jié)點(diǎn)有[2/M,M]個(gè)孩子；

3. 每個(gè)非根節(jié)點(diǎn)有[2/M-1,M-1]個(gè)關(guān)鍵字，并且以升序排列；

4. key[i]和key[i+1]之間的孩子節(jié)點(diǎn)的值介于key[i]、key[i+1]之間；

5. 所有的葉子節(jié)點(diǎn)都在同一層；

這里要提的是，2/M要上取整，也就是當(dāng)為偶數(shù)個(gè)進(jìn)行除二的時(shí)候取上半部分的中間數(shù)；

下面是對(duì)于B-樹的簡(jiǎn)單實(shí)現(xiàn)，最主要的是插入的過(guò)程：

#pragma once

#include <iostream>
using namespace std;

template <class K, int M = 3>
struct BTreeNode
{
	K _key[M];//存放關(guān)鍵值數(shù)組
	BTreeNode* _subs[M+1];//存放孩子結(jié)點(diǎn)的數(shù)組
	BTreeNode* _parent;//指向父節(jié)點(diǎn)的指針
	int _size;//表示當(dāng)前結(jié)點(diǎn)的關(guān)鍵值個(gè)數(shù)

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


	//插入關(guān)鍵值
	bool Insert(const K& key)
	{
		if(_root == NULL)//如果一個(gè)結(jié)點(diǎn)也沒(méi)有，創(chuàng)建結(jié)點(diǎn)并將關(guān)鍵字放入，返回真
		{
			_root = new BTreeNode<K, M>;
			_root->_key[0] = key;
			_root->_size = 1;
			return true;
		}

		mypair<K, M> p = Find(key);
		if(p->second >= 0)//如果已有結(jié)點(diǎn)，則返回假
			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)//相當(dāng)于用插入排序的方法將關(guān)鍵值插入合適的位置
			{
				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)//當(dāng)一個(gè)結(jié)點(diǎn)中關(guān)鍵值個(gè)數(shù)等于空間大小時(shí)就要進(jìn)行向上分裂
			{
				int mid = (M-1)/2;//首先上取整拿出中間數(shù)
				if(node == _root)//如果分裂到了根結(jié)點(diǎn)
				{
					BTreeNode<K, M>* tmp = new BTreeNode<K, M>;//重新new出一塊空間存放右半邊數(shù)據(jù)
					int index = 0;
					int i = mid+1;
					for(; i < node->_size; ++i)
					{
						tmp->_key[index] = node->_key[i];
						tmp->_subs[index] = node->_subs[i];//分裂移動(dòng)數(shù)據(jù)的時(shí)候要將其子樹一起移動(dòng)
						++index;
						++(tmp->_size);
						node->_key[i] = K();//將分裂出去的數(shù)據(jù)的位置重新置位
						node->_subs[i] = NULL;
					}

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

					BTreeNode<K, M>* newroot = new BTreeNode<K, M>;//將中間數(shù)據(jù)向上提升作為新的根結(jié)點(diǎn)
					newroot->_key[0] = node->_key[mid];
					newroot->_subs[0] = node;
					newroot->_subs[1] = tmp;
					newroot->_size = 1;
					tmp->_parent = newroot;//更新父結(jié)點(diǎn)

					node->_key[mid] = K();
					node->_size = (node->_size) - (tmp->_size) - 1;
					node->_parent = newroot;
					_root = newroot;
					return true;
				}
				else
				{
					newkey = node->_key[mid];//因?yàn)椴皇歉Y(jié)點(diǎn)要向上插入中間結(jié)點(diǎn)，先保存
					BTreeNode<K, M>* tmp = new BTreeNode<K, M>;//重新new出一塊空間存放右半邊數(shù)據(jù)
					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();//將分裂出去的數(shù)據(jù)的位置重新置位
						node->_subs[i] = NULL;
					}
					tmp->_subs[index] = node->_subs[i];//因?yàn)楹⒆颖汝P(guān)鍵值要多一個(gè)，因此當(dāng)循環(huán)出來(lái)時(shí)要記得
					node->_subs[i] = NULL;
					node->_key[mid] = K();
					tmp->_parent = node->_parent;
					node->_size = (node->_size) - (tmp->_size) - 1;

					sub = tmp;//將分裂復(fù)制完成的結(jié)點(diǎn)賦給下一步插入時(shí)要一塊移動(dòng)的變量保存
					node = node->_parent;//更新結(jié)點(diǎn)，向上其父結(jié)點(diǎn)進(jìn)行插入
				}
			}
			else//如果插入結(jié)點(diǎn)后并沒(méi)有滿，則正確返回
				return true;
		}
	}

	//查找指定關(guān)鍵值
	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)//如果要找的關(guān)鍵值小于當(dāng)前關(guān)鍵值，則直接跳出去遞歸
				break;
			else//如果要找的關(guān)鍵值大，則繼續(xù)向后查找
				continue;
		}
		
		if(root->_subs[i] == NULL)
			return mypair<K, M>(root, -1);//如果其孩子結(jié)點(diǎn)為NULL的時(shí)候一定找不到，就不用往下遍歷了
		else
			return _Find(root->_subs[i], key);//如果不為空則繼續(xù)遍歷
	}

	//清除結(jié)點(diǎn)
	void _ClearBTree(BTreeNode<K, M>* root)
	{
		if(root == NULL)
			return;
		
		for(int i = 0; i <= root->_size; ++i)
		{
			_ClearBTree(root->_subs[i]);
		}//當(dāng)遍歷完一層所有的孩子之后，改層才能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]<<" ";//當(dāng)遍歷返回的時(shí)候往往就找到了當(dāng)前子樹的最左結(jié)點(diǎn)值
		}
		_InOrder(root->_subs[i]);//不要忘記比關(guān)鍵值多出來(lái)的一個(gè)子樹
	}
private:
	BTreeNode<K, M>* _root;
};



//1.每一次插入結(jié)點(diǎn)的時(shí)候一定是在葉子結(jié)點(diǎn)進(jìn)行插入
//2.每一次進(jìn)行分裂將中間數(shù)向上提升插入的時(shí)候，其結(jié)點(diǎn)附帶的孩子也一定是滿的
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();
}

運(yùn)行結(jié)果：