#include 

using namespace std;

template 
struct BTreeNode
{
	K  _keys[M];
	BTreeNode* _subs[M + 1];
	BTreeNode* _parent;

	size_t _size;

	BTreeNode(const K& key)
		:_parent(NULL)
		, _size(0)
	{	
		for (int i = 0; i < M; ++i)
		{
			_keys[i] = 0;
		}
		for (int i = 0; i <= M; ++i)
		{
			_subs[i] = NULL;
		}
		_keys[_size++] = key;
	}
	~BTreeNode(){};
};

template 
class BTree
{
	
public:
	typedef BTreeNode Node;
	BTree()
		:_root(NULL)
	{}

	pair Find(const K& key)
	{
		if (_root == NULL)
		{
			return pair(NULL, -1);
		}
		Node* prev = NULL;
		Node* cur = _root;

		while (cur)
		{
			int i = 0;
			for (; i < (int)cur->_size; )
			{
				if (key>cur->_keys[i])
					++i;
				else if (key < cur->_keys[i]){
					break;
				}
				else
					return pair(cur, i);
			}
			prev = cur;
			cur = cur->_subs[i];
		}
		return pair(prev, -1);
	}

	bool Insert(const K& key)
	{
		if (_root == NULL)
		{
			_root = new Node(key);
			return true;
		}

		pair ret = Find(key);

		if (ret.second != -1)
			return false;
		Node* cur = ret.first;
		Node* prev = NULL;

		int i = cur->_size;
		while (i > ret.second&&key_keys[i-1])
		{
			cur->_keys[i ] = cur->_keys[i-1];
			--i;
		}
		cur->_keys[i] = key;
		++cur->_size;

		if (cur->_size < M)
			return true;

		int mid = M / 2;
		//K newKey = key;
		while (1){
			Node* newNode = NULL;
			//cout << M << endl;
			while (mid < M - 1)
			{
				if (newNode == NULL)
					newNode = new Node(cur->_keys[mid + 1]);
				else
					newNode->_keys[newNode->_size++] = cur->_keys[mid + 1];
				cur->_keys[mid + 1] = 0;
				newNode->_subs[newNode->_size - 1] = cur->_subs[mid+1];
				if (cur->_subs[mid+1])
					(cur->_subs[mid+1])->_parent = newNode;
				cur->_subs[++mid] = NULL;

				newNode->_subs[newNode->_size] = cur->_subs[mid+1];;
				if (cur->_subs[mid+1])
					(cur->_subs[mid+1])->_parent = newNode;

				cur->_subs[mid+1] = NULL;
				--cur->_size;
			}
			//cur->_subs[M / 2 + 1] = newNode;
			prev = cur->_parent;
			if (prev == NULL)
			{
				prev = new Node(cur->_keys[M / 2]);
				cur->_keys[M / 2] = 0;
				prev->_subs[0] = cur;
				prev->_subs[1] = newNode;
				cur->_parent = prev;
				newNode->_parent = prev;
				--cur->_size;
				_root = prev;
				return true;
			}

			i = prev->_size - 1;
			while (i >= 0 && prev->_keys[i] > cur->_keys[M / 2])
			{
				prev->_keys[i + 1] = prev->_keys[i];
				prev->_subs[i + 2] = prev->_subs[i+1];
				--i;
			}
			prev->_keys[i + 1] = cur->_keys[M / 2];
			prev->_subs[i + 2] = newNode;
			newNode->_parent = prev;
			cur->_subs[M / 2 + 1] = NULL;
			cur->_keys[M / 2] = 0;

			++prev->_size;
			--cur->_size;
			cur = prev;
			prev = cur->_parent;
			mid = M / 2;
			if (cur->_size < M)
				return true;
		}
		return true;
	}

	bool Remove(const K& key)
	{
		if (_root == NULL)
			return false;
		pair ret = Find(key);
		if (ret.second == -1)
			return false;
		Node* cur = ret.first;
		Node* prev = NULL;
		int index = ret.second;
		int pindex = 0;
		K newKey = key;
		while (cur)
		{
			prev = cur->_parent;//获取父节点

			if (cur->_subs[index] == NULL)//叶子节点 
			{
				if (cur->_size >= M / 2){//节点key 数量 >= M/2，直接删除
					for (int i = index; i < (int)cur->_size; ++i)
					{
						cur->_keys[i] = cur->_keys[i + 1];
					}
					cur->_size--;
					return true;
				}
				if (prev == NULL)//父为空 只有一个节点
				{
					if (cur->_size == 1)//只有一个key  删除后 释放节点 _root制空
					{
						_root = NULL;
						delete cur;
					}
					else//否则删除 key 移动其他
					{
						for (int i = index; i < (int)cur->_size; ++i)
						{
							cur->_keys[i] = cur->_keys[i + 1];
						}
					}
					return true;
				}
				else//父不为空
				{
					int dev = 0;
					for (; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1)
					{
						if (prev->_subs[dev] == cur)
							break;
					}
					if (dev !=0 && (int)prev->_subs[dev - 1]->_size > M / 2)//cur不为prev最左sub 找左边替代
					{
						Node* tmp = prev->_subs[dev - 1];
						cur->_keys[index] = prev->_keys[dev - 1];
						prev->_keys[dev - 1] = tmp->_keys[tmp->_size-1];
						tmp->_keys[tmp->_size - 1] = 0;
						tmp->_size--;
						return true;
					}
					if (dev != (int)prev->_size && (int)(prev->_subs[dev + 1]->_size) > M / 2)//不为最右 找右替代
					{

						Node* tmp = prev->_subs[dev + 1];
						cur->_keys[index] = prev->_keys[dev ];
						prev->_keys[dev ] = tmp->_keys[0];
						tmp->_keys[tmp->_size - 1] = 0;
						for (int i = 0; i <(int) tmp->_size; ++i)
						{
							tmp->_keys[i] = tmp->_keys[i + 1];
						}
						tmp->_size--;
						return true;
					}
					for (int i = index; i < (int)cur->_size; ++i)
					{
						cur->_keys[i] = cur->_keys[i + 1];
					}
					cur->_size--;
					//需要合并
					Node* ppNode = NULL;
					while (1){
						if (dev != 0)
						{
							ppNode = prev->_parent;
							Node* sub = prev->_subs[dev - 1];
							sub->_keys[sub->_size++] = prev->_keys[dev - 1];
							for (int i = 0; i <(int)cur->_size;++i)
							{
								sub->_keys[sub->_size++] = cur->_keys[i];			
							}
							for (int i = dev - 1; i < (int)prev->_size; ++i)
							{
								prev->_keys[i] = prev->_keys[i + 1];
								prev->_subs[i + 1] = prev->_subs[i + 2];
							}
							if (sub->_subs[0] == NULL){
								delete cur;
							}
							else
							{
								sub->_subs[sub->_size] = cur;
								cur->_parent = sub;
							}
							if ((int)prev->_size-- >1)
								return true;
							
							else
							{
								if (ppNode==NULL)
								{
									_root = sub;
									sub->_parent = NULL;
									delete prev;
									return true;
								}
								else
								{
									sub->_parent = prev->_parent;
									memcpy(prev, sub, sizeof(Node));
								
									delete sub;
									cur = prev;
									prev = ppNode;
									for (dev=0; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1)
									{
										if (prev->_subs[dev] == cur)
											break;
									}
									return true;
								}
							}
						}
						else
						{
							ppNode = prev->_parent;
							Node* sub = prev->_subs[dev +1];
							cur->_keys[cur->_size++] = prev->_keys[dev];
							for (int i = 0; i <(int)sub->_size;++i)
							{
								cur->_keys[cur->_size++] = sub->_keys[i];
							}
							for (int i = dev ; i < (int)prev->_size; ++i)
							{
								prev->_keys[i] = prev->_keys[i + 1];
								prev->_subs[i + 1] = prev->_subs[i + 2];
							}
							if (cur->_subs[0] == NULL){
								delete sub;
							}
							else
							{
								cur->_subs[cur->_size] = sub;
								sub->_parent = cur;
							}
							if ((int)prev->_size-- >1)
								return true;

							else
							{
								if (ppNode == NULL)
								{
									_root = cur;
									cur->_parent = NULL;
									delete prev;
									return true;
								}
								else
								{
									cur->_parent = prev->_parent;
									memcpy(prev, cur, sizeof(Node));

									delete cur;
									cur = prev;
									prev = ppNode;
									for (dev = 0; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1)
									{
										if (prev->_subs[dev] == cur)
											break;
									}
									return true;
								}
							}
						}
					}
				}
			}
			else//不为叶子
			{
				if (cur->_subs[index + 1]->_size >0)//找右孩子最小替代删除
				{
					Node* sub = cur->_subs[index + 1];
					while (sub->_subs[0])
					{
						sub = sub->_subs[0];
					}
					cur->_keys[index] = sub->_keys[0];
					cur = sub;
					index = 0;

				}
				else if (cur->_subs[index]->_size >0)//找左孩子最大替代
				{
					Node* sub = cur->_subs[index];
					int size=sub->_size;
					while (sub->_subs[0]){
						size = sub->_size;		
						sub = sub->_subs[size];
					}					
					cur->_keys[index] = sub->_keys[size - 1];
					cur = sub;
					index = (int)sub->_size;
	
				}
				else
				{
					delete cur->_subs[index];
					delete cur->_subs[index + 1];
					cur->_subs[index] = NULL;
					cur->_subs[index] = NULL;
				}
			}
		}	
		return true;
	}

	void Traverse()
	{
		_Traverse(_root);
		cout << endl;
	}

private:

	void _Traverse(Node* root)
	{
		if (root == NULL)
			return;
		int i = 0; 
		for (; i <(int) root->_size; ++i)
		{
			if (i == 0)
				_Traverse(root->_subs[0]);
			cout << root->_keys[i]<<" ";
			_Traverse(root->_subs[i+1]);
		}
	}

	Node* _root;
};