template<class K,class T>
struct AvltreeNode
{
	AvltreeNode<K, T>* _left;
	AvltreeNode<K, T>* _right;
	AvltreeNode<K, T>* _parent;
	pair<K,T> _kv;
	int _bt;//平衡因子
	AvltreeNode(const pair<K,T>& t)
		: _left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(t)
		,_bt(0)
	{}
};

template<class K,class T>
class Avltree
{
public:
	typedef AvltreeNode<K, T> Node;//这里将树的节点重命名，用于下面更加便捷的使用树的节点
 priveat:
   Node* _root;//一棵树自然只会存在一个根节点
};

//下面是寻找插入节点的代码
if (_root == nullptr)
		{
			_root = new Node(v);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first > v.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < v.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;//这里是key相等的情况，avl树依旧是不允许重复key的差入这里直接返回false即可
			}
		}//当运行到这里的时候，代表的就是找到了需要插入的位置。

cur = new Node(v);//给cur创建空间，这一步用于下面的计算平衡因子
		if (parent->_kv.first < v.first)
		{
			parent->_right = cur;
			cur->_parent = parent;//完成三叉链的连接。
		}
		else
		{
			parent->_left = cur;
			cur->_parent = parent;
		}

while (parent)//防止出现更新到根节点了还在往上更新。
		{
			if (parent->_left == cur)
			{
				parent->_bt--;//更新平衡因子，因为cur插入在了parent的左边，所以这里是让parent的平衡因子--
			}
			else
			{
				parent->_bt++;//插入在右节点是让parent的平衡因子++
			}
			if (parent->_bt == 0)
			{
				//这是最好的一种情况在节点插入之后，parent的高度恰好是插入在1了低的那一端此时的整棵树都是平衡的可以直接结束插入
				break;
			}
			else if (parent->_bt == 1 || parent->_bt == -1)
			{
				//这里代表的是parent的高度已经改变了需要继续往上处理，这里可以使用递归但是，能够使用循环
				//还是尽量使用循环比较好
				cur = parent;//让cur等于parent
				parent = parent->_parent;//让parent继续往上
			}
			else if (parent->_bt == 2 || parent->_bt == -2)//此时已经存在了平衡问题需要旋转处理了
			{
				//这里就是需要旋转的情况
			}
			else
			{
				//出现了其它的问题，即在旋转之前已经不是一个AVL树了
				assert(false);
			}
		}
		return true;//在插入完成之后返回true
	}

//下面我来实现一个简单的左单旋(右边高)
//这里为了便于理解你可以将parent看作是抽象图中的30，subr则是60，sublr则是b子树的根节点（注意这里的b可能为空）
	void RotateL(Node* parent)//这里我们将节点平衡因子为2的节点设置为一个parent
	{
		Node* parent_parent = parent->_parent;
		Node* SubR = parent->_right; // 代表平衡因子为2节点的右节点
		Node* SubRL = SubR->_left;//同理上一个节点的左节点
		//记住左单旋的图
		parent->_right = SubRL;//让subr的左节点给parent的右节点
		//但是这里sunrl可能会空所以需要判断一下
		if (SubRL) {
			SubRL->_parent = parent;//此时的subrl的父节点已经改变了
		}
		SubR->_left = parent;//让subr的左节点指向parent
		parent->_parent = SubR;
		//但是在这里不要忘记了，我们的节点是一个三叉链的结构
		//所以下面我们还需要去修改parent的指针，否则依旧会出错
		//这里最后还需要单独的处理一下一种特殊的情况那就是
		//parent刚好就是根节点
		if (_root == parent)
		{
			_root = SubR;//需要更新一下根节点
			SubR->_parent = nullptr;//此时的subr是根节点，根节点自然不再存在父亲节点了
		}
		else//此时的根节点不是parent
		{
			if (parent_parent->_left == parent)
			{
				parent_parent->_left = SubR;
			}
			else
			{
				parent_parent->_right = SubR;
			}
			//让paren_parent原先指向parent的指针重新指向subr
			SubR->_parent = parent_parent;
		}//经过这一步如果这里的parent是一个局部的子树，我就能将这颗子树和上面的节点连接起来
		//最后我们需要修改一下这颗树的平衡因子。
		//根据抽象图，abc的平衡因子是不需要改变的，选哟改变平衡因子的是parent和subr的平衡因子
		parent->_bt = 0;
		SubR->_bt = 0;//修改平衡因子。
	}

//下面我们来完成右单旋（左边高）
	void RotateR(Node* parent) 
	{
		Node* SubL = parent->_left;//依旧是找到那三个节点
		Node* SubLr = SubL->_right;
		parent->_left = SubLr;
		if (SubLr) {
			SubLr->_parent = parent;//完成对parent左节点的重新赋值
		}
		SubL->_right = parent;
		Node* parent_parent = parent->_parent;//依旧是用于将此时我们旋转后的局部AVL树连接到整体树上
		parent->_parent = SubL;
		if (_root == parent)
		{
			_root = SubL;//这里依旧是parent是根节点的一种情况
			SubL->_parent = nullptr;//祖先节点无父亲。
		}
		else
		{
			if (parent_parent->_left == parent)
			{
				parent_parent->_left = SubL;
			}
			else
			{
				parent_parent->_right = SubL;
			}
			SubL->_parent = parent_parent;
		}
		//最后是修改平衡因子
		parent->_bt = 0;
		SubL->_bt = 0;
	}//由此就完成了AVL树右单旋的处理。

void RotateRL(Node* parent)//右左双旋转
	{
		Node* SubR = parent->_right;
		Node* SubrL = SubR->_left;
		int count = SubrL->_bt;//首先取得此时的平衡因子，不然经过后面的旋转平衡因子可能会被改变
		RotateR(SubR);//首先以parent的右节点为轴进行一个右旋转
		RotateL(parent);//再以parent为轴进行一个左旋转。
		//然后我们要根据不同的情况对平衡因子进行判断
		//即要将三种情况分析出来，不然无法完成平衡因子的区分，这里可以使用抽象图中60所在的那个位置的平衡因子能够帮助我们区分这三种情况
		if (count == 0)
		{
			//代表的就是60自己插入的情况
			parent->_bt = SubR->_bt = SubrL->_bt = 0;
		}
		else if (count == 1)// 代表的是在抽象图中的c位置后面插入的情况
		{
			SubR->_bt = SubrL->_bt = 0;
			parent->_bt = -1;
		}
		else if (count == -1)//代表的是在抽象图的b位置后面插入节点的情况
		{
			SubR->_bt = 1;
			SubrL->_bt = parent->_bt = 0;
		}
		else
		{
			assert(false);//出现了错误的情况，不需要在进行平衡了
		}
	}//由此就完成了

void RotateLR(Node* parent)//左右双旋
	{
		Node* subL = parent->_left;
		Node* sublR = subL->_right;
		int count = sublR->_bt;//依旧是以这个情况为准来进行平衡因子的判断
		RotateL(subL);//首先以subl为轴进行一个左旋转
		RotateR(parent);//再以parent为轴进行一个右旋转
		if (count == 0)
		{
			parent->_bt = subL->_bt = sublR->_bt = 0;
		}
		else if (count == 1)//再抽象图的c位置后面插入
		{
			parent->_bt = sublR->_bt = 0;
			subL->_bt=-1;
		}
		else if (count == -1)
		{
			parent->_bt = 1;
			subL->_bt = sublR->_bt = 0;
		}
		else
		{
			assert(false);
		}
	}

bool isblance()
{
		return _isblance(_root);
}
 bool _isblance(Node* root)
{
		if (root == nullptr)
		{
			return true;
		}
		int lefthigh = Hight(root->_left);
		int righthigh = Hight(root->_right);
		if (righthigh - lefthigh != root->_bt)
		{
			cout << root->_kv.first << "当前节点平衡因子异常" << endl;
			return false;
		}
		return abs(righthigh - lefthigh) < 2&&_isblance(root->_left)&&_isblance(root->_right);
}