B-樹基本操作的實作 利用C++模板類封裝

程式還未經過嚴格的測驗，不能保證完全正確，僅作為學習參考，同時如果遇見bug歡迎指出，（把B-樹當成集合用在codefoces上面提交了一題，AC了，感覺問題不大）
注釋感徑訓比較詳細，我就不多bb了，直接上代碼

/*
專案名：B-樹
作者：龍卡
完成時間：2020/12/21 0:04
個人感受：手撕B-樹真的太難了，要想寫好還得在每一步把所有可能的情況全部考慮完，除錯程序中遇到的最嚴重的bug就是par指標
的維護不到位，有很多情況沒有維護好，導致出了bug，本來以為會讓做平衡二叉樹的實驗，結果直接上B-樹，只能說 “老趙，可真有你的”
*/
#include<iostream>
#include<algorithm>
#include<deque>
using namespace std;
const int M = 5;//B-樹的階 
const int MAX_N = M - 1;//關鍵字個數最大值 
const int MIN_N = (M >> 1) + (M & 1) - 1;//最小值 
const int SIZE = M + 1 + 1;//key，pchild的真實容量,M+1是為了下標，再+1是為了處理插入的情況
const int MID = (M >> 1) + (M & 1);//m/2向上取整

template<typename T>
class BMTree;
template<typename T>
class result;

//#define private public//debug永遠滴神

template<class T>
class node {
private:
	int n;//關鍵字的個數 
	T key[SIZE];
	node<T>* pchild[SIZE];
	node<T>* par;
	node(int n, node<T>* par = NULL) :n(n), par(par) { for (int i = 0; i < SIZE; i++)pchild[i] = NULL; }//我真沒有壓行的嫌疑[捂臉]
	int insert_key(const T& value)//在key中插入value,回傳插入的位置下標
	{
		int pos= upper_bound(key + 1, key + n + 1, value) - key;
		for (int i = ++n; i > pos; i--)key[i] = key[i - 1],pchild[i]=pchild[i-1];
		key[pos] = value;
		return pos;
	}
	void delete_key(int pos)
	{
		if (pos<0 || pos>n)throw "delete_key Error:Index out of range.";
		for (int i = pos; i <=n; i++)key[i] = key[i + 1],pchild[i]=pchild[i+1];//這里小于等于n是為了讓沒用的指標保持為空,避免插入時候的隱患
		n--;
	}
	node<T>* split()//自己作為左兒子分裂，回傳分裂后的右兒子指標
	{
		node<T>* lchild = this, * rchild = new node(M/2,this->par);
		this->n = MID - 1;
		for (int i = MID+1; i <= M; i++)
			rchild->key[i-MID] = lchild->key[i];
		for (int i = MID; i <= M; i++)
			rchild->pchild[i-MID] = lchild->pchild[i];
		return rchild;
	}
	bool too_big()const { return n > MAX_N; }
	bool rich()const { return n > MIN_N; }//大于最小值說明可以刪掉一個，就比較富有的啦
	bool too_small()const { return n < MIN_N; }
	static node<T>* merge(node<T>* a, node<T>* b,const T& value)//左a右b，順序很要緊
	{
		a->key[++(a->n)] = value;
		a->pchild[a->n] = b->pchild[0];
		for (int i = 1; i <= b->n; i++)a->key[i+a->n]=b->key[i], a->pchild[i+a->n]=b->pchild[i];
		a->n += b->n;
		delete b;
		return a;
	}
	friend class BMTree<T>;
	friend class result<T>;
};

template<typename T>
class result {
public:
	bool tag;
	int i;
	node<T>* p;
	deque<int> path;
	result() {}
	result(node<T>* p, int i, bool tag,const deque<int> &path) :p(p), i(i), tag(tag),path(path) {}
	void show()
	{
		cout << "R";
		for (deque<int>::iterator ite = path.begin(); ite != path.end(); ++ite)cout << *ite;
		cout << ",n=" << p->n<< "(";
		for (int i = 1; i <= p->n; i++)cout << "," + !(i - 1) << p->key[i];
		cout << ")\n";
	}
};

template<typename T>
class BMTree
{
private:
	node<T>* head;
private:
	BMTree(BMTree& b) {}
public:
	BMTree() :head(NULL) {}
	~BMTree(){clear(head);}//洗掉樹中的所有結點
private:
	void refresh(node<T>* ptr){for (int i = 0; i <= ptr->n&&ptr->pchild[i]; i++)ptr->pchild[i]->par = ptr;}
	void clear(node<T>* ptr)
	{
		if (!ptr)return;
		for (int i = 0; i <= ptr->n; i++)clear(ptr->pchild[i]);
		delete ptr;
	}
	void split(node<T>* ptr)//從p結點開始分裂 
	{
		if (ptr->n <= MAX_N)return;//沒有超過需求
		node<T>* par = ptr->par;
		int i = 1;
		if (!par)//沒有父親結點，說明當前是頭節點
		{
			par = new node<T>(1);
			head = par;
			ptr->par = par;
			par->key[1] = ptr->key[MID];
		}
		else i = ptr->par->insert_key(ptr->key[MID]);
		node<T>* rchild = ptr->split(), * lchild = ptr;
		par->pchild[i - 1] = lchild;
		par->pchild[i] = rchild;
		refresh(rchild);//就這個bug可以de一天
		split(ptr->par);
	}
	void check(node<T>* ptr,node<T> *last=NULL)//debug用的，不必在意
	{
		if (!ptr)return;
		if (ptr->par != last)cout <<"Error 錯誤結點對應的首個關鍵字"<< ptr->key[1]<<'\n';
		for (int i = 0; i <= ptr->n; i++)check(ptr->pchild[i],ptr);
	}
	void merge(node<T>* ptr)
	{
		check(head);
		if (ptr->n >= MIN_N)return;
		if (ptr == head)
		{
			if (ptr->n > 0)return; //頭節點指標個數可以少于MIN_N;
			delete head;//結點被全部洗掉完了
			head = NULL;
			return;
		}
		node<T>* par = ptr->par, *rbro = NULL, * lbro = NULL;
		T* key = par->key;
		int i = upper_bound(key + 1, key + par->n + 1, ptr->key[1]) - key-1;
		if (i > 0)lbro = par->pchild[i - 1];
		if (i < par->n)rbro = par->pchild[i + 1];
		//這下面的很多父親結點沒有改變，導致錯誤（已被修復，不愧是我，?( ?`ω ?^ )?）
		if (lbro && lbro->rich())
		{
			ptr->insert_key(par->key[i]);
			ptr->pchild[1] = ptr->pchild[0];
			ptr->pchild[0] = lbro->pchild[lbro->n],par->key[i]=lbro->key[lbro->n];//將左兄弟的最大值提上去
			//洗掉再插入可能會有指標問題，記得清空指標
			lbro->delete_key(lbro->n);
			refresh(ptr);
			return;
		}
		if (rbro && rbro->rich())
		{
			ptr->insert_key(par->key[i+1]);
			ptr->pchild[ptr->n] = rbro->pchild[0], par->key[i+1] = rbro->key[1];//將右兄弟的最小值提上去
			rbro->pchild[0] = rbro->pchild[1];
			rbro->delete_key(1);
			refresh(ptr);
			return;
		}
		//沒有富裕的情況，可能會改變頭節點指標哦.
		node<T>* l = (rbro ? rbro : lbro),*r=ptr;
		if (l == rbro)std::swap(l, r);
		i = (rbro ? (i + 1):i);//i為兩者中間夾的key的位置編號
		ptr = node<T>::merge(l, r, par->key[i]);//merge了以后必須更新ptr，因為原來的可能被釋放了
		refresh(ptr);
		if (par == head&&par->n==1)//頭節點只有一個關鍵字了,要將其洗掉
		{
			delete head;
			head = ptr;
			head->par = NULL;
			return;
		}
		par->delete_key(i);
		par->pchild[i-1] = ptr;//把合并后的結點連上去
		merge(par);
	}
	node<T>* min_key(node<T>* root)
	{
		if (root == NULL)throw "mid_key ERROR:從終端結點進入函式！";
		if (root->pchild[0] == NULL)return root;
		else return min_key(root->pchild[0]);
	}
public:
	result<T> find(const T& value)const
	{
		return find(value, head);
	}
	result<T> find(const T& value,node<T> *root)const//查找成功回傳true
	{
		node<T>* ptr = root, * last = NULL;
		deque<int> que;
		bool found = false;
		int i = -1;
		while (ptr && !found)
		{
			T* key = ptr->key, n = ptr->n;
			i = upper_bound(key + 1, key + n + 1, value) - key - 1;//找到大于value的第一個值的位置的前趨 
			if (i > 0 && key[i] == value)found = true;
			else
			{
				last = ptr;
				ptr = ptr->pchild[i];
				que.push_back(i);
			}
		}
		if (found)return result<T>(ptr, i, true,que);
		else return result<T>(last, i, false,que);//沒找到回傳應該插入的位置，即 key的i - i+1之間 
	}
	bool insert(const T& value)//插入失敗說明已經存在 
	{
		result<T> pos = find(value);
		if (pos.tag)return false;
		if (head == NULL)
		{
			head = new node<T>(1, NULL);
			head->key[1] = value;
			return true;
		}
		//因為查找回傳的位置一定是終端結點，所以才能直接插入value 
		node<T>* ptr = pos.p;
		ptr->insert_key(value);
		if (ptr->too_big())split(ptr);//需要分裂 
		return true;
	}
	void show_in(node<T> *ptr,deque<int> &num)
	{
		if (!ptr)return;
		result<T> res;
		res.path = num,res.p=ptr;
		res.show();
		for (int i = 0; i <= ptr->n; i++)
			if (ptr->pchild[i])
			{
				num.push_back(i);
				show_in(ptr->pchild[i],num);
				num.pop_back();
			}
	}
	bool erase(const T& value){return erase(value, head);}
	bool erase(const T& value,node<T> *root)//在root子樹中洗掉
	{
		result<int> res = find(value,root);
		if (!res.tag)return false;//B-樹里面沒有對應關鍵字，洗掉失敗
		//洗掉
		//1.找到要洗掉的關鍵字對應的結點
		//2.若該節點為終端結點，那么直接洗掉關鍵字，不是的話，就把關鍵字對應的右子樹的最小值拿過來，同時在右子樹洗掉它
		node<T>* ptr = res.p;
		int i = res.i;
		if (ptr->pchild[0] == NULL)
		{
			ptr->delete_key(i);//洗掉的時候個數肯定不會超標，delete_key不會下標越界
			merge(ptr);
		}
		else
		{
			node<T>* k = min_key(ptr->pchild[i]);//右子樹最小值
			ptr->key[i] = k->key[1];
			erase(k->key[1],ptr->pchild[i]);
		}
		return true;
	}
	void show(){deque<int> que;show_in(head,que);}
};
int main()
{
	//freopen("input.txt","r",stdin);
	BMTree<int> tree;
	int x;
	while (true)
	{
		cout << "1.插入關鍵字 \n2.洗掉關鍵字 \n3.查找關鍵字 \n4.層次遍歷輸出B-樹所有結點 \n5.結束程式\n";
		cin >> x;
		result<int> res;
		switch (x)
		{
			case 1:
				cout << "輸入要插入的關鍵字：";
				cin >> x;
				if (!tree.insert(x))cout << "插入失敗\n";
				//tree.show();
				cout << endl;
				break;
			case 2:
				cout << "輸入要洗掉的關鍵字：";
				cin >> x;
				cout << (tree.erase(x) ? "洗掉成功！":"洗掉失敗，結點不存在")<<endl;
				break;
			case 3:
				cout << "輸入要查找的關鍵字：";
				cin >> x;
				res = tree.find(x);
				if (!res.tag)
					cout << "關鍵字不存在！\n";
				else res.show();
				break;
			case 4:
				tree.show();//深度遍歷,還需要改成寬度優先遍歷
				break;
			case 5:
				return 0;
		default:
			break;
		}
	}
	return 0;
}