C++学习之数据结构：AVL树-EW帮帮网

1962年，苏联数学家 Georgy Adelson-Velsky 和 Evgenii Landis 在论文《信息组织算法》中首次提出一种新型二叉树结构。这个后来以二人名字首字母命名的 AVL树，解决了传统二叉搜索树(BST)的致命缺陷——数据有序插入时的退化成链表问题。它的诞生早于红黑树（1972年），成为计算机科学史上第一个自平衡二叉树结构，为后续所有平衡树算法奠定了理论基础。

AVL的概念

AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树，通过控制⾼度差去控制平衡

AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。

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

AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在，那么增删查改的效率也可

以控制在O（logN），相⽐⼆叉搜索树有了本质的提升

AVL的特性

1. 严格平衡性

平衡因子约束：每个节点的平衡因子（左子树高度 - 右子树高度）绝对值不超过1
数学保证：树高 h ≤ 1.44log₂(n+2)，确保树结构始终接近完全二叉树

2. 动态自平衡机制

实时监控：每次插入/删除后自动检测失衡节点

旋转修复：通过四种旋转操作恢复平衡：

失衡类型	旋转方案	示意图
LL型	单次右旋	→ /
RR型	单次左旋	← \
LR型	先左旋后右旋	→ ← ↻
RL型	先右旋后左旋	← → ↻

3. 复杂度保证

操作       | 时间复杂度 | 空间复杂度
-------------------------------
查找       | O(log n)   | O(1)
插入       | O(log n)   | O(1)
删除       | O(log n)   | O(1)
平衡维护   | O(1)旋转   | O(log n)回溯路径

4. 结构稳定性

最坏情况优化：消除二叉搜索树的退化风险
高度一致性：任意子树高度差≤1，确保操作可预测性

相比于二叉搜索树的优点

1. 性能稳定性飞跃

场景	二叉搜索树(BST)	AVL树
有序数据插入	退化为链表 O(n)	保持平衡 O(log n)
随机数据查询	平均 O(log n)	最坏 O(log n)
高频查找操作	性能波动大	性能稳定

示例：插入序列 [1,2,3,4,5]

BST 退化为链表，查找5需5次比较
AVL 保持平衡，查找5仅需2次比较

2. 空间效率提升

紧凑结构：AVL树高比随机BST低约45%
缓存友好：更矮的树 → 更少的缓存失效

3. 实时系统优势

操作可预测：严格保证单次操作O(log n)
无突发病态：消除BST的O(n)退化风险
关键应用场景：
- 航空控制系统（硬实时要求）
- 医疗设备调度
- 高频交易系统

4. 范围查询优化

中序遍历增强：平衡结构使范围查询更高效
内存局部性：平衡树减少磁盘I/O（数据库索引场景）

// AVL树范围查询示例
auto it_low = avl_tree.lower_bound(100);
auto it_high = avl_tree.upper_bound(200);
while (it_low != it_high) 
{
  process(*it_low++); // 高效连续访问
}

AVL树的实现

AVL树的结构

// 定义AVL树节点
template<class K, class V>
//AVL树三叉链
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)
	{
	}
};
//定义AVL树类
template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;
public:

private:
	Node* _root = nullptr;

};

AVL的插入

AVL插入一个数值的过程

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。

2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析。

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

4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树的⾼度，不会再影响上⼀层，所以插⼊结束

平衡因子变化

更新原则：

• 平衡因⼦ = 右⼦树⾼度-左⼦树⾼度

• 只有⼦树⾼度变化才会影响当前结点平衡因⼦。

• 插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在

parent的左⼦树，parent平衡因⼦--

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

更新停⽌条件：

更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0 或者 1->0，说明更新前parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束。

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

更新后parent的平衡因⼦等于2 或 -2，更新前更新中parent的平衡因⼦变化为1->2 或者 -1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：1、把parent⼦树旋转平衡。2、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。

不断更新，更新到根，跟的平衡因⼦是1或-1也停⽌了。

代码实现

//插入
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)
	{
		// 更新平衡因子
		if (cur == parent->_left)
			parent->_bf--;
		else
			parent->_bf++;
		if (parent->_bf == 0)
		{
			// 更新结束
			break;
		} 
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			// 继续往上更新
			cur = parent;
			parent = parent->_parent;
		} 
		else if (parent->_bf == 2 || parent->_bf == -2)
		{
			// 不平衡了，旋转处理
			break;
		} 
		else
		{
			//插入前就有2/-2的节点，不是AVL树了
			assert(false);
		}
	} 
	return true;
}

AVL树的旋转

AVL树的插入实现离不开AVL树的旋转，接下来我们将深入解释AVL树的旋转

旋转的原则

1. 保持搜索树的规则

2. 让旋转的树从不满⾜变平衡，其次降低旋转树的⾼度旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

旋转分为：右单旋、左单旋、左右双旋、右左双旋。下面依次来介绍

右单旋

本图1展⽰的是10为根的树，有a/b/c抽象为三棵⾼度为h的⼦树(h>=0)，a/b/c均符合AVL树的要求。

10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是⾼度为h的⼦树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景，实际右单旋形态有很多种，具体图2/图3/图4/图5进⾏了详细描述。

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

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

右单旋的特征：parent的平衡因子是-2，cur的平衡因子是-1。（cur为当前节点）

右单旋代码实现

//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;// 子树的左子树
	Node* subLR = subL->_right;// 子树的左子树的右子树
	// 注意除了修改孩子指针的指向外还要修改父亲指针的指向
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	Node* parentParent = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	// parent可能是整棵树的根，也可能是局部的子树
	// 如果是整棵树的根就修改_root
	// 如果是局部的指针要根上一层链接
	if (parentParent == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	} 
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subL;
		} 
		else
		{
			parentParent->_right = subL;
		} 
		subL->_parent = parentParent;
	} 
	parent->_bf = subL->_bf = 0;
}

左单旋

本图6展⽰的是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整棵树的⼀个局部⼦树，旋转后不会再影响上⼀层，插⼊结束了

左单旋代码实现

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	Node* parentParent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	} 
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		} 
		else
		{
			parentParent->_right = subR;
		} 
		subR->_parent = parentParent;
	} 
	parent->_bf = subR->_bf = 0;
}

左右双旋转

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

图7和图8分别为左右双旋中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。

左右双旋的代码实现

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	Node* parentParent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	} 
	else
	{
		if (parent == parentParent->_left)
		{
			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(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);
	}
}

右左双旋

• 跟左右双旋类似，下⾯我们将a/b/c⼦树抽象为⾼度h的AVL⼦树进⾏分析，另外我们需要把b⼦树的细节进⼀步展开为12和左⼦树⾼度为h-1的e和f⼦树，因为我们要对b的⽗亲15为旋转点进⾏右单旋，右单旋需要动b树中的右⼦树。b⼦树中新增结点的位置不同，平衡因⼦更新的细节也不同，通过观察12的平衡因⼦不同，这⾥我们要分三个场景讨论。

场景1：h >= 1时，新增结点插⼊在e⼦树，e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因⼦为0，15平衡因⼦为1。

场景2：h >= 1时，新增结点插⼊在f⼦树，f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为1，旋转后15和12平衡因⼦为0，10平衡因⼦为-1。

场景3：h == 0时，a/b/c都是空树，b⾃⼰就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋转，其中12的平衡因⼦为0，旋转后10和12和15平衡因⼦均为0。

右左双旋的代码实现

//右左双旋	
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 = 0;
		subRL->_bf = 0;
		parent->_bf = -1;
	} 
		else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_bf = 0;
		parent->_bf = 0;
	} 
		else
	{
	assert(false);
	}
}

接下来我们将对AVL树的插入代码进行汇总。

AVL树的插入代码

//插入
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)
	{
		// 更新平衡因子
		if (cur == parent->_left)
			parent->_bf--;
		else
			parent->_bf++;
		if (parent->_bf == 0)
		{
			// 更新结束
			break;
		} 
		else if (parent->_bf == 1 || parent->_bf == -1)
		{
			// 继续往上更新
			cur = parent;
			parent = parent->_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);
			}
			break;
		} 
		else
		{
			//插入前就有2/-2的节点，不是AVL树了
			assert(false);
		}
	} 
	return true;
}
//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;// 子树的左子树
	Node* subLR = subL->_right;// 子树的左子树的右子树
	// 注意除了修改孩子指针的指向外还要修改父亲指针的指向
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;
	Node* parentParent = parent->_parent;
	subL->_right = parent;
	parent->_parent = subL;
	// parent可能是整棵树的根，也可能是局部的子树
	// 如果是整棵树的根就修改_root
	// 如果是局部的指针要根上一层链接
	if (parentParent == nullptr)
	{
		_root = subL;
		subL->_parent = nullptr;
	} 
	else
	{
		if (parent == parentParent->_left)
		{
			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;
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;
	Node* parentParent = parent->_parent;
	subR->_left = parent;
	parent->_parent = subR;
	if (parentParent == nullptr)
	{
		_root = subR;
		subR->_parent = nullptr;
	} 
	else
	{
		if (parent == parentParent->_left)
		{
			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(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 = 0;
		subRL->_bf = 0;
		parent->_bf = -1;
	} 
		else if (bf == -1)
	{
		subR->_bf = 1;
		subRL->_bf = 0;
		parent->_bf = 0;
	} 
		else
	{
	assert(false);
	}
}

AVL树的查找

那⼆叉搜索树逻辑实现即可，搜索效率为 O(logN)

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

AVL树的平衡检查

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

AVL树的删除（了解）

AVL树主要是了解AVL树的更新和旋转，前面AVL树的插入已经够让我们去了解AVL树的旋转了。接下来AVL树的删除主要是为了扩展内容。

想进一步了解可以参考这本书：《殷⼈昆数据结构：⽤⾯向对象⽅法与C++语⾔描述》
接下来开始讲述：

删除操作比插入更复杂，因为删除节点后可能会破坏AVL树的平衡性，需要向上调整平衡因子并进行旋转操作。

删除步骤：

1. 首先按照二叉搜索树的规则找到要删除的节点。

2. 删除节点，并调整树的结构（分三种情况：被删除节点是叶子节点、有一个孩子、有两个孩子）。

3. 调整平衡因子，如果平衡因子变为2或-2，则进行旋转调整，旋转后可能还需要继续向上调整。注意：删除节点后，我们需要从被删除节点的父节点开始向上调整平衡因子，并检查是否失衡（平衡因子为2或-2）。

失衡的情况有四种，对应四种旋转：左单旋、右单旋、左右双旋、右左双旋。

在删除节点时，我们可能会遇到三种情况：

a. 被删除节点是叶子节点：直接删除，然后从父节点开始调整。

b. 被删除节点有一个孩子：用孩子节点替代被删除节点，然后从父节点开始调整。

c. 被删除节点有两个孩子：找到该节点的后继节点（右子树中最小的节点）或前驱节点（左子树中最大的节点），用后继（或前驱）节点的值替换被删除节点的值，然后删除后继（或前驱）节点。由于后继（前驱）节点最多只有一个孩子，因此可以转换为情况a或b。

删除节点后，平衡因子的更新规则：

- 如果删除的是左子树中的节点，则父节点的平衡因子加1（因为左子树高度减少）。 - 如果删除的是右子树中的节点，则父节点的平衡因子减1。更新后，根据父节点的平衡因子进行判断： - 如果更新后平衡因子为0，说明以父节点为根的子树高度减少了1，需要继续向上更新。

- 如果更新后平衡因子为1或-1，说明以父节点为根的子树高度不变，停止更新。 - 如果更新后平衡因子为2或-2，则需要进行旋转调整，旋转后，旋转子树的高度可能减少1，因此需要继续向上更新。旋转操作后，树的高度可能会减少1，所以旋转后需要继续向上更新平衡因子，直到根节点。

但是，注意在删除操作中，旋转后平衡因子的调整规则和插入时不同？实际上，旋转函数本身的操作是一样的，但是旋转后的平衡因子更新以及是否需要继续向上更新，需要根据情况判断。

在删除操作中，旋转后如果旋转子树的高度减少了1，那么就需要继续向上更新。而旋转函数内部会更新节点的平衡因子，但旋转后原父节点（旋转后的子节点）的平衡因子可能不为0（在双旋时可能为0也可能不为0），所以我们需要在旋转后判断是否需要继续向上更新。

因此，我们可能需要修改旋转函数，使其返回旋转后新的子树根节点（其实我们已有的旋转函数已经修改了指针关系，但没有返回），但这里我们不需要返回，因为旋转函数已经通过指针修改了结构。但是，在删除操作中，旋转后我们需要知道旋转子树的高度是否减少，从而决定是否继续向上更新。

实际上，在旋转函数中，我们设旋转后的子树根节点为newParent，那么旋转后newParent的平衡因子为0，但是旋转后整个子树的高度可能比旋转前减少1（在删除时，因为原本较高的子树被删除一个节点，旋转后子树高度可能减少1）。因此，旋转后我们需要继续向上更新。

具体步骤：

1. 找到要删除的节点。

2. 执行删除操作，并记录实际被删除节点的父节点（因为可能后继节点被删除，所以实际被删除节点的父节点不一定是当前节点的父节点）。

3. 从实际被删除节点的父节点开始向上更新平衡因子，并进行旋转调整，直到根节点。注意：删除节点时，如果节点有两个孩子，我们选择用后继节点（右子树的最小节点）来替换，然后删除后继节点（后继节点一定没有左孩子，因为它是右子树的最小节点）。

实现细节： - 我们用一个指针realDelParent来记录实际被删除节点的父节点，因为当被删除节点有两个孩子时，实际被删除的是后继节点，而后继节点的父节点可能不是原节点。

步骤：

1. 查找要删除的节点。

2. 如果没有找到，返回false。

3. 如果找到，分情况删除：

a. 左右孩子都为空：直接删除，然后从父节点开始更新。

b. 只有左孩子为空：用右孩子替代。

c. 只有右孩子为空：用左孩子替代。

d. 左右孩子都不为空：找到后继节点（右子树的最左节点），将后继节点的值赋给当前节点，然后删除后继节点（此时后继节点最多只有一个右孩子）。

4. 实际删除节点后，记录实际被删除节点的父节点（可能是原节点的父节点，也可能是后继节点的父节点）。

5. 从实际被删除节点的父节点开始向上更新平衡因子，并检查是否需要旋转。

AVL树的删除的代码实现

//删除函数
bool Erase(const K& key) 
{
	Node* parent = nullptr;
	Node* cur = _root;
	// 查找待删除节点
	while (cur) 
	{
		if (key < cur->_kv.first) 
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (key > cur->_kv.first) 
		{
			parent = cur;
			cur = cur->_right;
		}
		else 
		{
			break; // 找到节点
		}
	}
	if (cur == nullptr) 
	{
		return false; // 未找到
	}

	Node* realDelParent = parent; // 实际删除节点的父节点
	bool isLeftChild = false;     // 被删节点是否是父节点的左孩子

	// 情况1: 叶子节点或只有一个孩子
	if (cur->_left == nullptr || cur->_right == nullptr) 
	{
		Node* child = (cur->_left) ? cur->_left : cur->_right;

		if (cur == _root)
		{
			_root = child;
			if (_root) _root->_parent = nullptr;
			delete cur;
			return true;
		}
		else 
		{
			if (parent->_left == cur) 
			{
				parent->_left = child;
				isLeftChild = true;
			}
			else 
			{
				parent->_right = child;
				isLeftChild = false;
			}

			if (child) 
			{
				child->_parent = parent;
			}
			realDelParent = parent;
			delete cur;
		}
	}
	// 情况2: 有两个孩子
	else 
	{ 
		// 找到右子树的最小节点（后继）
		Node* minParent = cur;
		Node* minRight = cur->_right;
		bool minIsLeft = false;

		while (minRight->_left) 
		{
			minParent = minRight;
			minRight = minRight->_left;
			minIsLeft = true;
		}

		// 用后继节点的值替换当前节点
		cur->_kv = minRight->_kv;

		// 删除后继节点
		if (minIsLeft) 
		{
			minParent->_left = minRight->_right;
			if (minRight->_right) 
			{
				minRight->_right->_parent = minParent;
			}
		}
		else 
		{
			minParent->_right = minRight->_right;
			if (minRight->_right) 
			{
				minRight->_right->_parent = minParent;
			}
		}

		realDelParent = minParent;
		isLeftChild = minIsLeft;
		delete minRight;
	}

	// 从实际删除节点的父节点开始向上调整平衡因子
	Node* current = realDelParent;
	while (current) 
	{
		// 更新平衡因子
		if ((current == realDelParent && isLeftChild) ||
			(current != realDelParent && current->_left == realDelParent)) 
		{
			current->_bf++; // 左子树高度减少
		}
		else 
		{
			current->_bf--; // 右子树高度减少
		}

		realDelParent = current; // 保存当前节点作为下一次迭代的父节点
		Node* parentNode = current->_parent;

		// 检查平衡状态
		if (current->_bf == 1 || current->_bf == -1) 
		{
			// 高度不变，停止更新
			break;
		}
		else if (current->_bf == 0)
		{
			// 高度减少，继续向上更新
			current = parentNode;
		}
		else if (current->_bf == 2 || current->_bf == -2)
		{
			// 需要旋转调整
			Node* newRoot = current;
			if (current->_bf == 2) 
			{ // 左子树高
				if (current->_left->_bf >= 0) 
				{ // 右单旋
					RotateR(current);
					newRoot = current->_parent; // 旋转后current的父节点是新根
				}
				else 
				{ // 左右双旋
					RotateLR(current);
					newRoot = current->_parent;
				}
			}
			else if (current->_bf == -2)
			{ // 右子树高
				if (current->_right->_bf <= 0) 
				{ // 左单旋
					RotateL(current);
					newRoot = current->_parent;
				}
				else 
				{ // 右左双旋
					RotateRL(current);
					newRoot = current->_parent;
				}
			}

			// 旋转后新根节点的平衡因子为0，但子树高度可能减少
			if (newRoot->_bf == 0) 
			{
				current = newRoot->_parent; // 继续向上更新
			}
			else 
			{
				// 旋转后子树高度不变，停止更新
				break;
			}
		}
		else 
		{
			// 平衡因子错误
			assert(false);
		}
	}

	return true;
}

本篇内容就到这里了，喜欢请点个赞，谢谢。

封面图自取：

C++学习之数据结构：AVL树

AVL树介绍

历史溯源：数学家的优雅解法