平衡搜索二叉树（AVL树）

1. 待插入结点的key值比当前结点小就插入到该结点的左子树。
2. 待插入结点的key值比当前结点大就插入到该结点的右子树。
3. 待插入结点的key值与当前结点的key值相等就插入失败。

pCur 插入后， pParent 的平衡因子一定需要调整，在插入之前， pParent 的平衡因子分为三种情况：-1 ， 0, 1, 分以下两种情况：

? 1. 如果 pCur 插入到 pParent 的左侧，只需给 pParent 的平衡因子 -1 即可

? 2. 如果 pCur 插入到 pParent 的右侧，只需给 pParent 的平衡因子 +1 即可

此时： pParent 的平衡因子可能有三种情况： 0 ，正负 1 ， 正负 2

? 1. 如果 pParent 的平衡因子为 0 ，说明插入之前 pParent 的平衡因子为正负 1 ，插入后被调整成0 ，此时满足

? ? AVL 树的性质，插入成功

? 2. 如果 pParent 的平衡因子为正负 1 ，说明插入前 pParent 的平衡因子一定为 0 ，插入后被更 新成正负1 ，此 时以 pParent 为根的树的高度增加，需要继续向上更新

? 3. 如果 pParent 的平衡因子为正负 2 ，则 pParent 的平衡因子违反平衡树的性质，需要对其进 行旋转处理

理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：

其父结点是一个左右子树均为空的叶子结点，其平

衡因子是0，新增结点插入后其平衡因子更新为-1/1。
其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。
综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0
?

根据此结论，我们可以将旋转处理分为以下四类：??

1. 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
2. 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
3. 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
4. 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。

//插入函数
bool Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点
	{
		_root = new Node(kv);
		return true;
	}
	//1、按照二叉搜索树的插入方法，找到待插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
		{
			//往该结点的左子树走
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
		{
			//往该结点的右子树走
			parent = cur;
			cur = cur->_right;
		}
		else //待插入结点的key值等于当前结点的key值
		{
			//插入失败（不允许key值冗余）
			return false;
		}
	}

	//2、将待插入结点插入到树中
	cur = new Node(kv); //根据所给值构造一个新结点
	if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
	{
		//插入到parent的左边
		parent->_left = cur;
		cur->_parent = parent;
	}
	else //新结点的key值大于parent的key值
	{
		//插入到parent的右边
		parent->_right = cur;
		cur->_parent = parent;
	}

	//3、更新平衡因子，如果出现不平衡，则需要进行旋转
	while (cur != _root) //最坏一路更新到根结点
	{
		if (cur == parent->_left) //parent的左子树增高
		{
			parent->_bf--; //parent的平衡因子--
		}
		else if (cur == parent->_right) //parent的右子树增高
		{
			parent->_bf++; //parent的平衡因子++
		}
		//判断是否更新结束或需要进行旋转
		if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
		{
			break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
		}
		else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
		{
			//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
		{
			if (parent->_bf == -2)
			{
				if (cur->_bf == -1)
				{
					RotateR(parent); //右单旋
				}
				else //cur->_bf == 1
				{
					RotateLR(parent); //左右双旋
				}
			}
			else //parent->_bf == 2
			{
				if (cur->_bf == -1)
				{
					RotateRL(parent); //右左双旋
				}
				else //cur->_bf == 1
				{
					RotateL(parent); //左单旋
				}
			}
			break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了)
		}
		else
		{
			assert(false); //在插入前树的平衡因子就有问题
		}
	}

	return true; //插入成功
}

四、AVL树的旋转

4.1、右单旋

新节点插入较高左子树的左侧---左左：

1. 让subL的右子树作为parent的左子树。
2. 让parent作为subL的右子树。
3. 让subL作为整个子树的根。
4. 更新平衡因子。

void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
 
	parent->_left = subLR;
	if (subLR)  //右孩子可能为空
		subLR->_parent = parent;
 
	Node* ppnode = parent->_parent; //记录父节点的父节点
 
	subL->_right = parent;
	parent->_parent = subL;
 
	if (ppnode == nullptr) //如果父节点是根节点
	{
		_root = subL;      //改变根节点
		_root->_parent = nullptr;
	}
	else                   //如果父节点不是根节点
	{
		if (ppnode->_left == parent) //如果父节点是左孩子
		{
			ppnode->_left = subL;    
		}
		else                         //如果父节点是右孩子
		{
			ppnode->_right = subL;
		}
		subL->_parent = ppnode;
	}
	parent->_bf = subL->_bf = 0;    //最后更新平衡因子
}

4.2、左单旋

1. 让subR的左子树作为parent的右子树。
2. 让parent作为subR的左子树。
3. 让subR作为整个子树的根。
4. 更新平衡因子。

左单旋后满足二叉搜索树的性质：

1. subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
2. parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* parentParent = parent->_parent;

	//1、建立subR和parent之间的关系
	parent->_parent = subR;
	subR->_left = parent;

	//2、建立parent和subRL之间的关系
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	//3、建立parentParent和subR之间的关系
	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr; //subR的_parent指向需改变
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		}
		else //parent == parentParent->_right
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}

	//4、更新平衡因子
	subR->_bf = parent->_bf = 0;
}

4.3、左右双旋

1. 以subL为旋转点进行左单旋。
2. 以parent为旋转点进行右单旋。
3. 更新平衡因子。

左右双旋后满足二叉搜索树的性质：

左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根

1、subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2、subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
3、经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树

左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：

1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。

//左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1

	//1、以subL为旋转点进行左单旋
	RotateL(subL);

	//2、以parent为旋转点进行右单旋
	RotateR(parent);

	//3、更新平衡因子
	if (bf == 1)
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 0)
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false); //在旋转前树的平衡因子就有问题
	}
}

4.4、右左双旋

//右左双旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	int bf = subRL->_bf;

	//1、以subR为轴进行右单旋
	RotateR(subR);

	//2、以parent为轴进行左单旋
	RotateL(parent);

	//3、更新平衡因子
	if (bf == 1)
	{
		subRL->_bf = 0;
		parent->_bf = -1;
		subR->_bf = 0;
	}
	else if (bf == -1)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 1;
	}
	else if (bf == 0)
	{
		subRL->_bf = 0;
		parent->_bf = 0;
		subR->_bf = 0;
	}
	else
	{
		assert(false); //在旋转前树的平衡因子就有问题
	}
}

//中序遍历
void Inorder()
{
?? ?_Inorder(_root);
}
//中序遍历子函数
void _Inorder(Node* root)
{
?? ?if (root == nullptr)
?? ??? ?return;
?? ?_Inorder(root->_left);
?? ?cout << root->_kv.first << " ";
?? ?_Inorder(root->_right);
}

//判断是否为AVL树
bool IsAVLTree()
{
	int hight = 0; //输出型参数
	return _IsBalanced(_root, hight);
}
//检测二叉树是否平衡
bool _IsBalanced(Node* root, int& hight)
{
	if (root == nullptr) //空树是平衡二叉树
	{
		hight = 0; //空树的高度为0
		return true;
	}
	//先判断左子树
	int leftHight = 0;
	if (_IsBalanced(root->_left, leftHight) == false)
		return false;
	//再判断右子树
	int rightHight = 0;
	if (_IsBalanced(root->_right, rightHight) == false)
		return false;
	//检查该结点的平衡因子
	if (rightHight - leftHight != root->_bf)
	{
		cout << "平衡因子设置异常：" << root->_kv.first << endl;
	}
	//把左右子树的高度中的较大值+1作为当前树的高度返回给上一层
	hight = max(leftHight, rightHight) + 1;
	return abs(rightHight - leftHight) < 2; //平衡二叉树的条件
}