【C++】你的二叉搜索树为什么慢？因为你还没解锁“平衡”的力量--AVL树核心详解

小陈又菜

发布于 2025-12-24 11:06:39

1680

上一篇文章中我们介绍了二叉搜索树，我们讲到，在不良的插入顺序下，二叉搜索树会退化为单支树，将会丧失查找的优良性能。所以我们希望通过一种插入规则（又将其称为平衡规则），来降低二叉搜索树的高度，使得二叉搜索树趋近于一个完美二叉树（如下图），从而提高二叉搜索树的性能，今天我们就介绍AVL树。

1. AVL树

1.1. AVL树的概念

像我们上面提到的，当我们插入数据有序或者接近有序时，二叉搜索树就会退化成单支树，此时查找元素的效率相当于从顺序表中查找，效率较低。因此，两位俄罗斯数学家G.M.Adelson-Velski和E.M.Landis 在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新节点后，如果能保证每个节点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一颗AVL树有下面的性质：

它的左右子树都是AVL树
左右子树的高度之差（简称平衡因子）的绝对值不超过1(1/0/-1)

通过这样的平衡规则，使得二叉搜索树高度平衡，那么此时如果它有n个节点，其高度可保持在O(log N)，搜索时间复杂度为O(logN)。

2. AVL树节点的定义

我们这里实现K-V模型的AVL树，K模型的比较简单，大家可以自己实现：

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; // balance factor 
 
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
 
	// AVL树并没有规定必须要设计平衡因子
	// 只是一个实现的选择，方便控制平衡
};

从节点的定义我们可以看出，有普通的二叉搜树不同的是，AVL树中节点的设置添加了节点的parent节点，此处也是为了方便后续功能的实现（接着往下看就明白了）。除此之外，节点也定义了一个控制平衡因子_bf，用来表示当前节点右子树与左子树的高度差。

3. AVL树的插入和旋转

AVL树的插入过程可以分为两步：

按照二叉搜索树的方式插入新节点
调整节点的平衡因子

AVL树在插入的过程中，如果插入新节点后导致AVL树中某些节点的平衡因子的绝对值大于等于1时，要进行旋转操作，根据节点插入位置的不同，AVL树的旋转分为四种。接下来我们逐一分析可能出现的情况与解决该问题的旋转方法。

3.1. 左单旋

什么时候需要进行左单旋？当新节点插入在高度较高的右子树的右侧时，我们先看一个比较简单的情况，如下图我们要插入90，此时根节点的平衡因子会变成2，不满足AVL树的规则，所以我们应该进行旋转。

下面这种情况就是，新结点插在较高右子树的右侧，因此需要进行左单旋。

左单旋步骤如下：

让插入节点的父节点，也就是这里的60的左子树变成节点30的右子树，30这颗子树成为60的左子树。
调整改变节点的平衡因子。

然后我们来看更复杂的情况，在下图中，无论在b还是c树下插入新节点，都是在30的右树下插入新节点，因此这里将有4中可能性（分别是b的左右孩子，c的左右孩子处），这里以c的孩子为例。但是情况均为左单旋情况。

左单旋步骤如下：

将60的左树变为30的右树
再让30成为60的左树
最后更改旋转因子

这里我们还需要考虑一些特殊情况：

60可能存在右子树也可能不存在。
30可能是根节点，也可能是子树，如果是根节点，那我需要更新根节点，如果是是子树，要考虑是左子树还是右子树。

代码实现左单旋：

void RotateL(Node* parent)
	{
		//左旋
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subR->_left = parent;
		parent->_parent = subR;
 
		if (parent == _root)
		{
			_root = subR;
			_root->_parent = nullptr;
		}
		else
		{
			if (parent == ppNode->_left)
			{
				ppNode->_left = subR;
			}
			else
			{
				ppNode->_right = subR;
			}
 
			subR->_parent = ppNode;
		}
 
		//更新平衡因子
		parent->_bf = 0;
		subR->_bf = 0;
	}

这个地方可以比较形象地解释一下代码，我们抽离出原型：

旋转前：     
     parent
    /     \
   A      subR
          /   \
       subRL   C

旋转后：
      subR
     /    \
  parent   C
  /   \
 A   subRL

特殊的情况，parent不是根节点：

旋转前：
      ppNode
      /    \
  parent    D     ← parent是ppNode的左孩子
   /   \
  A    subR
       /   \
    subRL   C

旋转后：
      ppNode  
      /    \
    subR    D     ← subR接替parent的位置
    /   \
 parent  C
  /   \
 A   subRL

------------------------------------------

旋转前：
      ppNode
      /    \
     D    parent   ← parent是ppNode的右孩子
          /   \
        subR   A
        /   \
       B   subRL

旋转后：
      ppNode
      /    \
     D    subR    ← subR接替parent的位置
          /   \
        parent  A
        /   \
       B   subRL

3.2. 右单旋

右单旋的情况与左单旋的情况正好相反，当节点插入到更高左子树的左侧时，需要右单旋。

我们先举一个最简单的例子，在下图中，我们需要插入节点10，这导致60（根节点）的平衡因子不满足AVL树规则，那我们要想重新平衡，就需要将60的左子树较少一层即可，右子树增加一层，即将左子树提上来即可。

右单旋步骤：

将30的右子树变成60的左子树
再让60变成30的左子树
最后更新节点的平衡因子

我们再来讨论一下较为复杂的情况：

同样我们需要考虑一些特殊的情况：

30可能不存在右子树
60可能是根节点，也可能不是，如果不是，就可能是右子树，也可能是左子树

代码实现右单旋：

void RotateR(Node* parent)
	{
		//右旋
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
 
		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;
 
		Node* ppNode = parent->_parent;
 
		subL->_right = parent;
		parent->_parent = subL;
 
		if (parent == _root)
		{
			_root = subL;
			_root->_parent = nullptr;
		}
		else
		{
			if (ppNode->_left == parent)
			{
				ppNode->_left = subL;
			}
			else
			{
				ppNode->_right = subL;
			}
			subL->_parent = ppNode;
		}
 
		subL->_bf = parent->_bf = 0;
	}

3.3. 先左单旋再右单旋

当新节点插入在较高左子树的右侧，就需要发生左右旋。

我们用图的形式直观地展示一下：

代码实现左右双旋：

//左右双旋
	void RotateLR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;
 
		int bf = subLR->_bf;
		RotateL(parent->_left);//左
		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
		{
			// subLR->_bf 旋转前就出现问题
			assert(false);
		}
	}

3.4. 先右单旋在左单旋

当新节点插入较高右子树的左侧时就要进行右左单旋。我们直接来看具体情况

将右左双旋变成单旋再旋转，即对90进行右单旋再对30进行左单旋，旋转完再考虑平衡因子的更新。

代码实现右左双旋：

//右左双旋
	void RotateRL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;
		int bf = subRL->_bf;
 
		RotateR(parent->_right);
		RotateL(parent);
 
		if (bf == 0)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 0;
		}
		else if (bf == 1)
		{
			subRL->_bf = 0;
			parent->_bf = -1;
			subR->_bf = 0;
		}
		else if(bf == -1)
		{
			subRL->_bf = 0;
			parent->_bf = 0;
			subR->_bf = 1;
		}
		else
		{
			// subLR->_bf 旋转前就有问题
			assert(false);
		}
	}

AVL树的旋转共以上四种情况。

总结：

加入pParent为根的子树不平衡时，即pParent的平衡因子为2或者-2，分以下情况考虑：

pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根伟pSubR
- 当pSubR的平衡因子为1时，执行左单旋
- 当pSubR的平衡因子为-1时，执行右左双旋转
pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的跟为pSubL
- 当pSubL的平衡因子为-1时，执行右单旋
- 当pSubL的平衡因子为1是，执行左右双旋

旋转完成后，原pParent为跟的子树的高度降低，已经平衡，不需要再向上更新了。

考虑完所有的旋转情况后，我们此时实现insert插入。

insert插入大框架还是二叉搜索树的insert,只不过加入了平衡因子，不平衡时进行旋转。

4. AVL树insert实现代码

bool Insert(const pair<K, V>& kv)
	{
		//1、按照搜索树的规则插入
		//2、看是否违反平衡规则，如果违反就需要处理：旋转
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_bf = 0;
			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->_right)
			{
				parent->_bf++;
			}
			else
			{
				parent->_bf--;
			}
 
			//是否继续更新？
			// 1 or -1  ->插入节点填上了矮的那边
			if (parent->_bf == 0)
			{
				break;
			}
			//0->1 或者 -1 插入节点导致一边变高了
			else if (parent->_bf == 1 || parent->_bf == -1)
			{
				//子树的高度变了，继续更新祖先
				cur = cur->_parent;
				parent = parent->_parent;
			}
			// -1 or 1 -》 2 or -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);
				}
				else if (parent->_bf == -2 && cur->_bf == -1)//左右双旋
				{
					RotateLR(parent);
				}
				else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋
				{
					RotateRL(parent);
				}
				break;
			}
			else
			{
				//插入之前AVL树就存在不平衡子树
				assert(false);
			}
		}
		return true;
	}

5. 判断一棵树是否是AVL树

由于AVL是在二叉搜索树的基础上加入了平衡机制，因此验证AVL树可以分为两步：

首先验证其是否为二叉搜索树：如果中序遍历可得到一个有序的序列，就说明是二叉搜索树
验证其是否为平衡树（把握AVL树的规则）：
1. 每个节点子树高度差的绝对值不超过1（注意节点如果没有平衡因子）
2. 节点的平衡因子是否计算正确
3. 每个AVL树的左右子树也为AVL树，因此可以使用递归判断其左右子树是否为AVL树

代码实现：

void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;
		_InOrder(root->_left);
		cout << root->_kv.first << " ";
		_InOrder(root->_right);
	}
 
	int _Height(Node* root)
	{
		if (root == nullptr)
			return 0;
		int lh = _Height(root->_left);
		int rh = _Height(root->_right);
 
		return lh > rh ? lh + 1 : rh + 1;
	}
 
	//是否是平衡树
	bool _IsBalanceTree(Node* root)
	{
		// 空树也是AVL树
		if (nullptr == root)
			return true;
 
		// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		int diff = rightHeight - leftHeight;
 
		// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
		// pRoot平衡因子的绝对值超过1，则一定不是AVL树
		if (abs(diff) >= 2)
		{
			cout << root->_kv.first << "节点平衡因子异常" << endl;
			return false;
		}
 
		if (diff != root->_bf)
		{
			cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
			return false;
		}
 
		// pRoot的左和右如果都是AVL树，则该树一定是AVL树
		return _IsBalanceTree(root->_left)
			&& _IsBalanceTree(root->_right);
	}

6. AVL树的验证与查看

我们通过层序遍历的方式来查看AVL树，层序遍历我们使用到队列：

//层序输出
	vector<vector<int>> levelOrder() {
		vector<vector<int>> vv;
		if (_root == nullptr)
			return vv;
 
		queue<Node*> q;
		int levelSize = 1;
		q.push(_root);
 
		while (!q.empty())
		{
			// levelSize控制一层一层出
			vector<int> levelV;
			while (levelSize--)
			{
				Node* front = q.front();
				q.pop();
				levelV.push_back(front->_kv.first);
				if (front->_left)
					q.push(front->_left);
 
				if (front->_right)
					q.push(front->_right);
			}
			vv.push_back(levelV);
			for (auto e : levelV)
			{
				cout << e << " ";
			}
			cout << endl;
 
			// 上一层出完，下一层就都进队列
			levelSize = q.size();
		}
 
		return vv;
	}

我们来试着手动插入一些数据来看一下程序是否正确：

6.1. 顺序插入

void TestAVLTree2()
{
	const size_t N = 10;
	vector<int> v;
	v.reserve(N);
	srand(time(0));//生成随机树
	for (size_t i = 0; i < N; ++i)
	{
		//v.push_back(rand());
		v.push_back(i);
	}
 
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}
 
	t.levelOrder();
	cout << endl;
	cout << "是否平衡?" << t.IsBalanceTree() << endl;
	cout << "高度:" << t.Height() << endl;
 
 
	//t.InOrder();
}

运行结果：

6.2. 随机值插入

void TestAVLTree2()
{
	const size_t N = 10;
	vector<int> v;
	v.reserve(N);
	srand(time(0));//生成随机树
	for (size_t i = 0; i < N; ++i)
	{
		v.push_back(rand());
		
	}

	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
	}

	t.levelOrder();
	cout << endl;
	cout << "是否平衡?" << t.IsBalanceTree() << endl;
	cout << "高度:" << t.Height() << endl;


	//t.InOrder();
}

运行结果：

7. AVL树的性能

AVL树是一颗绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O（log N）。但是如果要对AVL树做一些结构修改的操作，性能非常低下。比如：插入是要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，可能要一直让旋转持续到根。这也是为什么本篇没有分析AVL的删除。

总地来说，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会变），可以考虑AVL树，但如果要经常修改，就不适合使用AVL树。

（本篇完）

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

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

root