今天你学C++了吗？——AVL树

用户11352420

发布于 2025-05-20 09:27:51

4390

AVL的概念

什么是AVL呢？

AVL树是一种自平衡的二叉搜索查找树，在C++中常用于实现高效的动态集合操作，例如插入、删除和查找。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们于1962年首次提出这一数据结构。AVL树的出现是为了控制搜索二叉树的平衡，所以AVL树引入了一个平衡因子的概念~

AVL树要求任何节点的两个子树的高度差（称为平衡因子）的绝对值不超过1。
平衡因子定义为：平衡因子 = 左子树高度 - 右子树高度。（当然也可以是【右子树高度 - 左子树高度】）
如果插入或删除节点导致树的平衡性被破坏，AVL树会通过旋转操作（单旋转或双旋转）重新恢复平衡，这个是我们后面的重点讲解部分~

有的人可能会说，既然是平衡的，那么为什么不是高度差为0呢？这一点事实上是很难做到的，因为要保证每一个节点高度差为0，那么只有满二叉树才可以满足这个条件了~这样不就只可以表示满二叉树了吗！高度差为0看似完美，但在实际节点数分布下（如2个节点、4个节点等）往往无法实现。所以高度差不超过1的规则，既保证了树的平衡性，又允许树根据节点数灵活调整结构，避免因过度限制导致构建失败。这种设计在保持高效操作的同时，实现了平衡性与灵活性的统一！

我们可以来看看例子：（以【右子树高度 - 左子树高度】为标准）

不难看出下面的这样一颗二叉树就是AVL树，每一个结点的左右子树高度差都不大于1~

但是下面的这一棵二叉树就不是AVL树，结点10的左右子树高度差为2，不满足条件~

AVL树的结构

结合前面博客中二叉搜索树的结构二叉搜索树，那么AVL树是平衡的二叉搜索树，那么肯定有二叉搜索树的大体结构~

二叉搜索树的结点应该保存三个数据： 1、当前结点保存的数据 2、当前结点的左子树地址 3、当前结点的右子树地址 AVL树结点还需要添加部分内容，一个是平衡因子，一个是双亲指针~ 平衡因子好理解，双亲指针有什么作用呢？在后面我们会进行解释~

知道了结点的定义，我们就可以这样定义AVL树的结构：

//AVL树结点结构
template<class K,class V>
struct AVLTreeNode
{
	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;
private:
	Node* _root = nullptr;//根节点

public:
	//功能实现
};

知道了AVL树的结构，接下来我们就可以对AVL树进行插入，删除等操作了

AVL树的插入

我们首先来看看对AVL树的插入数据操作~

AVL树插入值流程

插入操作：依据二叉搜索树的规则来插入一个值。
平衡因子更新：新结点插入后，仅会对祖先结点的高度产生影响，进而可能改变部分祖先结点的平衡因子。因此，需要沿着从新增结点到根结点的路径更新平衡因子。在最坏的情况下，可能需要一直更新到根结点；而在某些情况下，更新到中间某个结点就可以停止了，在后续会详细分析具体情况。
插入结束条件：
- 若在更新平衡因子的过程中没有出现不平衡的情况，那么插入操作结束。
- 若在更新平衡因子的过程中出现了不平衡，对不平衡的子树进行旋转操作。旋转操作在调整平衡的同时，会降低子树的高度，使得不再影响上一层结点，此时插入操作结束。

平衡因子更新

更新原则

我们实现的AVL树平衡因子的计算公式为：平衡因子 = 右子树高度 - 左子树高度。
只有当子树的高度发生变化时，才会影响当前结点的平衡因子。
插入结点会导致高度增加，所以：
- 若新增结点位于父结点（parent）的右子树，那么父结点的平衡因子加1（parent的平衡因子++）。
- 若新增结点位于父结点（parent）的左子树，那么父结点的平衡因子减1（parent平衡因子--）。
父结点所在子树的高度是否发生变化，决定了是否需要继续向上更新平衡因子。

更新停止条件

平衡因子变为0的情况：当更新操作完成后，若父结点（parent）的平衡因子等于0，且在更新过程中其平衡因子变化为 -1→0 或者 1→0，这表明在更新之前，父结点的子树呈现一边高一边低的状态，而新增结点被插入到了较低的那一边。如此一来，插入操作后父结点所在的子树高度并未发生改变，也就不会对父结点的父结点的平衡因子产生影响，此时更新操作可以结束。

平衡因子变为1或 -1的情况：更新结束后，若父结点的平衡因子为1或 -1，且在更新前和更新过程中其平衡因子变化为 0→1 或者 0→ -1，这意味着在更新之前，父结点的子树两边高度是相等的。然而，新增结点插入之后，父结点所在的子树出现了一边高一边低的情况。虽然此时父结点所在的子树仍然符合平衡要求，但是子树的高度增加了1，这会对父结点的父结点的平衡因子产生影响，所以需要继续向上进行更新操作。

平衡因子变为2或 -2的情况：更新完成后，若父结点的平衡因子为2或 -2，且在更新前和更新过程中其平衡因子变化为 1→2 或者 -1→ -2，这说明在更新之前，父结点的子树就是一边高一边低的状态，而新增结点插入到了较高的那一边，导致父结点所在的子树较高的那一边变得更高，从而破坏了子树的平衡状态，父结点所在的子树不再符合平衡要求，需要进行旋转处理。旋转操作有两个目标：一是将父结点的子树调整至平衡状态；二是降低父结点子树的高度，使其恢复到插入结点之前的高度。因此，旋转操作完成后，无需再继续向上进行更新，插入操作结束。（旋转策略我们后面会重点讲解）

更新到根结点的情况：在不断向上更新的过程中，如果更新操作一直进行到根结点，即便根结点的平衡因子为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 (kv.first < cur->_kv.first)//比当前结点小，插入当前结点左子树
		{
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)//比当前结点大，插入当前结点右子树
		{
			parent = cur;
			cur = cur->_right;
		}
		else//相等就不进行插入，插入失败
		{
			return false;
		}
	}
	//parent即为插入结点父结点
	cur = new Node(kv);
	//判断是插入父结点左边还是右边
	if (kv.first < parent->_kv.first)
	{
		parent->_left = cur;
	}
	else if (kv.first > parent->_kv.first)
	{
		parent->_right = cur;
	}

	cur->_parent = parent;

	//平衡因子更新
	while (parent)
	{
		//我们实现的AVL树平衡因子的计算公式为：平衡因子 = 右子树高度 - 左子树高度
		if (parent->_left == cur)
			//插入结点在左子树,父结点平衡因子--
		{
			parent->_bf--;
		}
		else if (parent->_right == cur)
			//插入结点在右子树，父结点平衡因子++
		{
			parent->_bf++;
		}

		//分情况讨论

		//1、父结点平衡因子更新为0，不需要继续向上更新
		if (parent->_bf == 0)
			break;

		//2、父结点平衡因子更新为-1或者1，需要继续向上更新
		//如果当前父结点为根结点，parent会到空，跳出循环
		else if (parent->_bf == -1 || parent->_bf == 1)
		{
			cur = parent;
			parent = parent->_parent;
		}

		//3、父结点平衡因子更新为-2或者2，已经不平衡需要旋转处理
		else if (parent->_bf == -2 || parent->_bf == 2)
		{
			//旋转处理

			break;
		}

		//其他情况，说明更新有问题
		else
		{
			assert(false);
		}

	}

	//更新结束
	return true;

}

总的逻辑写完了，接下来就是我们的旋转处理了，我们继续来看看~

旋转处理

在前面我们已经进行了平衡因子的更新，我们可以发现当有结点的平衡因子达到2或者-2的时候，这个时候就不是平衡二叉树了，那么我们就需要进行旋转处理~

旋转的原则

保持搜索树的规则（高度差<=1)
让旋转的树从不满足到变平衡，降低旋转树的高度
旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

左单旋(右边高往左旋）

我们以这个例子来看看：

我们进行左单旋

仅仅看这个，可能会有一点难以理解，我们根据这个来画一个通用的图：

插入前（h表示任意高度，可以是0，可以是1，可以是2....)

插入后：

左单旋（B变成parent的右边，parent变成cur的左边）

为了后面代码实现，我们这里把cur记为subR，B记录为subRL~

有了前面的画图，接下来我们进行代码实现：

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

	//更改指向
	subR->_left = parent;
	parent->_right = subRL;

	//修改变动结点（subR，subRL，parent）的parent

	if(subRL)//subRL可能为空
		subRL->_parent = parent;
	parent->_parent = subR;

	//subR可能成为整棵树的根结点，需要进行判断更新subR的parent
	Node* parentParent = parent->_parent;
	if (parentParent == nullptr)
	{
		//subR成为整棵树的根结点
		_root = subR;
		subR->_parent = nullptr;
	}
	else
	{
		if (parentParent->_left == parent)//判断原节点是父亲的左/右结点
		{
			parentParent->_left == subR;
		}
		else
		{
			parentParent->_right = subR;
		}
		//更新subR父结点
		subR->_parent = parentParent;
	}

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

右单旋(左边高往右旋）

相信有了左单旋的基础，右单旋就更加简单了~

我们依然进行画图理解：

前面我们提到过h是可以代表任意高度的，这里我们讨论几种情况：

情况一：h==0

情况二：h==1

情况三：h==2

情况四：h==3

我们可以发现不论是哪一种情况，都是可以进行相同的右单旋操作，也就有了我们的通用方案~

接下来，我们就进行代码实现：

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

	//旋转操作
	parent->_left = subLR;
	subL->_right = parent;

	//更新相应结点parent
	if (subLR)//h可能等于0，那么subLR可能为空
		subLR->_parent = parent;
	
	Node* parentParent = parent->_parent;//保存父结点的父亲
	if (parentParent == nullptr)//说明原来的父结点是根结点
	{
		_root = subL;
		subL->_parent = nullptr;
	}

	else
	{
		if (parentParent->_left == parent)//父结点是左孩子
		{
			parentParent->_left = subL;
		}

		else
		{
			//父结点是右孩子
			parentParent->_right = subL;
		}

		subL->_parent = parentParent;
	}

	parent->_parent = subL;

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

}

代码大致上是差不多的，只是逻辑上有一些区别~

有了左单旋和右单旋，接下来，我们来看看更加复杂的情况~

左右双旋

在有些情况下，我们仅仅进行左单旋或者右单旋是无法解决问题的，比如说下面的例子~

示例：不再是单纯的左边高，结点10是左边高，而结点5是右边高~也就可以发现插入节点之后parent和cur结点平衡因子异号~

显然进行简单的单旋操作就不能解决问题了~单旋之后依然是不平衡的~

我们继续以一个通用的例子进行分析：

我们可以看到在b子树新增加结点导致5结点右边高，10结点左边高，简单的单旋无法重新设置平衡，我们需要进行双旋，双旋就是利用两次单旋，经过第一次单旋让10结点变成单纯的左边高，再一次单旋就可以达到平衡~

我们对b子树进行进一步的拆分

b子树新增加的结点点有下面的三种情况，我们来进行逐一分析：

情况一：新增加结点在e子树

第一步：以5（subL）为旋转点进行左单旋

第二步；以10结点（parent）为旋转点进行右单旋

经过两步单旋操作之后，这就平衡了~

情况二：新增加结点在f子树

情况三：新增结点就是b子树（也就是h==0）

这三种情况都是先进行左单旋再进行右单旋，操作是一样的，那么我们就可以进行代码复用，使用前面的左右单旋代码，这里比较麻烦的是平衡因子的更新~

我们可以看到三种情况的平衡因子是不一样的，我们可以根据结点插入后subLR的平衡因子来进行分情况讨论更新平衡因子~

代码实现：

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

	//根据没有旋转前subLR的平衡因子分情况讨论
	int bf = subLR->_bf;
	
	//先以subL为旋转点左旋
	RotateL(subL);
	//再以parent为旋转点右旋
	RotateR(parent);
	//每一个结点父结点已经更新，只需要修改平衡因子
	if (bf == -1)//插入在e子树
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 1;
	}
	else if (bf == 1)//插入在f子树
	{
		subLR->_bf = 0;
		subL->_bf = -1;
		parent->_bf = 0;
	}
	else if (bf == 0)//插入在b子树自己
	{
		subLR->_bf = 0;
		subL->_bf = 0;
		parent->_bf = 0;
	}

	else//其他情况，说明有问题
	{
		assert(false);
	}
}

右左双旋

知道了左右双旋，那么右左双旋就好分析了~

我们同样用一个通用的例子来进行分析：

我们直接画图理解

对b子树进行进一步拆分：

b子树新增加的结点点有下面的三种情况，我们来进行逐一分析：

情况一：新增加结点在e子树

情况二：新增加结点在f子树

第一步：以15（subR）为旋转点进行右单旋

第二步；以10结点（parent）为旋转点进行左单旋

完整图

情况三：新增结点就是b子树（也就是h==0）

这三种情况都是先进行右单旋再进行左单旋，操作是一样的，那么我们就可以进行代码复用，使用前面的左右单旋代码，这里比较麻烦的是平衡因子的更新~

根据经验，我们可以利用结点插入后subRL的平衡因子来进行分情况讨论更新平衡因子~

代码实现：

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

	//根据没有旋转前subRL的平衡因子分情况讨论
	int bf = subRL->_bf;

	//先以subR为旋转点右旋
	RotateR(subR);
	//再以parent为旋转点左旋
	RotateL(parent);
	//每一个结点父结点已经更新，只需要修改平衡因子

	if (bf == -1)//插入在e子树
	{
		subRL->_bf = 0;
		subR->_bf = 1;
		parent->_bf = 0;
	}
	else if (bf == 1)//插入在f子树
	{
		subRL->_bf = 0;
		subR->_bf = 0;
		parent->_bf = -1;
	}
	else if (bf == 0)//插入在b子树自己
	{
		subRL->_bf = 0;
		subR->_bf = 0;
		parent->_bf = 0;
	}

	else//其他情况，说明有问题
	{
		assert(false);
	}
}

AVL树的查找

我们知道AVL树是二叉平衡搜索树，那么我们就可以使用二叉搜索树的查找逻辑~

初始化：从根节点开始遍历
循环比较：
- 条件：只要当前节点不为空且未找到目标值，继续循环。
- 比较操作：
  - 若目标值等于当前节点值，查找成功，返回当前节点。
  - 若目标值小于当前节点值，移动到左子节点。
  - 若目标值大于当前节点值，移动到右子节点。
终止条件：
- 找到目标节点，返回结果。
- 当前节点为空，说明目标值不存在。

代码实现：

//查找结点
Node* Find(const K&key)//查找key
{
	Node* cur = _root;

	while (cur)
	{
		if (cur->_kv.first > key)//key在左子树
		{
			cur = cur->_left;
		}
		else if (cur->_kv.first < key)//key在右子树
		{
			cur = cur->_right;
		}

		else
		{
			return cur;//相等，返回当前结点
		}
	}

	//没有找到返回空
	return nullptr;
}

AVL树的实现就结束了~

总代码

#include<iostream>
#include<vector>
#include<cassert>
using namespace std;

//AVL树结点结构
template<class K,class V>
struct AVLTreeNode
{
	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;
private:
	Node* _root = nullptr;//根节点

public:
	//功能实现

	//查找结点
	Node* Find(const K&key)//查找key
	{
		Node* cur = _root;

		while (cur)
		{
			if (cur->_kv.first > key)//key在左子树
			{
				cur = cur->_left;
			}
			else if (cur->_kv.first < key)//key在右子树
			{
				cur = cur->_right;
			}

			else
			{
				return cur;//相等，返回当前结点
			}
		}

		//没有找到返回空
		return 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 (kv.first < cur->_kv.first)//比当前结点小，插入当前结点左子树
			{
				parent = cur;
				cur = cur->_left;
			}
			else if (kv.first > cur->_kv.first)//比当前结点大，插入当前结点右子树
			{
				parent = cur;
				cur = cur->_right;
			}
			else//相等就不进行插入，插入失败
			{
				return false;
			}
		}
		//parent即为插入结点父结点
		cur = new Node(kv);
		//判断是插入父结点左边还是右边
		if (kv.first < parent->_kv.first)
		{
			parent->_left = cur;
		}
		else if (kv.first > parent->_kv.first)
		{
			parent->_right = cur;
		}

		cur->_parent = parent;

		//平衡因子更新
		while (parent)
		{
			//我们实现的AVL树平衡因子的计算公式为：平衡因子 = 右子树高度 - 左子树高度
			if (parent->_left == cur)
				//插入结点在左子树,父结点平衡因子--
			{
				parent->_bf--;
			}
			else if (parent->_right == cur)
				//插入结点在右子树，父结点平衡因子++
			{
				parent->_bf++;
			}

			//分情况讨论

			//1、父结点平衡因子更新为0，不需要继续向上更新
			if (parent->_bf == 0)
				break;

			//2、父结点平衡因子更新为-1或者1，需要继续向上更新
			//如果当前父结点为根结点，parent会到空，跳出循环
			else if (parent->_bf == -1 || parent->_bf == 1)
			{
				cur = parent;
				parent = parent->_parent;
			}

			//3、父结点平衡因子更新为-2或者2，已经不平衡需要旋转处理
			else if (parent->_bf == -2 || parent->_bf == 2)
			{
				//旋转处理

				//插入在右子树(右边高）——左单旋
				if (parent->_bf == 2 && cur->_bf == 1)
				{
					RotateL(parent);
				}

				插入在左子树(左边高）——左单旋
				else if (parent->_bf == -2 && cur->_bf == -1)
				{
					RotateR(parent);
				}
				//parent与cur平衡因子异号需要进行双旋

				//左右双旋
				else if (parent->_bf == -2 && cur->_bf == 1)
				{
					RotateLR(parent);
				}

				//右左双旋
				else if (parent->_bf == 2 && cur->_bf == -1)
				{
					RotateRL(parent);
				}


				break;
			}

			//其他情况，说明更新有问题
			else
			{
				assert(false);
			}

		}

		//更新结束
		return true;

	}

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

		//更改指向
		subR->_left = parent;
		parent->_right = subRL;

		//修改变动结点（subR，subRL，parent）的parent

		if(subRL)//subRL可能为空
			subRL->_parent = parent;
		parent->_parent = subR;

		//subR可能成为整棵树的根结点，需要进行判断更新subR的parent
		Node* parentParent = parent->_parent;
		if (parentParent == nullptr)
		{
			//subR成为整棵树的根结点
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parentParent->_left == parent)//判断原节点是父亲的左/右结点
			{
				parentParent->_left == subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			//更新subR父结点
			subR->_parent = parentParent;
		}

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

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

		//旋转操作
		parent->_left = subLR;
		subL->_right = parent;

		//更新相应结点parent
		if (subLR)//h可能等于0，那么subLR可能为空
			subLR->_parent = parent;
		
		Node* parentParent = parent->_parent;//保存父结点的父亲
		if (parentParent == nullptr)//说明原来的父结点是根结点
		{
			_root = subL;
			subL->_parent = nullptr;
		}

		else
		{
			if (parentParent->_left == parent)//父结点是左孩子
			{
				parentParent->_left = subL;
			}

			else
			{
				//父结点是右孩子
				parentParent->_right = subL;
			}

			subL->_parent = parentParent;
		}

		parent->_parent = subL;

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

	}

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

		//根据没有旋转前subLR的平衡因子分情况讨论
		int bf = subLR->_bf;
		
		//先以subL为旋转点左旋
		RotateL(subL);
		//再以parent为旋转点右旋
		RotateR(parent);
		//每一个结点父结点已经更新，只需要修改平衡因子
		if (bf == -1)//插入在e子树
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 1;
		}
		else if (bf == 1)//插入在f子树
		{
			subLR->_bf = 0;
			subL->_bf = -1;
			parent->_bf = 0;
		}
		else if (bf == 0)//插入在b子树自己
		{
			subLR->_bf = 0;
			subL->_bf = 0;
			parent->_bf = 0;
		}

		else//其他情况，说明有问题
		{
			assert(false);
		}
	}

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

		//根据没有旋转前subRL的平衡因子分情况讨论
		int bf = subRL->_bf;

		//先以subR为旋转点右旋
		RotateR(subR);
		//再以parent为旋转点左旋
		RotateL(parent);
		//每一个结点父结点已经更新，只需要修改平衡因子

		if (bf == -1)//插入在e子树
		{
			subRL->_bf = 0;
			subR->_bf = 1;
			parent->_bf = 0;
		}
		else if (bf == 1)//插入在f子树
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = -1;
		}
		else if (bf == 0)//插入在b子树自己
		{
			subRL->_bf = 0;
			subR->_bf = 0;
			parent->_bf = 0;
		}

		else//其他情况，说明有问题
		{
			assert(false);
		}
	}
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-05-19，如有侵权请联系 cloudcommunity@tencent.com 删除

搜索