✍作者：阿润菜菜
📖专栏：C++

AVL树的定义

一棵AVL树是其每个结点的平衡因子绝对值最多相差1的二叉查找树。
平衡因子？这是什么东西，别急，继续往下看。

先给出对应平衡因子的计算，我们这里是根节点的右子树高度减去左子树高度。同时平衡因子的绝对值越大，说明树越不平衡。当平衡因子的绝对值大于1时，就需要进行旋转操作来恢复平衡。

当然更好一点的定义是每个结点的左子树和右子树的高度差。如果用右子树的高度减去左子树的高度来计算平衡因子，那么需要注意平衡因子的符号和旋转方向会相反。这是因为，如果你按照定义来计算平衡因子，那么当平衡因子为正时，说明左子树比右子树高，此时需要进行右旋或左右双旋；当平衡因子为负时，说明右子树比左子树高，此时需要进行左旋或右左双旋。但是如果你用右子树的高度减去左子树的高度来计算平衡因子，那么当平衡因子为正时，说明右子树比左子树高，此时需要进行左旋或右左双旋；当平衡因子为负时，说明左子树比右子树高，此时需要进行右旋或左右双旋。也就是说，平衡因子的符号和旋转方向会相反。

根据定义这颗二叉排序树中有结点的平衡因子的绝对值超过1，就不是一颗AVL树。

例如上图：在插入90结点之前是一颗标准的AVL树，在插入90结点之后就不是了，我们查找一下最小不平衡二叉排序树，从距离90结点最近的结点开始，80结点平衡因子为1,70结点平衡因子为2，到这里就找到了，所以以50为根结点的子树就是最小不平衡二叉排序树。
明白了以上概念后我们就需要再了解一下左旋与右旋的概念了。AVL树的精华部分就是通过旋转来保持一颗二叉平衡搜索树👇👇👇

AVL树的旋转机制

首先初步认识一下AVL树的四种旋转：
AVL的四种旋转是指在插入或删除节点后，为了保持AVL树的平衡性，需要对树进行调整的操作。
AVL旋转的名称一般是根据新节点插入的位置和最先失衡的节点的位置来命名的。

这么说清楚些：

• 左单旋（RR）：当新节点插入到较高右子树的右侧时，需要对最先失去平衡的节点进行一次左旋，使其右子树成为新的根节点，原根节点成为其左子树。
• 右单旋（LL）：当新节点插入到较高左子树的左侧时，需要对最先失去平衡的节点进行一次右旋，使其左子树成为新的根节点，原根节点成为其右子树。
• 左右双旋（LR）：当新节点插入到较高左子树的右侧时，需要先对左子树进行一次左旋，再对最先失去平衡的节点进行一次右旋，使其左子树的右子树成为新的根节点。
• 右左双旋（RL）：当新节点插入到较高右子树的左侧时，需要先对右子树进行一次右旋，再对最先失去平衡的节点进行一次左旋，使其右子树的左子树成为新的根节点。

然后：
旋转的原则：保持此棵树继续是二叉搜索树
旋转的目的：保持左右均衡，降低整棵树的高度

1.左旋操作 — 新节点插入较高右子树的右侧—右右：左单旋

1. 在较高右子树右侧插入节点后，节点30的平衡因子变为2，这时我们将30节点进行左旋，这样AV了树就重新达到平衡了

下面展示代码基本上都加上了注释，对比上面左旋流程仔细分析一下，这里需要注意一下，旋转完后结点的父节点都需要重置。

代码示例：左旋操作

void RotateL(Node* parent) // 左旋操作
{
	Node* subR = parent->_right; // subR 是 parent 的右子树根节点
	Node* subRL = subR->_left; // subRL 是 subR 的左子树根节点

	parent->_right = subRL; // 将 subRL 作为 parent 的右子树
	if (subRL)
		subRL->_parent = parent; // 如果 subRL 存在，更新其父节点为 parent

	Node* ppnode = parent->_parent; // ppnode 是 parent 的父节点

	subR->_left = parent; // 将 parent 作为 subR 的左子树
	parent->_parent = subR; // 更新 parent 的父节点为 subR

	if (ppnode == nullptr) // 如果 ppnode 不存在，说明 parent 是根节点
	{
		_root = subR; // 更新根节点为 subR
		_root->_parent = nullptr; // 根节点的父节点为空
	}
	else // 如果 ppnode 存在
	{
		if (ppnode->_left == parent) // 如果 parent 是 ppnode 的左子树
		{
			ppnode->_left = subR; // 将 subR 作为 ppnode 的左子树
		}
		else // 如果 parent 是 ppnode 的右子树
		{
			ppnode->_right = subR; // 将 subR 作为 ppnode 的右子树
		}

		subR->_parent = ppnode; // 更新 subR 的父节点为 ppnode
	}

	parent->_bf = subR->_bf = 0; // 更新 parent 和 subR 的平衡因子为 0
}

2.右旋操作 — 新节点插入较高左子树的左侧——左左：右单旋

1. 新节点插入较高左子树的左侧时，节点60的平衡因子变为2，这里我们将节点60进行右旋，就变成右图的一颗AVL树了

void RotateR(Node* parent) // 右旋操作，和左旋操作对称，只需将左右互换即可
{
	Node* subL = parent->_left; // subL 是 parent 的左子树根节点
	Node* subLR = subL->_right; // subLR 是 subL 的右子树根节点

	parent->_left = subLR; // 将 subLR 作为 parent 的左子树
	if (subLR)
		subLR->_parent = parent; // 如果 subLR 存在，更新其父节点为 parent

	Node* ppnode = parent->_parent; // ppnode 是 parent 的父节点

	subL->_right = parent; // 将 parent 作为 subL 的右子树
	parent->_parent = subL; // 更新 parent 的父节点为 subL

	if (parent == _root) // 如果 parent 是根节点
	{
		_root = subL; // 更新根节点为 subL
		_root->_parent = nullptr; // 根节点的父节点为空
	}
	else // 如果 ppnode 存在
	{
		if (ppnode->_left == parent) // 如果 parent 是 ppnode 的左子树
		{
			ppnode->_left = subL; // 将 subL 作为 ppnode 的左子树
		}
		else // 如果 parent 是 ppnode 的右子树
		{
			ppnode->_right = subL; // 将 subL 作为 ppnode 的右子树
		}
		
        subL->_parent = ppnode; // 更新subL的父节点为ppnode;
    }

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

3.左右双旋 — 新节点插入较高左子树的右侧——左右：先左单旋再右单旋

上面就是左旋与右旋的操作，这部分搞明白之后理解双旋就容易了。

关于双旋的代码： 旋转的代码其实并不需要我们怎么写，我们直接复用左右单旋的代码即可，但在传参时要注意轴点的位置变化，拿右左双旋来举例，轴点先为subR后为parent。
请先看双旋操作中平衡因子的调节

void RotateLR(Node* parent)//LR型，先对parent的左子树进行左旋，再对parent进行右旋;
{
    Node*subL=parent->left;//subL是parent的左子树根节点;
    Node*subLR=subL->right;//subLR是subL的右子树根节点;
    int bf=subLR->bf;//记录subLR的平衡因子;

    RotateL(parent->left);//对parent的左子树进行左旋;
    RotateR(parent);//对parent进行右旋;

    if(bf==1)//如果subLR的平衡因子为1;
    {
        parent->bf=0;//更新parent的平衡因子为0;
        subLR->bf=0;//更新subLR的平衡因子为0;
        subL->bf=-1;//更新subL的平衡因子为-1;
    }
    else if(bf==-1)//如果subLR的平衡因子为-1;
    {
        parent->bf=1;//更新parent的平衡因子为1;
        subLR->bf=0;//更新subLR的平衡因子为0;
        subL->bf=0;//更新subL的平衡因子为0;
    }
    else if(bf==0)//如果subLR的平衡因子为0;
    {
        parent->bf=0;//更新parent的平衡因子为0;
        subLR->bf=0;//更新subLR的平衡因子为0;
        subL->bf=0;//更新subL的平衡因子为0;
    }
    else//其他情况不可能发生;
    {
        assert(false);
    }
}

4.右左双旋 — 新节点插入较高右子树的左侧——右左：先右单旋再左单旋

void RotateRL(Node* parent)//RL型，先对parent的右子树进行右旋，再对parent进行左旋;
{
    Node*subR=parent->right;//subR是parent的右子树根节点;
    Node*subRL=subR->left;//subRL是subR的左子树根节点;
    int bf=subRL->bf;//记录subRL的平衡因子;

    RotateR(parent->right);//对parent的右子树进行右旋;
    RotateL(parent);//对parent进行左旋;

    if(bf==0)//如果subRL的平衡因子为0;
    {
        parent->bf=subR->bf=subRL->bf=0;//更新三个结点的平衡因子都为0;
    }
    else if(bf==1)//如果subRL的平衡因子为1;
    {
        parent->bf=-1;//更新parent的平衡因子为-1;
        subR->bf=subRL->bf=0;//更新subR和subRL的平衡因子都为0;
    }
    else if(bf==-1)//如果subRL的平衡因子为-1;
    {
        subR->bf=1;//更新subR的平衡因子为1;
        parent->bf=subRL->bf=0;//更新parent和subRL的平衡因子都为0;
    }
    else//其他情况不可能发生;
    {
        assert(false);
    }
}

5. 双旋操作中平衡因子的调节

关于双旋的代码实现，它主要的难点不是旋转，因为旋转我们直接复用单旋代码就可以处理了，真正的难点是在平衡因子的调节这块儿，他又分了三种情况。

总结：
假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR
   当pSubR的平衡因子为1时，执行左单旋
   当pSubR的平衡因子为-1时，执行右左双旋
2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL
   当pSubL的平衡因子为-1是，执行右单旋
   当pSubL的平衡因子为1时，执行左右双旋
   旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

AVL树的插入实现

先给出AVL树的基本框架：

//AVL树的节点
template<class K, class V>//直接设置成KV模型，不搞K模型了
	class AVLTreeNode
	{
	public:
		AVLTreeNode(const std::pair<K, V>& p) :
			_data(p),
			_left(nullptr),
			_right(nullptr),
			_parent(nullptr),
			_bf(0)
		{}
		std::pair<K, V> _data;//K、V关系封装在一起
		int _bf;//平衡因子
		AVLTreeNode<K, V> *_left;//
		AVLTreeNode<K, V> *_parent;//用于记录当前节点的父节点
		AVLTreeNode<K, V> *_right;
	};
	template<class K, class V=bool>
	class AVLTree
	{
		typedef AVLTreeNode<K, V> Node;//节点
	public:
		AVLTree() :_root(nullptr)
		{}
	private:
	//在private方法这里定义旋转操作的方法
	Node* _root;
	};

步骤如下：

1. 按照二叉搜索树的规则，从根节点开始比较，找到合适的位置插入新节点。
2. 从插入节点向上回溯，更新每个节点的高度和平衡因子。
3. 如果发现某个节点的平衡因子的绝对值大于1，说明该节点失去平衡，需要进行旋转操作。
4. 根据失去平衡的节点和其子节点的平衡因子，判断旋转的类型（LL，RR，LR或RL）。
5. 根据旋转的类型，进行相应的单旋或双旋操作，调整节点的位置和指针。
6. 在旋转后，再次更新相关节点的高度和平衡因子。
7. 返回新的根节点或子树的根节点。

整体参考代码：

bool insert(const std::pair<K, V>& data)
{
	Node* parent = nullptr;
	Node* cur = _root;
	if (_root == nullptr)//空树
	{
		_root = new Node(data);
		return true;
	}
	while (cur)
	{
		parent = cur;
		if (cur->_data.first == data.first)
			return false;
		else if (cur->_data.first > data.first)
			cur = cur->_left;
		else
			cur = cur->_right;
	}
	cur = new Node(data);
	cur->_parent = parent;//记住要维护父指针域
	if (parent->_data.first > cur->_data.first)
		parent->_left = cur;
	else
		parent->_right = cur;
	//插入一个节点过后，必定导致，cur这个节点的祖宗节点的平衡因子改变，我们需要跟新cur的父节点的平衡因子
	while (parent)
	{
	//cur是parent的右孩子,parent右孩子_bf++
		if (cur->_data.first > parent->_data.first)
			parent->_bf++;
		else
			parent->_bf--;
		//检查更新过后的parent的平衡因子，然后做出不同的反应
		if (parent->_bf == 0)
		{
			//更新过后parent的平衡因子为0，那么更新之前parent的平衡因子一定是 ±1 （可列方阵=程验证）;
			//这说明，新插入的节点，是插在parent矮的一颗子树上的，parent这棵树的高度不变，无需在更新祖宗节点的平衡因子;
			//此次插入，非常成功
			break;
		}
		else if (abs(parent->_bf) == 1)
		{
			//更新过后parent的平衡因子是 ±1 那么说明更新之前parent的_bf一定是0
			//这说明在此次插入过后，parent这棵树的高度增加了，必须更新祖宗节点的_bf
			parent = parent->_parent;//parent、cur直接往上更新
		}
		else if (abs(parent->_bf) == 2)
		{
			//更新过后parent的平衡因子是 ±2 ,那么说明更新之前parent的_bf一定是±1；
			//这说明，此时parent这课树已经失衡了，需要旋转parent这课树
			//不平衡又有四种情况，这四种情况，对应不同的旋转方法

			//这里有个小细节，就是要先比较parent->_bf，再比较parent->_left/parent->_right,不能交换比较顺序，不然会出现错误
			if (parent->_bf == 2 && parent->_right->_bf == 1)//（RR型）
			{
				//parent左旋
				RotateL(parent);
			}
			else if (parent->_bf == -2 && parent->_left->_bf == -1)//(LL型)
			{
				//parent右旋
				RotateR(parent);
			}
			else if (parent->_bf == 2 && parent->_right->_bf == -1)//(RL型)
			{
				//先记录一下parent的右节点的左节点的_bf
				Node* SubR = parent->_right;
				Node* SubRL = SubR->_left;//放心这个节点一定存在，可证明
				int bf = SubRL->_bf;
				//1、先parent->_right右旋
				RotateR(parent->_right);
				//2、再parent左旋
				RotateL(parent);
				//这里我们需要重新更新一下平衡因子，因为单单的左旋、右旋只会将平衡因子置0，这是不正确的，需要我们手动调节
				if (bf == -1)
				{
					SubRL->_bf = 0;
					parent->_bf = 0;
					SubR->_bf = 1;
				}
				else if (bf == 1)
				{
					SubRL->_bf = 0;
					SubR->_bf = 0;
					parent->_bf = -1;
				}
				else if (bf == 0)
				{
					SubRL ->_bf= 0;
					SubR ->_bf= 0;
					parent->_bf = 0;
				}
				else
				{
					assert(false);
				}
			}
			else if (parent->_bf == -2 && parent->_left->_bf == 1)//(LR型)
			{
				Node* SubL = parent->_left;
				Node* SubLR = SubL->_right;//放心这个节点一定存在，可证明
				int bf = SubLR->_bf;
				//1、先parent->_left左旋
				RotateL(parent->_left);
				//2、再parent右旋
				RotateR(parent);
				//平衡因子调节
				if (bf == -1)
				{
					SubLR->_bf = 0;
					SubL->_bf = 0;
					parent->_bf = 1;
				}
				else if (bf == 1)
				{
					SubLR->_bf = 0;
					SubL->_bf = -1;
					parent->_bf = 0;
				}
				else if (bf == 0)
				{
					SubLR->_bf = 0;
					SubL->_bf = 0;
					parent->_bf = 0;
				}
				else
				{
					assert(false);
				}
			}
			else
			{
			//不用说了，插入之前的AVL树就已经出问题了
				assert(false);
			}
			//无论哪种旋转，旋转完毕过后，头结点平衡因子都为0了，
			//这课树已经平衡了，不需要在向上调整了
			break;
		}
		else
		{
//如果更新完过后parent->_bf等于1、-1、0、-2、2之外的数，不用说了，插入之前的AVL树就已经出问题了
     	assert(false);
		}
	}
	return true;
}
void RotateR(Node* parent)
{
	Node* SubL = parent->_left;
	Node* SubLR = SubL->_right;
	Node* ppNode = parent->_parent;

	parent->_left = SubLR;
	if (SubLR)//SubLR节点存在
		SubLR->_parent = parent;

	SubL->_right = parent;
	parent->_parent = SubL;
	if (ppNode == nullptr)//parent是根节点
	{
		SubL->_parent = nullptr;
		_root = SubL;
	}
	else
	{
		SubL->_parent = ppNode;
		if (ppNode->_data.first > SubL->_data.first)
			ppNode->_left = SubL;
		else
			ppNode->_right = SubL;
	}
	SubL->_bf = 0;
	parent->_bf = 0;
}
void RotateL(Node* parent)
{
	Node* SubR = parent->_right;//这个节点一定存在，可以证明
	Node* SubRL = parent->_right->_left;//这个节点就不一定存在了
	Node* ppNode = parent->_parent;//提前记录一下parent的父亲
	//开始链接SubRL节点
	parent->_right = SubRL;
	if (SubRL)//只有当这个节点存在时，才需要维护器=其父亲节点
		SubRL->_parent = parent;
	//开始链接parent节点
	SubR->_left = parent;
	parent->_parent = SubR;

	//开始链接SubR节点
	if (ppNode == nullptr)//如果parent就是根，那么需要更新根节点
	{
		SubR->_parent = nullptr;
		_root = SubR;
	}
	else//parent不是根节点
	{
		SubR->_parent = ppNode;
		if (ppNode->_data.first > SubR->_data.first)
			ppNode->_left = SubR;
		else
			ppNode->_right = SubR;
	}
	//更新平衡因子
	SubR->_bf = 0;
	parent->_bf = 0;
}

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$lo{g}_2(N)$。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。