解读AVL树：平衡二叉搜索树的奥秘

✨✨小新课堂开课了，欢迎欢迎~✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：C++：由浅入深篇

小新的主页：编程版小新-CSDN博客

前言：

前面我们已经介绍了二叉搜索树，今天我们要学习的AVL是一颗高度平衡的二叉搜索树，如何让一棵树保持平衡呢？欲知后事，请看下文。

 一.AVL树的概念

AVL树是最先发明的平衡二叉搜索树，AVL是一颗空树，或者具备下列性质的二叉搜索树：

1.它的左右子树都是AVL树

2.它的左右子树的高度差的绝对值不超过1

AVL树是一颗高度平衡的二叉搜索树，通过控制高度差去控制平衡。

二.平衡因子的概念

 AVL树实现这里我们引入一个平衡因子(balance factor)的概念，每个结点都有一个平衡因子，平衡因子是指一个节点的右子树高度与左子树高度之差，也就是说任何结点的平衡因子等于0/1/-1(左右子树的高度差的绝对值不超过1)

AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡，就像一个风向标一样。

思考一下为什么AVL树是高度平衡二叉搜索树，要求高度差不超过1，而不是高度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，而是有些情况是做不到高度差是0的。比如一棵树是2个结点，4个结点等情况下，无法做到高度差是0。

平衡因子以右子高度减去左子树高度为例。

AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN ，那么增删查改的效率也可以控制在logN ，相比二叉搜索树有了本质的提升。

三.AVL树的实现

3.1AVL树的结构

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针，后续更新平衡因子可以看到
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;//左子树
	AVLTreeNode<K, V>* _right;//右子树
	AVLTreeNode<K, V>* _parent;//父亲节点
	int _bf; // 平衡因子


	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:
	//...
private:
	Node * _root = nullptr;
};

3.2AVL树的插入

3.2.1 AVL树插入一个值的大概过程

1. 插入一个值按二叉搜索树规则进行插入。

2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子。

更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。

3. 更新平衡因子过程中没有出现问题，则插入结束。

4. 更新平衡因子过程中出现不平衡，对不平衡子树进行旋转。

旋转后将子树调平衡的同时降低了子树的高度，不会再影响上一层，所以插入结束。

总结：

3.2.2平衡因子的更新

更新原则：

• 平衡因子 = 右子树高度-左子树高度

• 只有子树高度变化才会影响当前结点平衡因子

• 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子--

• parent所在子树的高度是否变化决定了是否会继续往上更新

示例一：

示例二：

更新停止条件：

1• 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树一边高一边低，新增的结点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。

2• 更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说明更新前parent子树两边一样高，新增的插入结点后，parent所在的子树一边高一边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。

3• 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树一边高一边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理。

旋转的目标有两个：

1、把parent子树旋转平衡。

2、降低parent子树的高度，恢复到插入结点以前的高度。(插入之前是符合AVL树的要求的)

所以旋转后也不需要继续往上更新，插入结束。

3.2.3插入节点及其更新平衡因子

把上面的更新过程理解清楚了，代码的实现就简单了。

//插入
bool Insert(const pair<K, V>& kv)
{
	//根为空要单独考虑
	if (_root == nullptr)
	{
		_root = new Node(kv);

		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			//往右走
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			//往左走
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	//插入
	cur = new Node(kv);

	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	//链接父亲
	cur->_parent = parent;

	//控制平衡
	//更新平衡因子
	while (parent)
	{
		//新增节点在parent的左子树
		if (cur == parent->_left)
		{
			parent->_bf--;//平衡因子--
		}
		else
		{
			//新增节点在parent的右子树
			parent->_bf++;//平衡因子++
		}

		//检查是否需要向上更新祖先的平衡因子
		if (parent->_bf == 0)
		{
			//更新结束
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			//新增的插入结点后,parent所在的子树符合平衡要求
			//但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//新增的插入结点在高的那边，parent所在的子树高的那边更高了
			// 破坏了平衡，parent所在的子树不符合平衡要求
			// 需要旋转处理
			

			break;//旋转之后，就更新结束了
		}
		else
		{
			assert(false);
		}

	}

	return true;
}

3.3旋转

3.3.1 旋转的原则

旋转原则：

1. 保持搜索树的规则

2. 让旋转的树从不平衡变平衡，其次降低旋转树的高度

旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什么值都可以，只要大小关系符合搜索树的规则即可。

3.3.2右单旋

本图1展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根(在实现代码时，这里就是一个需要考虑的小细节）。

这里图一a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/图5进行了详细描述。

其中，parent是失衡节点，其左子树被命名为subL，其左子树的右子树被命名为subLR。

旋转规则如下：

1.将subLR链接到parent的左边。

2.将parent链接到subL的右边

3.将parent与sunL的平衡因子置为0

示例一：

示例二：

示例三：

示例四：

 如果去讨论插入前a/b/c是高度为4的AVL子树的话，情况更是多的数不胜数，不过我们不必纠结这个问题，因为我们已经给出了如图一所示的旋转模版，所有的情况都包含在内，我们只要掌握右旋的旋转规则就能解决问题。

实践：右单旋代码实现

void RotateR(Node* parent)
{
	 //旋转
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	parent->_left = subLR;

	//更改_parent的指向
	if (subLR)//可能高度为0，如情况1
	{
		subLR->_parent = parent;
	}

	//提前记录parent的父亲节点,因为parent也可能是一整棵树中局部子树的根
	Node* Pparent = parent->_parent;

	subL->_right = parent;
	parent->_parent = subL;


	//parent之前可能是整棵树的根，也可能是一整棵树中局部的子树的根
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		//如果parent之前只是一颗树中局部的子树的根
		//我们就需要提前记录parent的_parent
		if (Pparent->_left == parent)
		{
			Pparent->_left = subL;
		}
		else
		{
			Pparent->_right = subL;
		}

		subL->_parent = Pparent;

		//更新平衡因子
		subL->_bf = 0;
		parent->_bf = 0;
	}
}

3.3.3左单旋

本图6展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a/b/c是高度为h的子树，是一种概括抽象表示，他代表了所有左单旋的场景，实际左单旋形态有很多种，具体跟上面右旋类似。

 其中，parent是失衡节点，其右子树被命名为subR，其右子树的左子树被命名为subRL。

旋转规则如下：

1.将subRL链接到parent的右边

2.将parent链接到subR的左边

3.将parent与subR的平衡因子置为0

我们不具体的向右旋那样，具体讨论了，下面我们去看几个例子，熟悉一下左旋的过程。

可以发现旋转之后，即保持了搜索树的规则又让旋转的树从不平衡变平衡，其次降低旋转树的高度。 

 实践：左单旋代码实现

	void RotateL(Node* parent)
	{
		//旋转
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;

		//更新_parent的指向
		if (subRL)//可能高度为0
		{
			subRL->_parent = parent;
		}

		//	//提前记录parent的父亲节点,因为parent之前也可能是一整棵树中局部的子树的根
		Node* Pparent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		//parent之前可能是整棵树的根，也可能是一整棵树中局部的子树的根
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			//如果parent之前只是一颗树中局部的子树的根
		   //我们就需要提前记录parent的_parent
			if (Pparent->_left == parent)
			{
				Pparent->_left = subR;
			}
			else
			{
				Pparent->_right = subR;
			}

			subR->_parent = Pparent;

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

		}
	}

3.3.4左右双旋

通过图7和图8可以看到，左边高时，如果插入位置不是在a子树，而是插入在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边高，左单旋解决的纯粹的右边高，但是插入在b子树中，10为跟的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，需要用两次旋转才能解决，以5为旋转点进行一个左单旋，以10为旋转点进行⼀个右单旋，这棵树这棵树就平衡了。

 由图可以更加直观的看到，像这种不是纯粹的一边高的情况，只靠左旋/右旋是不能解决问题的。不仅树不平衡，我们在更新平衡因子的时候，也有错误。

那我们该如何是好呢？

对于这种情况我们需要先左单旋，再右单旋的方式，其中，失衡节点为parent，其左子树节点为subL,而有左子树的右子树为subLR。

其调整规则如下：

1.先对subL进行左旋

2.再对parent 进行右旋

3.调整平衡因子

下面我们具体看个示例。

但是新增节点的位置不同，平衡因子的更新也会有差异，这里我们分为三种情况。

1.当subLR = -1时，如上图所示，调整后subL = 0;subLR = 0;parent = 1。

2.当subLR= 0时，如下图所示，调整后subL = 0;subLR = 0;parent = 0。

3.当subLR = 1时，如下图所示，调整后subL = -1;subLR = 0;parent = 0。

实践：左右双旋代码实现

void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	int bf = subLR->_bf;

	RotateL(parent->_left);
	RotateR(parent);

	if (bf == 0)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subL->_bf = 0;
		subLR->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)
	{
		subL->_bf = -1;
		subLR->_bf = 0;
		parent->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

 3.3.5右左双旋

和左右双旋的情况类似，当出现不是纯粹的某一边高时，仅仅使用一次单旋是解决不了问题的。例如对12而言是左边高，对8而言是右边高。我们就要先对12进行右旋，再对8进行左旋才能解决问题。

对于这种情况我们需要先右单旋，再左单旋的方式，设失衡节点为parent，其右子树节点为subR，而有右子树的左子树为subRL。

其调整规则如下：

先对subR进行右旋

再对parent进行左旋

调整平衡因子

我们针对上面的例子，具体实践看看。

但是新增节点的位置不同，平衡因子的更新也会有差异，这里我们分为三种情况。

1.当subRL = -1时，如上图所示，调整后subR = 1;subRL = 0;parent = 0。

2.当subRL = 0时，如下图所示，调整后subR = 0;subRL = 0;parent = 0。

3.当subRL = 1时，如下图所示，调整后subR = 0;subRL = 0;parent = -1。

实践：右左双旋代码实现

void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	int bf = subRL->_bf;

	RotateR(parent->_right);
	RotateL(parent);

	if (bf == 0)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_bf = 0;
		parent->_bf = 0;
	}
	else if (bf == 1)
	{
		subR->_bf = 0;
		subRL->_bf = 0;
		parent->_bf = -1;
	}
	else
	{
		assert(false);
	}
}

3.3.6插入完整代码

//插入
bool Insert(const pair<K, V>& kv)
{
	//根为空要单独考虑
	if (_root == nullptr)
	{
		_root = new Node(kv);

		return true;
	}

	Node* parent = nullptr;
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first < kv.first)
		{
			//往右走
			parent = cur;
			cur = cur->_right;
		}
		else if (cur->_kv.first > kv.first)
		{
			//往左走
			parent = cur;
			cur = cur->_left;
		}
		else
		{
			return false;
		}
	}

	//插入
	cur = new Node(kv);

	if (parent->_kv.first < kv.first)
	{
		parent->_right = cur;
	}
	else
	{
		parent->_left = cur;
	}
	//链接父亲
	cur->_parent = parent;

	//控制平衡
	//更新平衡因子
	while (parent)
	{
		//新增节点在parent的左子树
		if (cur == parent->_left)
		{
			parent->_bf--;//平衡因子--
		}
		else
		{
			//新增节点在parent的右子树
			parent->_bf++;//平衡因子++
		}

		//检查是否需要向上更新祖先的平衡因子
		if (parent->_bf == 0)
		{
			//更新结束
			break;
		}
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			//新增的插入结点后,parent所在的子树符合平衡要求
			//但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新
			cur = parent;
			parent = parent->_parent;
		}
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			//新增的插入结点在高的那边，parent所在的子树高的那边更高了
			// 破坏了平衡，parent所在的子树不符合平衡要求
			// 需要旋转处理
			if (parent->_bf == -2 && cur->_bf ==-1)
			{
				RotateR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == 1)
			{
				RotateL(parent);
			}
			else if (parent->_bf == -2 && cur->_bf == 1)
			{
				RotateLR(parent);
			}
			else if (parent->_bf == 2 && cur->_bf == -1)
			{
				RotateRL(parent);
			}
			else
			{
				assert(false);
			}


			break;//旋转之后，就更新结束了
		}
		else
		{
			assert(false);
		}

	}

	return true;
}

3.4AVL树的查找

和二叉搜索树的查找逻辑一样，搜索效率为 O(logN)。

Node* Find(const k& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (cur->_kv.first > key)
		{
			cur = cur->_left;
		}
		else if (cur->_kv.first < key)
		{
			cur=cur->_right
		}
		else
		{
			return cur;
		}
	}

	return nullptr;
}

3.5AVL树平衡检测

我们实现的AVL树是否合格，我们通过检查左右子树高度差的的程序进行反向验证，同时检查一下结点的平衡因子更新是否出现了问题。

	int _Hight(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int LeftHight = _Hight(root->_left);
		int RightHight = _Hight(root->_right);

		return LeftHight > RightHight ? LeftHight + 1 : RightHight+1;
	}

	bool _IsBalanceTree(Node* root)
	{
		//空树
		if (root == nullptr)
		{
			return true;
		}

		int LeftHight = _Hight(root->_left);
		int RightHight = _Hight(root->_right);
		int diff = RightHight - LeftHight;

		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}

		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		// root的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);

	}

四.源码

#pragma once
#include<iostream>
#include<assert.h>
#include<utility>

using namespace std;

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针，后续更新平衡因子可以看到
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;//左子树
	AVLTreeNode<K, V>* _right;//右子树
	AVLTreeNode<K, V>* _parent;//父亲节点
	int _bf; // 平衡因子


	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;

public:

	AVLTree()
	{}

	AVLTree(const AVLTree& t)
	{
		_root = copy(t._root);
	}

	Node* copy(Node* root)
	{
		if (root == nullptr)
			return nullptr;
	
		Node* newnode = new Node(root->_kv);
		// 递归地拷贝原始根节点的左子树，并将结果赋给新节点的左指针
		newnode->_left = copy(root->_left);
		// 递归地拷贝原始根节点的右子树，并将结果赋给新节点的右指针
		newnode->_right = copy(root->_right);
		// 新节点的父节点默认为空
		newnode->_parent = nullptr;
		// 如果新节点的左子节点存在，设置其父节点为新节点
		if (newnode->_left)
		{
			newnode->_left->_parent = newnode;
		}
		// 如果新节点的右子节点存在，设置其父节点为新节点
		if (newnode->_right)
		{
			newnode->_right->_parent = newnode;
		}
		// 返回新树的根节点指针
		return newnode;
	}

	AVLTree<K, V>& operator=(const AVLTree <K, V> t)
	{
		
		this->swap(_root, t._root);
		return *this;
	}

	~AVLTree()
	{
		Destroy(_root);
	}

	void Destroy(Node*& root)
	{
		if (root == nullptr)
		{
			return;
		}

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


	//插入
	bool Insert(const pair<K, V>& kv)
	{
		//根为空要单独考虑
		if (_root == nullptr)
		{
			_root = new Node(kv);

			return true;
		}

		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				//往右走
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				//往左走
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		//插入
		cur = new Node(kv);

		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		//链接父亲
		cur->_parent = parent;

		//控制平衡
		//更新平衡因子
		while (parent)
		{
			//新增节点在parent的左子树
			if (cur == parent->_left)
			{
				parent->_bf--;//平衡因子--
			}
			else
			{
				//新增节点在parent的右子树
				parent->_bf++;//平衡因子++
			}

			//检查是否需要向上更新祖先的平衡因子
			if (parent->_bf == 0)
			{
				//更新结束
				break;
			}
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//新增的插入结点后,parent所在的子树符合平衡要求
				//但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新
				cur = parent;
				parent = parent->_parent;
			}
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//新增的插入结点在高的那边，parent所在的子树高的那边更高了
				// 破坏了平衡，parent所在的子树不符合平衡要求
				// 需要旋转处理
				if (parent->_bf == -2 && cur->_bf ==-1)
				{
					RotateR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}
				else
				{
					assert(false);
				}


				break;//旋转之后，就更新结束了
			}
			else
			{
				assert(false);
			}

		}

		return true;
	}


	void RotateR(Node* parent)
	{
		 //旋转
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;

		//更改_parent的指向
		if (subLR)//可能高度为0，如情况1
		{
			subLR->_parent = parent;
		}

		//提前记录parent的父亲节点,因为parent也可能是一整棵树中局部子树的根
		Node* Pparent = parent->_parent;
	
		subL->_right = parent;
		parent->_parent = subL;


		//parent之前可能是整棵树的根，也可能是一整棵树中局部的子树的根
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			//如果parent之前只是一颗树中局部的子树的根
			//我们就需要提前记录parent的_parent
			if (Pparent->_left == parent)
			{
				Pparent->_left = subL;
			}
			else
			{
				Pparent->_right = subL;
			}

			subL->_parent = Pparent;

			//更新平衡因子
			subL->_bf = 0;
			parent->_bf = 0;
		}
	}

	void RotateL(Node* parent)
	{
		//旋转
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;

		//更新_parent的指向
		if (subRL)//可能高度为0
		{
			subRL->_parent = parent;
		}

		//	//提前记录parent的父亲节点,因为parent之前也可能是一整棵树中局部的子树的根
		Node* Pparent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;

		//parent之前可能是整棵树的根，也可能是一整棵树中局部的子树的根
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			//如果parent之前只是一颗树中局部的子树的根
		   //我们就需要提前记录parent的_parent
			if (Pparent->_left == parent)
			{
				Pparent->_left = subR;
			}
			else
			{
				Pparent->_right = subR;
			}

			subR->_parent = Pparent;

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

		}
	}

	


	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		int bf = subLR->_bf;

		RotateL(parent->_left);
		RotateR(parent);

		if (bf == 0)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subL->_bf = 0;
			subLR->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)
		{
			subL->_bf = -1;
			subLR->_bf = 0;
			parent->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}

	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		int bf = subRL->_bf;

		RotateR(parent->_right);
		RotateL(parent);

		if (bf == 0)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == -1)
		{
			subR->_bf = 1;
			subRL->_bf = 0;
			parent->_bf = 0;
		}
		else if (bf == 1)
		{
			subR->_bf = 0;
			subRL->_bf = 0;
			parent->_bf = -1;
		}
		else
		{
			assert(false);
		}
	}

	Node* Find(const K & key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > key)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)
			{
				cur = cur->_right;
			}
			else
			{
				return cur;
			}
		}

		return nullptr;
	}

	int Height()
	{
		return _Height(this->_root);
	}

	int Size()
	{
		return _Size(this->_root);
	}
	/* 
	bool isBalanceTree()
	{
		return IsBalanceTree(this->_ root);
	}*/

	void inOrder()
	{
		InOrder(this->_root);

		cout << endl;
	}


private:

	void InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}

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

	int _Height(Node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}

		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);

		return LeftHeight > RightHeight ? LeftHeight + 1 : RightHeight+1;
	}

	bool IsBalanceTree(Node* root)
	{
		//空树
		if (root == nullptr)
		{
			return true;
		}

		int LeftHeight = _Height(root->_left);
		int RightHeight = _Height(root->_right);
		int diff = RightHeight - LeftHeight;

		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "高度差异常" << endl;
			return false;
		}

		if (root->_bf != diff)
		{
			cout << root->_kv.first << "平衡因子异常" << endl;
			return false;
		}

		// root的左和右如果都是AVL树，则该树一定是AVL树
		return IsBalanceTree(root->_left) && IsBalanceTree(root->_right);

	}

	int _Size(Node* root)
	{
		if (root == nullptr)
			return 0;

		return _Size(root->_left) + _Size(root->_right) + 1;
	}

private:
		Node* _root = nullptr;
};

总结：

AVL的旋转难题，我们已经解决了，下面我们就要进入红黑树了，红黑树也是一个平衡二叉搜索树，就让我们一起去看看是怎么回事吧。

感谢各位大佬的观看，创作不易，还请各位大佬点赞支持~