#include <iostream>
using namespace std;

namespace BST
{
	template<class T>
	struct TreeNode
	{
		T _key;
		TreeNode<T>* _left;
		TreeNode<T>* _right;

		TreeNode()
			:_key(T())
			, _left(nullptr)
			, _right(nullptr)
		{}

		TreeNode(const T& key)
			:_key(key)
			, _left(nullptr)
			, _right(nullptr)
		{}
	};

	template<class T>
	struct Compare
	{
		bool operator()(const T& left, const T& right) { return left > right; }
	};

	//二叉搜索树
	template<class T, class Com = Compare<T>>
	class BSTree
	{
		using NodeType = TreeNode<T>;
		using TreeType = BSTree<T, Com>;
	public:
		BSTree()
			:_root(nullptr)
			, _size(0)
		{}

		BSTree(const TreeType& bst)
			:_root(nullptr)
			, _size(0)
		{
			_root = Copy(bst._root);
			_size = bst._size;
		}

		TreeType& operator=(TreeType bst)
		{
			swap(bst); //我们自己实现的交换函数
			return *this;
		}

		bool Insert(const T& key)
		{
			if (_root == nullptr)
			{
				NodeType* newnode = new NodeType(key);
				_root = newnode;
				_size = 1;
				return true;
			}

			NodeType* parent = _root;
			NodeType* cur = _root;
			while (cur)
			{
				parent = cur;
				//节点值小于key
				if (_com(key, cur->_key)) cur = cur->_right;
				//节点值大于key
				else if (_com(cur->_key, key)) cur = cur->_left;
				else return false;
			}

			NodeType* newnode = new NodeType(key);
			if (_com(key, parent->_key)) parent->_right = newnode;
			else parent->_left = newnode;

			++_size;
			return true;
		}

		bool Erase(const T& key)
		{
			if (_root == nullptr) return false;

			//删除节点
			NodeType* parent = nullptr;
			NodeType* cur = _root;
			//找节点
			while (cur)
			{
				//节点值小于key
				if (_com(key, cur->_key))
				{
					parent = cur;
					cur = cur->_right;
				}
				//节点值大于key
				else if (_com(cur->_key, key))
				{
					parent = cur;
					cur = cur->_left;
				}
				else //找到了 开始删除
				{
					if (cur->_right == nullptr) //删除的节点只有左子树
					{
						NodeType* DelNode = cur;
						//改变链接关系
						//如果要删除的是根节点
						if (cur == _root) _root = cur->_left;
						else //非根节点
						{
							if (parent->_left == cur) parent->_left = cur->_left;
							else parent->_right = cur->_left;
						}
						delete DelNode;
					}
					else if (cur->_left == nullptr) //删除的节点只有右子树
					{
						NodeType* DelNode = cur;
						//改变链接关系
						//如果要删除的是根节点
						if (cur == _root) _root = cur->_right;
						else //非根节点
						{
							if (parent->_left == cur) parent->_left = cur->_right;
							else parent->_right = cur->_right;
						}
						delete DelNode;
					}
					else //子节点都在
					{
						//找替代 左子树的最大节点(最右节点) 右子树的最小节点(最左节点)
						//去左子树中找最大节点
						//NodeType* maxParent = cur;
						//NodeType* maxLeft = cur->_left;
						//while (maxLeft->_right)
						//{
						//	maxParent = maxLeft;
						//	maxLeft = maxLeft->_right;
						//}
						//cur->_key = maxLeft->_key;
						////接管替代节点的右孩子
						//if (maxParent->_left == maxLeft) maxParent->_left = maxLeft->_left;
						//else maxParent->_right = maxLeft->_left;
						//delete maxLeft;

						//去右子树中找最小节点
						NodeType* minParent = cur;
						NodeType* minRight = cur->_right;
						while (minRight->_left)
						{
							minParent = minRight;
							minRight = minRight->_left;
						}
						cur->_key = minRight->_key;
						//接管替代节点的右孩子
						if (minParent->_left == minRight) minParent->_left = minRight->_right;
						else minParent->_right = minRight->_right;
						delete minRight;
					}
					--_size;
					return true;
				}
			}

			return false; //找不到节点
		}

		bool Find(const T& key) //key模型
		{
			if (_root == nullptr) return false;

			NodeType* cur = _root;
			while (cur)
			{
				if (_com(key, cur->_key)) cur = cur->_right;
				else if (_com(cur->_key, key)) cur = cur->_left;
				else return true;
			}
			return false;
		}

		bool RecuInsert(const T& key) //递归插入
		{
			return _RecuInsert(key, _root);
		}

		bool RecuErase(const T& key) //递归删除
		{
			return _RecuErase(key, _root);
		}

		bool RecuFind(const T& key)
		{
			return _RecuFind(key, _root);
		}

		size_t size() { return _size; }

		void swap(TreeType& bst) //交换函数
		{
			//也可以调用库中的swap
			NodeType* root = bst._root;
			bst._root = _root;
			_root = root;

			Com com = bst._com;
			bst._com = _com;
			_com = com;

			size_t sz = bst._size;
			bst._size = _size;
			_size = sz;
		}

		void clear() //清空节点
		{
			Destroy(_root);
			_root = nullptr;
		}

		//中序遍历打印
		void MidBfd()
		{
			_MidBfd(_root);
			cout << endl;
		}

		~BSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

	private:
		//前序拷贝一棵树
		NodeType* Copy(const NodeType* root)
		{
			if (root == nullptr) return nullptr;

			NodeType* newnode = new NodeType(root->_key);

			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);
			return newnode;
		}

		//中序
		void _MidBfd(NodeType* root)
		{
			if (root == nullptr) return;

			_MidBfd(root->_left);
			cout << root->_key << " ";
			_MidBfd(root->_right);
		}

		//后序销毁
		void Destroy(NodeType* root)
		{
			if (root == nullptr) return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

		bool _RecuInsert(const T& key, NodeType*& root) //递归插入
		{
			if (root == nullptr)
			{
				NodeType* newnode = new NodeType(key);
				root = newnode;
				return true;
			}

			if (_com(key, root->_key)) return _RecuInsert(key, root->_right);
			else if (_com(root->_key, key)) return _RecuInsert(key, root->_left);

			return false;
		}

		bool _RecuErase(const T& key, NodeType*& root) //递归删除
		{
			if (root == nullptr) return false;

			if (_com(key, root->_key)) return _RecuErase(key, root->_right);
			else if (_com(root->_key, key)) return _RecuErase(key, root->_left);
			else //找到了
			{
				NodeType* delNode = root;
				if (root->_left == nullptr) root = root->_right;
				else if (root->_right == nullptr) root = root->_left;
				else //两个子节点都存在
				{
					//找一个替代
					//找左边的最大节点
					NodeType* cur = root->_left;
					while (cur->_right) cur = cur->_right;

					//找右边的最小节点
					//NodeType* cur = root->_right;
					//while (cur->_left) cur = cur->_left;

					//将要删除的值与替代节点交换
					T tmp = root->_key;
					root->_key = cur->_key;
					cur->_key = tmp;

					return _RecuErase(key, root->_left); //转而删除子节点
					//return _RecuErase(key, root->_right); //转而删除子节点

				}
				delete delNode;
				return true;
			}
			return false;
		}

		bool _RecuFind(const T& key, NodeType* root)
		{
			if (root == nullptr) return false;

			if (_com(key, root->_key)) return _RecuFind(key, root->_right);
			else if (_com(root->_key, key)) return _RecuFind(key, root->_left);
			else return true;

			return false;
		}

	private:
		NodeType* _root; //根节点
		size_t _size;       //节点数量
		Com _com;        //比较函数
	};

	//二叉搜索树KV
	template<class KT,class VT , class Com = Compare<KT>>
	class KVBSTree
	{
		using NodeType = TreeNode<pair<KT,VT>>;
		using TreeType = KVBSTree<KT, VT, Com>;
	public:
		KVBSTree()
			:_root(nullptr)
			, _size(0)
		{}

		KVBSTree(const TreeType& bst)
			:_root(nullptr)
			, _size(0)
		{
			_root = Copy(bst._root);
			_size = bst._size;
		}

		TreeType& operator=(TreeType bst)
		{
			swap(bst); //我们自己实现的交换函数
			return *this;
		}

		bool Insert(const KT& key,const VT& value)
		{
			if (_root == nullptr)
			{
				NodeType* newnode = new NodeType({key,value});
				_root = newnode;
				_size = 1;
				return true;
			}

			NodeType* parent = _root;
			NodeType* cur = _root;
			while (cur)
			{
				parent = cur;
				//节点值小于key
				if (_com(key, cur->_key.first)) cur = cur->_right;
				//节点值大于key
				else if (_com(cur->_key.first, key)) cur = cur->_left;
				else return false;
			}

			NodeType* newnode = new NodeType({ key,value });
			if (_com(key, parent->_key.first)) parent->_right = newnode;
			else parent->_left = newnode;

			++_size;
			return true;
		}

		bool Erase(const KT& key)
		{
			if (_root == nullptr) return false;

			//删除节点
			NodeType* parent = nullptr;
			NodeType* cur = _root;
			//找节点
			while (cur)
			{
				//节点值小于key
				if (_com(key, cur->_key.first))
				{
					parent = cur;
					cur = cur->_right;
				}
				//节点值大于key
				else if (_com(cur->_key.first, key))
				{
					parent = cur;
					cur = cur->_left;
				}
				else //找到了 开始删除
				{
					if (cur->_right == nullptr) //删除的节点只有左子树
					{
						NodeType* DelNode = cur;
						//改变链接关系
						//如果要删除的是根节点
						if (cur == _root) _root = cur->_left;
						else //非根节点
						{
							if (parent->_left == cur) parent->_left = cur->_left;
							else parent->_right = cur->_left;
						}
						delete DelNode;
					}
					else if (cur->_left == nullptr) //删除的节点只有右子树
					{
						NodeType* DelNode = cur;
						//改变链接关系
						//如果要删除的是根节点
						if (cur == _root) _root = cur->_right;
						else //非根节点
						{
							if (parent->_left == cur) parent->_left = cur->_right;
							else parent->_right = cur->_right;
						}
						delete DelNode;
					}
					else //子节点都在
					{
						//找替代 左子树的最大节点(最右节点) 右子树的最小节点(最左节点)
						//去左子树中找最大节点
						//NodeType* maxParent = cur;
						//NodeType* maxLeft = cur->_left;
						//while (maxLeft->_right)
						//{
						//	maxParent = maxLeft;
						//	maxLeft = maxLeft->_right;
						//}
						//cur->_key = maxLeft->_key;
						////接管替代节点的右孩子
						//if (maxParent->_left == maxLeft) maxParent->_left = maxLeft->_left;
						//else maxParent->_right = maxLeft->_left;
						//delete maxLeft;

						//去右子树中找最小节点
						NodeType* minParent = cur;
						NodeType* minRight = cur->_right;
						while (minRight->_left)
						{
							minParent = minRight;
							minRight = minRight->_left;
						}
						cur->_key = minRight->_key;
						//接管替代节点的右孩子
						if (minParent->_left == minRight) minParent->_left = minRight->_right;
						else minParent->_right = minRight->_right;
						delete minRight;
					}
					--_size;
					return true;
				}
			}

			return false; //找不到节点
		}

		pair<pair<KT,VT>,bool> Find(const KT& key) //key-value模型 通过key找value
		{
			//这里使用pair再套一层pair，用于返回查询的结果是否有效
			//false表示查询返回值无效
			if (_root == nullptr) return { {},false };

			NodeType* cur = _root;
			while (cur)
			{
				if (_com(key, cur->_key.first)) cur = cur->_right;
				else if (_com(cur->_key.first, key)) cur = cur->_left;
				else return { cur->_key,true };
			}
			return { {},false };
		}

		size_t size() { return _size; }

		void swap(TreeType& bst) //交换函数
		{
			//也可以调用库中的swap
			NodeType* root = bst._root;
			bst._root = _root;
			_root = root;

			Com com = bst._com;
			bst._com = _com;
			_com = com;

			size_t sz = bst._size;
			bst._size = _size;
			_size = sz;
		}

		void clear() //清空节点
		{
			Destroy(_root);
			_root = nullptr;
		}

		//中序遍历打印
		void MidBfd()
		{
			_MidBfd(_root);
			cout << endl;
		}

		~KVBSTree()
		{
			Destroy(_root);
			_root = nullptr;
		}

	private:
		//前序拷贝一棵树
		NodeType* Copy(const NodeType* root)
		{
			if (root == nullptr) return nullptr;

			NodeType* newnode = new NodeType(root->_key);

			newnode->_left = Copy(root->_left);
			newnode->_right = Copy(root->_right);
			return newnode;
		}

		//中序
		void _MidBfd(NodeType* root)
		{
			if (root == nullptr) return;

			_MidBfd(root->_left);
			cout << root->_key.first << " : " << root->_key.second << endl;
			_MidBfd(root->_right);
		}

		//后序销毁
		void Destroy(NodeType* root)
		{
			if (root == nullptr) return;

			Destroy(root->_left);
			Destroy(root->_right);
			delete root;
		}

	private:
		NodeType* _root; //根节点
		size_t _size;       //节点数量
		Com _com;        //比较函数
	};
}