【C++：AVL树】深入理解AVL树的平衡之道：从原理、旋转到完整实现代码

用户11831438

发布于 2025-12-30 13:21:39

2870

一、初识AVL树：如何让二叉搜索树“站”得更稳

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

它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1

AVL树是一棵高度平衡搜索二叉树，通过控制高度差取控制平衡

在AVL树的实现这里我们引用一个平衡因子（balance factor）的概念，每个节点都有一个平衡因子：

任何节点的平衡因子=左子树高度-右子树高度（也就是说任何节点的平衡因子等于0/1/-1）

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

思考一下—— 为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差为0呢？0不是更好的平衡吗？不是不想这样设计，而是有些情况是做不到高度差是0的——比如一棵树是2个结点，4个结点等情况下，高度差最好就是1，无法做到高度差是0——也就是说，不是不想做，而是做不到！

AVL树整体节点数量和分布和完全二叉树类似，高度可以控制在

，那么增删查改的效率也可以控制在

，相较于二叉搜索树有了质的提升！！！

二、AVL树架构解析：实现核心操作

2.1 AVL树的结构

template<class k,class v>
struct ALVTreeNode
{
	pair<k, v> _kv;//存储的是一个key_value的数据
	ALVTreeNode<k, v>* _left;
	ALVTreeNode<k, v>* _right;
	ALVTreeNode<k, v>* _parent;//指向父节点的指针
	int _bf;//平衡因子
	ALVTreeNode(const pair<k, v>& kv)
		:_kv(kv)
		,_left(nullptr)
		,_right(nullptr)
		,_bf(0)
	{}
};
template<class k,class v>
class ALVTree
{
	typedef ALVTreeNode<k, v> node;
private:
	node* _root = nullptr;//根节点
};

2.2 插入与平衡维护

AVL树的插入和搜索二叉树的插入逻辑一模一样，在插入的过程中我们需要通过平衡因子来判断这棵AVL树是否平衡，如果不平衡，我们就要对它进行旋转操作。

ok，我们来看一下这个插入的过程——

插入一个值按二叉搜索树规则进行插入
更新平衡因子
更新平衡因子过程中没有出现问题，则插入结束
更新平衡因子过程中出现不平衡，则对不平衡子树旋转

插入数据代码：

template<class k,class v>
class ALVTree
{
	typedef ALVTreeNode<k, v> node;
public:
	bool insert(const pair<k, v>& kv)
	{
		if (_root == nullptr)
		{
			_root = new node(kv);
		}
		node* cur = _root;
		node* parent = nullptr;
		while (cur != nullptr)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
}

说到更新平衡因子，这里有个问题：新加入节点的平衡因子为多少？

ok，新插入节点没有左右子树，所以新插入节点的平衡因子为0

新插入的节点只会影响他的祖先节点的高度，也就是说可能会影响部分祖先节点的平衡因子

引入平衡因子可以判断这棵树有没有平衡，平衡则插入结束，不平衡则旋转！！！

2.2.3 平衡因子更新

更新原则：

平衡因子=右子树高度-左子树高度
只有子树高度变化才会影响当前节点的平衡因子（子树高度不变，不会影响平衡因子）
插入节点，会增加高度，若新增节点在其parent（父节点）的右子树中，parent的平衡因子++；若新增节点在其parent（父节点）的左子树中，parent平衡因子--
插入节点后，parent（新增节点的父节点）所在的子树高度是否变化决定了是否会继续往上更新

插入节点后，更新了parent（新增节点的父节点）的平衡因子

那还要不要继续往上更新呢？——

看parent（新增节点的父节点）所在的子树高度是否变化，若高度变了，会影响上一层；高度不变，不会影响上一层

ok，这里我们来详细探讨一下： 什么时候需要继续向上更新平衡因子？

（1）

有了_parent的指针（指向父节点的指针），方便更新平衡因子！！！

（2）

若更新后parent 的平衡因子为2或者-2，变化过程为1->2或-1->-2，说明更新前parent所在的子树一边高一边低，但是满足平衡要求；新插入的节点插入在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在子树不符合平衡要求，需要旋转处理！！！

旋转的目的：

把parent所在子树旋转平衡
降低parent所在子树的高度，恢复到插入节点之前的高度，旋转后插入结束
（3）

更新后parent的平衡因子等于0，更新过程为1->0或-1->0，说明更新前parent的子树一边高一边低，新增节点插入在低的那边，插入后parent所在的子树高度不变，不会影响parent的父节点

（4）

总结一下：

情况一：继续向上更新

条件： parent 平衡因子 从 0 → 1 或 0 → -1
含义： 子树高度增加，会影响上层祖先
操作： parent = parent->_parent，继续循环
可能结果： 继续向上，直到情况二、三或到达根节点

情况二：立即停止更新

条件： parent 平衡因子 从 1 → 0 或 -1 → 0
含义： 子树从不平衡变平衡，但高度未变
操作： 立即结束整个更新过程
位置： 可能在任意中间节点停止

情况三：旋转后停止

条件： parent 平衡因子 从 1 → 2 或 -1 → -2
含义： 严重不平衡，需要旋转修复
操作： 旋转后立即结束更新
位置： 在第一个不平衡节点处停止

终止条件总结

更新过程在以下时刻必然停止：

✅ 情况二：遇到 平衡因子 → 0 的节点
✅ 情况三：遇到 平衡因子 → ±2 的节点
✅ 到达根节点：最坏情况，更新到根节点后停止

代码演示：

//调整平衡因子
//最坏更新到根节点
while (parent)
{
	//插入节点都会改变其父节点的平衡因子
	if (parent->_left == cur)
	{
		parent->_bf--;
	}
	else
	{
		parent->_bf++;
	}
	//插入节点的父节点的平衡因子调整完之后，要不要继续向上调整吗？
	//分为3种情况：
	//（1）插入之前一边高一边低，现在左右两边相等，不会再影响上一层，就over
	if (parent->_bf == 0)
	{
		break;//原先是1/-1
	}
	//（2）parent所在的子树高度变了，1或者-1，是由0->1或0->-1
	//插入之前两边一样高，现在一边高一边低，子树的整体高度变了，需要继续往上更新
	else if (parent->_bf == 1 || parent->_bf == -1)
	{
		cur = parent;
		parent = parent->_parent;
	}
	//（3）parent所在子树已经不平衡，需要旋转处理
	else if (parent->_bf == 2 || parent->_bf == -2)
	{
		//旋转
		break;
	}
	else
	{
		assert(false);
	}
}

2.3 平衡的艺术：详解AVL树的旋转

2.3.1 右单旋 (Left Left Case - LL)

右单旋的使用场景就是左子树更高导致的不平衡。

如图所示，假设10为根的树，有a / b / c抽象为三棵高度为h的子树(h >= 0)，a / b / c均符合AVL树的要求。10可能是整棵树的根，也可能是一个整棵树中局部的子树的根。这里a / b / c是高度为h的子树，是一种概括抽象表示，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体后面会有图形进行了详细描述。

在a子树中插入一个新结点，导致a子树的高度从h变成h + 1，不断向上更新平衡因子，导致10的平衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。

旋转核心步骤，因为5 < b子树的值 < 10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h + 2，符合旋转原则。插入之后，10所在的子树是整棵树的局部子树，旋转后不会再影响上一层，插入结束了。

总结一下：

触发条件：

节点 parent 的平衡因子为 -2（左子树更高）
其左孩子 subL 的平衡因子为 -1（新节点插入在 subL 的左子树）

场景模拟： 插入节点后，parent 的平衡因子从 -1 变为 -2。不平衡的“重心”在 parent 的左孩子的左子树上，是一条直线，所以用一次右旋即可解决。

操作步骤：

让 subL 的右子树 subLR 成为 parent 的左子树。
让 parent 成为 subL 的右子树。
将 subL 提升为整个子树新的根节点，并更新其父指针。
更新 parent 和 subL 的父指针。
调整平衡因子

ok，现在我们来看一下为什么这里要有a / b / c抽象为三棵高度为h的子树(h >= 0)?

其实这是因为如果没有a / b / c抽象为三棵高度为h的子树(h >= 0)，我们无法穷举出所有情况！！

情况1：插入前a / b / c高度h==0（a/b/c所在子树为空）

情况2：插入前a / b / c高度h==1（a/b/c所在子树只有一个节点）

上面这种情况新增节点有两个插入的位置——a的左边和右边

情况3：插入前a / b / c高度h==2

上图中的组合场景有36种

情况4：插入前a / b / c高度h==3

上图中的组合场景有5400种

也就是说，我们使用a / b / c抽象为三棵高度为h的子树(h >= 0)就可以代表所有中情况！！！

代码实现：

//（3）parent所在子树已经不平衡，需要旋转处理
else if (parent->_bf == 2 || parent->_bf == -2)
{
	//旋转
	//左单旋
	if (parent->_bf == -2 && cur->_bf == -1)
	{
		RotateR(parent);
	}
//右单旋
void RotateR(node* parent)
{
	node* subL = parent->_left;
	node* subLR = subL->_right;
	subL->_right = parent;
	parent->_left = subLR;
	//subLR可能为空
	if(subLR)
		subLR->_parent = parent;
    node* parentParent = parent->_parent;
	parent->_parent = subL;
	//若parent是根节点
	if (parent == _root)
	{
		_root = subL;
		subL->_parent = nullptr;
	}
	else
	{
		//parent不是根节点
		if (parentParent->_left == parent)
		{
			parentParent->_left = subL;
			subL->_parent = parentParent;
		}
		else
		{
			parentParent->_right = subL;
			subL->_parent = parentParent;
		}
	}
	//修改平衡因子
	parent->_bf = subL->_bf = 0;
}

ok，我们来看分析一下这个代码，看看为什么要这么写——

2.3.2 左单旋 (Right Right Case - RR)

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

在a子树中插入一个新结点，导致a子树的高度从h变成h + 1，不断向上更新平衡因子，导致10的平衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。

旋转核心步骤，因为10 < b子树的值 < 15，将b变成10的右子树，10变成15的左子树，15变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h + 2，符合旋转原则。如果插入之前10整棵树的一个局部子树，旋转后不会再影响上一层，插入结束了

总结一下：

触发条件：

节点 parent 的平衡因子为 2（右子树更高）
其右孩子 subR 的平衡因子为 1（新节点插入在 subR 的右子树）

场景模拟： 与右单旋完全对称。不平衡的“重心”在 parent 的右孩子的右子树上。

操作步骤：

让 subR 的左子树 subRL 成为 parent 的右子树。
让 parent 成为 subR 的左子树。
将 subR 提升为整个子树新的根节点。
更新相关的父指针。
调整平衡因子

代码实现：

//左单旋
else if (parent->_bf == 2 && cur->_bf == 1)
{
	RotateL(parent);
}
//左单旋
void RotateL(node* parent)
{
	node* subR = parent->_right;
	node* subRL = subR->_left;
	subR->_left = parent;
	node* parentParent = parent->_parent;
	parent->_right = subRL;
	parent->_parent = subR;
	if (subRL)
		subRL->_parent = parent;
	//让subR成为新的整棵树的根节点/子树的根节点
	if (parent == _root)
	{
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)
		{
			parentParent->_left = subR;
		}
		else {
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}
	//调整平衡因子
	parent->_bf = subR->_bf = 0;
}

2.3.3 左右双旋 (Left Right Case - LR)

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

这个顺序是有讲究的，不能调换，这里不能说先左单旋再右单旋，这里一定是左单旋再右单旋，先变成纯粹的左单旋，再右单旋，才平衡。

2.3.3.1 情况1：插入前a / b / c高度h == 0

2.3.3.2 情况2：插入前a / b / c高度h == 1

上面两张图分别为左右双旋中h == 0和h == 1两种情况的具体场景的流程分析

下面我们将a / b / c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的细节进一步展开为8和左子树高度为h -1的e和f子树，因为我们要以b的父亲节点5为旋转点进行左单旋，左单旋需要动b树中的左子树。

b子树中新增结点的位置不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里我们要分三个场景讨论——

场景1：h >= 1时，新增结点插入在e⼦树，e子树高度从h-1并为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因⼦为-1，旋转后8和5平衡因⼦为0，10平衡因⼦为1。
场景2：h >= 1时，新增结点插入在f子树，f子树高度h-1变为h并不断更新8->5->10平衡因子，引发旋转，其中8的平衡因子为1，旋转后8和10平衡因子为0，5平衡因子为-1。
场景3：h == 0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新5->10平衡因子，引发旋转，其中8的平衡因子为0，旋转后8和10和5平衡因子均为0。

总结一下：

触发条件：

节点 parent 的平衡因子为 -2
其左孩子 subL 的平衡因子为 1（新节点插入在 subL 的右子树）

场景模拟： 不平衡的形状是一条折线。先对 subL 进行左旋，将其变成 LL 情况，再对 parent 进行右旋。

操作步骤：

以 subL 为轴进行左单旋。
再以 parent 为轴进行右单旋。
新的根节点是 subLR（subL 的右孩子）。

平衡因子更新（关键且复杂）： 双旋后的平衡因子更新取决于插入前 subLR 本身的平衡因子 (bf)：

情况a：subLR->bf == 0 (插入后它就是新节点)
- 旋转后：parent->_bf = 0, subL->_bf = 0, subLR->_bf = 0
情况b：subLR->bf == -1 (新节点在 subLR 的左子树)
- 旋转后：parent->_bf = 1, subL->_bf = 0, subLR->_bf = 0
情况c：subLR->bf == 1 (新节点在 subLR 的右子树)
- 旋转后：parent->_bf = 0, subL->_bf = -1, subLR->_bf = 0
代码实现：

//左右单旋
else if (parent->_bf == -2 && cur->_bf == 1)
{
	RotateLR(parent);
}
				
//左右双旋
void RotateLR(node* parent)
{
	node* subL = parent->_left;
	node* subLR = subL->_right;
	int bf = subLR->_bf;
	RotateL(subL);
	RotateR(parent);
	//修改平衡因子
	if (bf == 0)
	{
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = 0;
		subL->_bf = -1;
		subLR->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 1;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.3.4 右左双旋

了解了左右双旋转的实现逻辑之后，右左双旋的流程也可以自己试着分析一下。

触发条件：

节点 parent 的平衡因子为 2
其右孩子 subR 的平衡因子为 -1（新节点插入在 subR 的左子树）

场景模拟： 与左右双旋完全对称。

操作步骤：

以 subR 为轴进行右单旋。
再以 parent 为轴进行左单旋。
新的根节点是 subRL（subR 的左孩子）。

平衡因子更新： 取决于插入前 subRL 的平衡因子：

情况a：subRL->bf == 0
- 旋转后：parent->_bf = 0, subR->_bf = 0, subRL->_bf = 0
情况b：subRL->bf == 1 (新节点在 subRL 的右子树)
- 旋转后：parent->_bf = -1, subR->_bf = 0, subRL->_bf = 0
情况c：subRL->bf == -1 (新节点在 subRL 的左子树)
- 旋转后：parent->_bf = 0, subR->_bf = 1, subRL->_bf = 0

代码实现：

else if (parent->_bf == 2 && cur->_bf == -1)
{
	RotateRL(parent);
}
//右左双旋
void RotateRL(node* parent)
{
	node* subR = parent->_right;
	node* subRL = subR->_left;
	int bf = subRL->_bf;

	RotateR(subR);
	RotateL(parent);
	//更新平衡因子
	if (bf == 0)
	{
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else if (bf == -1)
	{
		parent->_bf = 0;
		subR->_bf = 1;
		subRL->_bf = 0;
	}
	else if (bf == 1)
	{
		parent->_bf = -1;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

2.4 AVL树的删除

AVL树的删除我们不做过多介绍，很复杂，像前面介绍二叉搜索树的时候也是，插入并不复杂，但是删除非常麻烦，AVL树底层是一棵搜索二叉树，所以它的删除也是非常棘手的一个问题！

如果uu们感兴趣，可以去看这本书——

图书推荐：《殷人昆数据结构：用面向对象方法与C++语言描述》

ok，AVL树的相关内容就说到这里，剩下的查找和搜索二叉树没有太大区别~~~

三、调试技巧

有些uu喜欢通过对比代码的方式来解决BUG，看看和别人写的哪里不一样？其实这是在走捷径！学习的意义：学知识，就是——锻炼学习能力、分析能力、解决问题能力。对比代码、问别人、求助于AI……分析能力、解决问题能力都没有得到锻炼，这对于我们今后的工作是没有好处的。

调试的技巧有很多种，我们平常通过简单地调试实际上只能解决一小部分问题，很多问题仅凭调试是解决不了问题的。我们可以打印、可以打印日志（这个在公司里面很常用）——

AVL.h

#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
using namespace std;
template<class k, class v>
struct ALVTreeNode
{
	pair<k, v> _kv;//存储的是一个key_value的数据
	ALVTreeNode<k, v>* _left;
	ALVTreeNode<k, v>* _right;
	ALVTreeNode<k, v>* _parent;//指向父节点的指针
	int _bf;//平衡因子
	ALVTreeNode(const pair<k, v>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};
template<class k, class v>
class ALVTree
{
	typedef ALVTreeNode<k, v> node;
public:
	bool insert(const pair<k, v>& kv)
	{
		if (_root == nullptr)
		{
			_root = new node(kv);
			return true;
		}
		node* cur = _root;
		node* parent = nullptr;
		while (cur)
		{
			if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else
			{
				return false;
			}
		}
		cur = new node(kv);
		if (parent->_kv.first > kv.first)
		{
			parent->_left = cur;
		}
		else
		{
			parent->_right = cur;
		}
		cur->_parent = parent;
		//调整平衡因子
		//最坏更新到根节点
		while (parent)
		{
			//插入节点都会改变其父节点的平衡因子
			if (parent->_left == cur)
			{
				parent->_bf--;
			}
			else
			{
				parent->_bf++;
			}
			//插入节点的父节点的平衡因子调整完之后，要不要继续向上调整吗？
			//分为3种情况：
			//（1）插入之前一边高一边低，现在左右两边相等，不会再影响上一层，就over
			if (parent->_bf == 0)
			{
				break;//原先是1/-1
			}
			//（2）parent所在的子树高度变了，1或者-1，是由0->1或0->-1
			//插入之前两边一样高，现在一边高一边低，子树的整体高度变了，需要继续往上更新
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				cur = parent;
				parent = parent->_parent;
			}
			//（3）parent所在子树已经不平衡，需要旋转处理
			else if (parent->_bf == 2 || parent->_bf == -2)
			{
				//旋转
				//右单旋
				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);
			}
		}
	}
	//右单旋
	void RotateR(node* parent)
	{
		node* subL = parent->_left;
		node* subLR = subL->_right;
		subL->_right = parent;
		parent->_left = subLR;
		//subLR可能为空
		if (subLR)
			subLR->_parent = parent;
		node* parentParent = parent->_parent;
		parent->_parent = subL;
		//若parent是根节点
		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			//parent不是根节点
			if (parentParent->_left == parent)
			{
				parentParent->_left = subL;
			}
			else
			{
				parentParent->_right = subL;
			}
			subL->_parent = parentParent;
		}
		//修改平衡因子
		parent->_bf = subL->_bf = 0;
	}
	//左单旋
	void RotateL(node* parent)
	{
		node* subR = parent->_right;
		node* subRL = subR->_left;
		subR->_left = parent;
		node* parentParent = parent->_parent;
		parent->_right = subRL;
		parent->_parent = subR;
		if (subRL)
			subRL->_parent = parent;
		//让subR成为新的整棵树的根节点/子树的根节点
		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)
			{
				parentParent->_left = subR;
			}
			else {
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
		//调整平衡因子
		parent->_bf = subR->_bf = 0;
	}
	//左右双旋
	void RotateLR(node* parent)
	{
		node* subL = parent->_left;
		node* subLR = subL->_right;
		int bf = subLR->_bf;
		RotateL(subL);
		RotateR(parent);
		//修改平衡因子
		if (bf == 0)
		{
			parent->_bf = 0;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = 0;
			subL->_bf = -1;
			subLR->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 1;
			subL->_bf = 0;
			subLR->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	//右左双旋
	void RotateRL(node* parent)
	{
		node* subR = parent->_right;
		node* subRL = subR->_left;
		int bf = subRL->_bf;

		RotateR(subR);
		RotateL(parent);
		//更新平衡因子
		if (bf == 0)
		{
			parent->_bf = 0;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else if (bf == -1)
		{
			parent->_bf = 0;
			subR->_bf = 1;
			subRL->_bf = 0;
		}
		else if (bf == 1)
		{
			parent->_bf = -1;
			subR->_bf = 0;
			subRL->_bf = 0;
		}
		else
		{
			assert(false);
		}
	}
	bool Find(size_t first)
	{
		node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first > first)
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < first)
			{
				cur = cur->_right;
			}
			else
			{
				return true;
			}
		}
		return false;
	}
	int Size()
	{
		return _Size(_root);
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	int TreeHigh()
	{
		return _TreeHigh(_root);
	}
	bool IsBalanceTree()
	{
		return _IsBalanceTree(_root);
	}
private:
	int _Size(node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		return _Size(root->_left) + _Size(root->_right) + 1;
	}
	void _Inorder(node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_Inorder(root->_left);
		cout << root->_kv.first << ":" << root->_kv.second <<endl;
		_Inorder(root->_right);
	}
	int _TreeHigh(node* root)
	{
		if (root == nullptr)
		{
			return 0;
		}
		int lefthigh = _TreeHigh(root->_left);
		int righthigh = _TreeHigh(root->_right);
		return lefthigh > righthigh ? lefthigh + 1 : righthigh + 1;
	}
	bool _IsBalanceTree(node* root)
	{
		//空树也是AVL树
		if (root == nullptr)
		{
			return true;
		}
		int leftHigh = _TreeHigh(root->_left);
		int rightHigh = _TreeHigh(root->_right);
		int diff = leftHigh - rightHigh;
		//说明不是AVL树
		if (abs(diff) >= 2 || rightHigh - leftHigh != root->_bf)
		{
			cout << root->_kv.first << "⾼度差异常" << endl;
			return false;
		}
		return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
	}
	node* _root = nullptr;
};

test.cpp

#define  _CRT_SECURE_NO_WARNINGS  1
#include"AVL.h"
void TestAVLTree1()
{
	ALVTree<int, int> t;
	// 常规的测试例 
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	// 特殊的带有双旋场景的测试用例 
	int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };

	for (auto e : a)
	{
		if (e == 14)
		{
			int i = 0;
		}
		t.insert({ e,e });
		//cout << e << "->" << t.IsBalanceTree() << endl;
	}
	t.Inorder();
	cout << t.Size() << endl;
	cout << t.IsBalanceTree() << endl;
}

// 插入一堆随机值，测试平衡，顺便测试一下高度和性能
void TestAVLTree2()
{
	const int N = 100000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));
	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
	}
	size_t begin2 = clock();
	ALVTree<int, int> t;
	for (auto e : v)
	{
		t.insert(make_pair(e, e));
	}
	size_t end2 = clock();
	cout << "Insert:" << end2 - begin2 << endl;
	cout << t.IsBalanceTree() << endl;

	cout << "Height:" << t.TreeHigh() << endl;
	cout << "Size:" << t.Size() << endl;
	size_t begin1 = clock();
	// 确定在的值 
	/*for (auto e : v)
	{
	t.Find(e);
	}*/
	// 随机值 
	for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}
	size_t end1 = clock();
	cout << "Find:" << end1 - begin1 << endl;
}

int main()
{
	//TestAVLTree1();
	TestAVLTree2();

	return 0;
}

运行截图：