C++实现AVL树：理解旋转操作的每一个细节

watergraphically

865人浏览 · 2025-10-24 14:48:49

watergraphically · 2025-10-24 14:48:49 发布

认识 AVL 树

AVL 树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备以下性质的二叉搜索树：它的左右子树都是 AVL 树，且左右子树的高度差的绝对值不超过1。AVL树是一棵高度平衡搜索二叉树，通过控制高度差去控制平衡。为什么 AVL 树要求高度差不超过1，而不是高度差是0呢？？0不是更好的平衡吗？不是不想这样设计，而是有些情况是做不到高度差为0，并不是所有的树都是满二叉树，大部分的树都是完全二叉树。

为了方便的实现AVL树，我们在这里引入⼀个平衡因子(balancefactor)的概念，每个结点都有⼀个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL 树并不是必须要平衡因子，但是有了平衡因子可以更方便我们进行观察和控制树是否平衡，就像⼀个风向标⼀样。AVL 树整体结点数量和分布和完全⼆叉树类似，高度可以控制在 logN ，那么增删查改的效率也可以控制在 O(logN) ，相比二叉搜索树有了本质的提升。AVL 树的模型如下图所示：

每个结点的平衡因子的绝对值都小于等于1。

接下来展示 AVL 树的基本结构

template<class K, class V>
struct AVLTreeNode
{
	// 需要parent指针，方便更新平衡因子
	pair<K, V> _kv;
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	int _bf; // 平衡因子(balance factor) bf

	AVLTreeNode(const pair<K, V>& kv)
		: _kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

template<class K, class V>
class AVLTree
{
	typedef AVLTreeNode<K, V> Node;

private:
	Node* _root = nullptr;
};

AVL 树的插入

AVL 仍然遵循搜索树的规则，所以 AVL 的 insert 操作，也与二叉搜索树的 insert 操作一致，只不过AVL 树有自己的独特之处。AVL树的 insert 操作的基本框架：

// 插入
bool Insert(const pair<K, V>& kv)
{
	// 若树为空，则直接新增结点，赋值给root指针
	if (_root == nullptr)
	{
		_root = new Node(kv);

		return true;
	}
	// 若树不为空
	// 定义一个指针找空位置，插入新节点
	Node* cur = _root;
	// 定义一个指针，指向 cur 的父节点
	Node* parent = nullptr; // 初始值为空

	while (cur) // 找空位置，跳出循环说明找到空位置了
	{
		//插入值比当前结点大往右走
		if (kv.first > cur->_kv.first)
		{
			// 更新 parent 的指向
			parent = cur;
			cur = cur->_right;
		}
		//插入值比当前结点小往左⾛
		else if (kv.first < cur->_kv.first)
		{
			// 更新 parent 的指向
			parent = cur;
			cur = cur->_left;
		}
		// 插入值等于当前结点的值，返回false
		else
		{
			return false;
		}
	}

	// 跳出循环，说明cur当前为空，也表明找到了空位置
	cur = new Node(kv);
	// 链接 —— 需要判断链接在 parent 的左边还是右边
	if (kv.first > parent->_kv.first)
	{
		// 插入的值大于 parent 的值，链接在右边
		parent->_right = cur;
	}
	else if (kv.first < parent->_kv.first)
	{
		// 插入的值小于 parent 的值，链接在左边
		parent->_left = cur;
	}
	else
	{
		// 插入的值等于 parent 的值，返回 false
		return false;
	}

    // 更新结点parent指针的指向
    // 将新插入结点的parent指针指向它的父节点,即parent结点
    cur->_parent = parent;
}

平衡因子的更新

AVL 树与二叉搜索树的 insert 的实现有些不同，AVL树中最重要的步骤之一是更新平衡因子。

对于下图所示的AVL树：

现在插入一个key值为9的结点，如下图所示：

新插入结点可能会影响该结点的部分祖先的平衡因子，如：影响了9的父节点10的平衡因子，但是不影响10的父节点8的平衡因子。所以更新平衡因子，更新的就是新插入结点的部分祖先的平衡因子，这也是为什么 AVL 树的结构中定义了 parent 指针，就是方便寻找结点的父节点，检查是否需要更新平衡因子。插入结点，高度会增加/不变，对于上图插入结点9之后，其父节点的平衡因子更新，由-1变为0。

倘若插入一个 key 值为13的结点，如下图所示：

插入 key 值为13的结点之后，其父节点的平衡因子更新，由0变为-1。

由上述两种插入情况的结果可以发现：如果新插入的结点为父节点的左孩子，则父节点的平衡因子+1，如果新插入的结点为父节点的右孩子，则父节点的平衡因子-1。

平衡因子的更新规则

平衡因子的计算公式：平衡因子 = 右子树高度 - 左子树高度

注意：只有子树高度变化才会影响当前结点平衡因子

新增结点在 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 子树的高度，恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新，插入结束

• 不断更新，更新到根结点，就停止更新

代码实现：

// 更新平衡因子 --- 循环条件,结点parent不为空
while (parent)
{
	// 新增结点在parent的左子树，parent平衡因子 --
	if (cur == parent->_left)
	{
		parent->_bf--;
	}
	// 新增结点在parent的右子树，parent平衡因子 ++
	else
	{
		parent->_bf++;
	}

	// 判断是否需要继续向上更新
	// 1. 更新后 parent 的平衡因子等于0,结束更新
	if (parent->_bf == 0)
	{
		break;
	}
	// 2. 更新后 parent 的平衡因子等于1或-1,继续向上更新
	else if (parent->_bf == -1 || parent->_bf == 1)
	{
		cur = parent;
		parent = parent->_parent;
	}
	// 3. 更新后 parent 的平衡因子等于2或-2,旋转
	else if (parent->_bf == -2 || parent->_bf == 2)
	{
		// 旋转
	}
	// 4. 更新后 parent 的平衡因子为其它,说明上述的更新过程中存在错误
	else
	{
		assert(false);
	}
}

旋转

更新结点的平衡因子后，结点的平衡因子可能为2或-2，这时就需要执行旋转操作了，而旋转操作是 AVL 的重重点，它需要注意许多细节的处理，理解起来也更加的困难。

对于下图所示的树，简单的更新平衡因子不能使之满足 AVL 的规则，需要执行旋转操作

旋转的规则：

保持搜索树的规则

让旋转的树从不满足变平衡，其次降低旋转树的高度

旋转总共分为四种：左单旋/右单旋/左右双旋/右左双旋。

右单旋

右单旋：左边高，往右边旋转。

情况1：

情况2：

所有的情况都可以用下图抽象化表示，基本旋转步骤也与下图一致。

再泛化的表示成下图所示：

总结：什么情况需要右单旋？当 parent 结点的平衡因子为-2并且 cur 的平衡因子为-1时，需要右单旋。

将上图的步骤用代码实现：

// 右单旋 --- parent->_bf == -2 && cur->_bf == -1
if (parent->_bf == -2 && cur->_bf == -1)
{
    // 右单旋
    // 旋转点 parent
	RotateR(parent);
}


void RotateR(Node* parent)
{
	//        8
	//   3         h    
	// h   h+1    
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// subLR 变成parent的左子树
	parent->_left = subLR;
    // parent 变成subL的右子树
    subL->_right = parent;
}

右单旋的代码就这么简单的实现了吗？需要注意 AVL 树的结构中还有 parent 指针，旋转之后需要维护结点的 parent 指针的指向。改进后如下图所示：

// 右单旋 --- parent->_bf == -2 && cur->_bf == -1
if (parent->_bf == -2 && cur->_bf == -1)
{
    // 右单旋
    // 旋转点 parent
	RotateR(parent);
}


void RotateR(Node* parent)
{
	//        8
	//   3         h    
	// h   h+1    
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// subLR 变成parent的左子树
	parent->_left = subLR;
    // 更新结点的parent指针的指向
    // subLR 的父节点变成了 parent
    subLR->_parent = parent;
   
    // parent 变成subL的右子树
    subL->_right = parent;
    //更新结点的parent指针的指向
	// parent 的父节点变成了 subL
	parent->_parent = subL;
    
}

这样就完成了吗？还没有。需要注意 subLR 可能为空，如情况1，这样 subLR->parent 就涉及空指针的解引用问题。除此之外，还存在问题。

之前根结点为8，旋转之后根结点为3，不仅要动其它结点的 parent 指针的指向，也要动根结点3的parent 指针的指向；此外还需要考虑我们所旋转的树可能是某个树的局部子树。所以我们需要分两种情况讨论：1. 旋转的树不是局部子树，也就是8的 parent 指针指向空；2. 旋转的树是局部子树，也就是8的 parent 指针不指向空。

最终代码实现：

// 右单旋 --- parent->_bf == -2 && cur->_bf == -1
if (parent->_bf == -2 && cur->_bf == -1)
{
    // 右单旋
    // 旋转点 parent
	RotateR(parent);
}

// 右单旋
void RotateR(Node* parent)
{
	//        8
	//   3         h    
	// h   h+1    
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// subLR 变成parent的左子树
	parent->_left = subLR;
	// 更新结点的parent指针的指向
	// subLR 的父节点变成了 parent
	if (subLR != nullptr)
	{
		subLR->_parent = parent;
	}

	// 记录当前根结点的父节点
	Node* parentParent = parent->_parent;
	// parent 变成subL的右子树
	subL->_right = parent;
	// 在更新根结点之前，更新结点的parent指针的指向
	// parent 的父节点变成了 subL
	parent->_parent = subL;
    
    // 更新根结点
	// 在更新根结点之前,如果 parent 为 _root,即parentParent等于空
	if (parentParent == nullptr)
	{
		_root = subL;
		// 根结点的parent指针置为空
		subL->_parent = nullptr;
	}
	// 在更新根结点之前,如果 parent 不为 _root,即parentParent不为空
	// 表明我们旋转的树是局部子树
	// 这时又需要分情况讨论，这个子树是左子树还是右子树
	else
	{
		// 左子树
		if (parentParent->_left == parent)
		{
			// parentParent的左子树的根结点更新了
			// 更新parentParent的左指针指向
			parentParent->_left = subL;
		}
		// 右子树
		else
		{
			// parentParent的右子树的根结点更新了
			// 更新parentParent的右指针指向
			parentParent->_right = subL;
		}

		// 更新子树根结点的parent指针的指向
		subL->_parent = parentParent;
	}

	// 旋转之后，还需更新subL和parent结点的平衡因子
	// 它们的平衡因子都变成了0，上图展示过
	subL->_bf = parent->_bf = 0;
}

左单旋

左单旋：右边高，往左边旋转。

所有的情况都可以用下图抽象化表示，基本旋转步骤也与下图一致

总结：什么情况需要左单旋？当 parent 结点的平衡因子等于2并且 cur 的平衡因子等于1时，需要左单旋。

左单旋的基本细节处理与右单旋类似。最终代码实现如下图所示：

// 左单旋 --- parent->_bf == 2 && cur->_bf == 1
else if (parent->_bf == 2 && cur->_bf == 1)
{
	// 左单旋
	// 旋转点parent
	RotateL(parent);
}

// 左单旋
void RotateL(Node* parent)
{
	//      8
	//  h        10
	//        h      h+1
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// subRL 变成parent的右子树
	parent->_right = subRL;
	// 更新subRL的parent指针的指向
	if (subRL != nullptr)
	{
		subRL->_parent = parent;
	}
	// 在更新根结点之前，记录根结点的父节点
	Node* parentParent = parent->_parent;
	// parent变成subR的左子树
	subR->_left = parent;
	// 更新parent的parent指针的指向
	parent->_parent = subR;

	// 在更新根结点之前,如果 parent 为 _root,即parentParent为空
	// 更新根结点
	if (parentParent == nullptr)
	{
		_root = subR;
		// 根结点的parent指针置为空
		subR->_parent = nullptr;
	}
	// 在更新根结点之前,如果 parent 不为 _root,即parentParent不为空
	// 表明我们旋转的树是局部子树
	// 这时又需要分情况讨论，这个子树是左子树还是右子树
	else
	{
		// 左子树
		if (parentParent->_left == parent)
		{
			// parentParent的左子树的根结点更新了
			// 更新parentParent的左指针指向
			parentParent->_left = subRL;
		}
		// 右子树
		else
		{
			// parentParent的右子树的根结点更新了
			// 更新parentParent的右指针指向
			parentParent->_right = subR;
		}

		// 更新子树根结点的parent指针的指向
		subR->_parent = parentParent;
	}

	// 旋转之后，还需更新subR和parent结点的平衡因子
	// 它们的平衡因子都变成了0，上图展示过
	subR->_bf = parent->_bf = 0;
}

左右双旋

单旋都是纯粹的一边高，对于所有结点要么左边高，要么右边高。但是还可能是下面这种情况：

对于结点3来说，是右边高；对于结点8来说是左边高。对于上面这种情况单旋是无法解决的，这时就需要双旋了。

情况1：

情况2：

情况3：

不管是插入 d 子树还是 e 子树，左右双旋的步骤都是一致的，但是3和8最终的平衡因子是有区别的。由于插入 d 子树还是插入 e 子树会影响最终结点的平衡因子，所以需要判断到底是插入 d 子树还是插入 e 子树，如何判断？根据插入结点后，subLR 的平衡因子来判断：若 subLR 的平衡因子为0，说明是情况1；若 subLR 的平衡因子为-1，则插入的是 d 子树；若 subLR 的平衡因子为1，则插入的是 e 子树。

总结：什么情况需要左右双旋？当 parent 结点的平衡因子等于-2并且 cur 结点的平衡因子等于1时，需要左右双旋。

最终代码实现：

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

// 左右双旋
void RotateLR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;

	// 插入子树的不同会改变最终结点的平衡因子,但是可以通过subLR的平衡因子进行判断
	// 然而单旋会改变结点的平衡因子,所以需要提前存储结点的 subLR 平衡因子
	int bf = subLR->_bf;
	// 左单旋
	// 旋转点subL
	RotateL(subL);

	// 右单旋
	// 旋转点parent
	RotateR(parent);

	// 如果subLR原来的平衡因子为0，说明满足情况1
	if (bf == 0)
	{
		// 平衡因子均为0
		parent->_bf = 0;
		subL->_bf = 0;
		subLR->_bf = 0;
	}
	// 如果subLR原来的平衡因子为-1，说明插入的是d子树
	else if (bf == -1)
	{
		// parent 的平衡因子最终为1
		parent->_bf = 1;
		// subL 的平衡因子最终为0
		subL->_bf = 0;
		// subLR 的最终平衡因子为0
		subLR->_bf = 0;
	}
	// 如果subLR原来的平衡因子为1，说明插入的是e子树
	else if(bf == 1)
	{
		// parent 的平衡因子最终为0
		parent->_bf = 0;
		// subL 的最终平衡因子为-1
		subL->_bf = -1;
		// subLR 的最终平衡因子为0
		subLR->_bf = 0;
	}
	// 如果subLR原来的平衡因子为其它，说明存在错误
	else
	{
		assert(false);
	}
}

右左双旋

右左双旋的基本细节处理与左右双旋的类似，可以分成以下三种情况：

情况1：

情况2：

情况3：

总结：什么情况需要右左双旋？当 parent 结点的平衡因子等于2并且 cur 结点的平衡因子等于-1时，需要右左双旋。

最终代码实现：

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

// 右左单旋
void RotateRL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;

	// 插入子树的不同会改变最终结点的平衡因子,但是可以通过 subRL 的平衡因子进行判断
	// 然而单旋会改变结点的平衡因子,所以需要提前存储结点的 subRL 平衡因子
	int bf = subRL->_bf;
	// 右单旋
	// 旋转点subR
	RotateR(subR);

	// 左单旋
	// 旋转点parent
	RotateL(parent);

	// 如果subLR原来的平衡因子为0，说明满足我所说的特殊情况
	if (bf == 0)
	{
		// 平衡因子均为0
		parent->_bf = 0;
		subR->_bf = 0;
		subRL->_bf = 0;
	}
	// 如果subRL原来的平衡因子为-1，说明插入的是d子树
	else if (bf == -1)
	{
		// parent 的平衡因子最终为0
		parent->_bf = 0;
		// subR 的平衡因子最终为1
		subR->_bf = 1;
		// subRL 的最终平衡因子为0
		subRL->_bf = 0;
	}
	// 如果subRL原来的平衡因子为1，说明插入的是e子树
	else if (bf == 1)
	{
		// parent 的平衡因子最终为-1
		parent->_bf = -1;
		// subR 的最终平衡因子为0
		subR->_bf = 0;
		// subRL 的最终平衡因子为0
		subRL->_bf = 0;
	}
	// 如果subRL原来的平衡因子为其它，说明存在错误
	else
	{
		assert(false);
	}
}

检查 AVL 树是否平衡

插入结点后，更新结点的平衡因子，旋转之后，最终还要检查 AVL 树是否平衡。如何判断AVL树已经平衡？不能通过平衡因子的绝对值是否小于2来判断树已经平衡，为什么？因为有可能平衡因子更新错误，有可能平衡因子是对的，但是树不是AVL树。那如何判断AVL树平衡，通过左右子树的高度差的绝对值是否小于大于等于2。

最终代码实现：

// 获取树的高度
int _Height(Node* root)
{
	if (root == nullptr)
	{
		return 0;
	}

	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

// 检查AVL树是否平衡
bool _IsBalanceTree(Node* root)
{
	// 空树也是AVL树
	if (nullptr == root)
			return true;
	// 计算root结点的平衡因子：即root左右子树的高度差
	int leftHeight = _Height(root->_left);
	int rightHeight = _Height(root->_right);
	int diff = rightHeight - leftHeight;

	// 如果计算出的平衡因子与root的平衡因子不相等
	// 或者 root 平衡因子的绝对值超过1，则一定不是AVL树
	if (abs(diff) >= 2)
	{
		cout << root->_kv.first << "高度差异常" << endl;
		return false;
	}
	if (root->_bf != diff)
	{
		cout << root->_kv.first << "平衡因子异常" << endl;
		return false;
	}
	// 如果root的左和右都是AVL树，则该树一定是AVL树
	return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

它的处理与二叉搜索树中的中序遍历处理一致，设置成私有，在类中再实现一个子函数，子函数中调用主函数。