当前位置： 首页 > article >正文

从失衡到平衡：手撕 AVL 树的插入旋转操作

article 2025/3/26 7:29:49

目录

0.写在前面

1.AVL树的历史起源

1. 严格的自平衡机制

2. 高效的操作性能

2.AVL树的模拟实现

Step 1：Tree结点的构造 

Step 2：构造AVLTree类 

 Step 3: 完成插入函数 

Step 4: 刨析旋转 

左单旋：

右单旋：

左右双旋：

​编辑

右左双旋：

Step 5：检查AVL树

InOrder：

Height：

IsBalance：

Step 6：测试AVL树

3.AVL树的优缺点

一、AVL 树的优点

1. 严格的平衡性

2. 稳定的性能下限

二、AVL 树的缺点

1. 高维护成本

2. 存储开销

3. 实现复杂度高

0.写在前面

      AVL树是数据结构中久负盛名的平衡二叉搜索二叉树，前面已经介绍了BInary Search Tree二叉搜索树的实现，但是由于BST不一定平衡，有可能出现O(N)量级的高度，今天来介绍一下BST的强化版——平衡的BST——AVL，如果没听过这棵树的读者可以了解一下背景：

1.AVL树的历史起源

一、AVL 树的历史背景

  1. 起源
    AVL 树由苏联数学家 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年 在论文《An algorithm for the organization of information》中首次提出，旨在解决普通二叉搜索树（BST）在动态操作（插入、删除）中退化为链表的问题。

  2. 命名由来
    AVL 树名称取自两位发明者姓氏的首字母，是计算机科学中    最早的自平衡二叉搜索树结构之一，其核心思想是通过动态调整树的结构，保持高度平衡，从而保证操作的高效性。

二、AVL 树的强大功能与核心优势

1. 严格的自平衡机制
  • 平衡因子：每个节点的平衡因子定义为左子树高度 - 右子树高度，AVL 树要求所有节点的平衡因子绝对值不超过1。
  • 动态调整：插入或删除节点后，若失衡（平衡因子绝对值≥2），通过旋转操作（单旋或双旋）恢复平衡，确保树的高度始终为O（logn)。
  • 四种旋转策略：LL 型（右旋）、RR 型（左旋）、LR 型（先左后右）、RL 型（先右后左）。
2. 高效的操作性能
  • 时间复杂度：所有操作（查找、插入、删除）的时间复杂度严格稳定在 O(log n)，优于普通 BST 的最坏情况 O (n)。
  • 应用场景优势：数据库索引：快速定位数据，支持高并发查询。文件系统：高效管理目录结构，加速文件检索。内存管理：动态分配与回收内存块，避免碎片化。路由表与网络协议：快速匹配 IP 地址，提升网络吞吐量。事件调度系统：精准管理定时任务，如操作系统进程调度。

2.AVL树的模拟实现

        由于AVL树的插入和删除都涉及到大量复杂的旋转，由于篇幅有限，本篇重点介绍的是AVL树的插入：并且规定平衡因子的计算是右子树的高度-左子树的高度。

Step 1：Tree结点的构造 

思路：

---1--- 先来想想如何存储结点，如果我们使用堆那样的数组是否合适？当然不合适，因为涉及到下标访问的问题，那么还剩下链式结构可以供我们选择了。

---2--- 构造AVLTreeNode当然是要方便类外直接进行访问的，因此用struct来构造，来想想一个结点要存储什么？

---3--- 在结点中存储left地址，right地址，还有parent地址，这是典型的三叉链表的特征，以及当前结点的pair，pair可以是多种类型的，因此需要进行泛型编程，运用模板template，这里也可以只储存Key，我们干脆麻烦一点，储存键值对，pair<Key,Value>。

---4--- 最后要写一个构造函数，因为在创造结点的时候可能会用到，记得将left，right置为nullptr哦~

template<class K, class V>
struct AVLTreeNode
{
	AVLTreeNode<K, V>* _left;
	AVLTreeNode<K, V>* _right;
	AVLTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	int _bf;

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

补充：欸，其实还没有介绍完，对了！这里漏掉了平衡因子，Balance Factor是AVL能保持绝对平衡必不可少的因素，后面的旋转操作需要大量依赖_bf！

Step 2：构造AVLTree类 

 思路：

---1--- 为了表示AVLTreeNode方便一些，在类中typedef一下以便我们来表示。

---2--- 这里的成员变量只需要_root就足够了，存储根结点

---3--- 下面给出AVLTree类的大致框架:

​
template<class K, class V>
class AVLTree
{
public:
	typedef AVLTreeNode<K, V> Node;
	AVLTree()
		:_root(nullptr)
	{
	}

	/...

	Node* _root;
};

​

 Step 3: 完成插入函数 

思路：

---1--- 简单来说，前面的步骤与BST二叉搜索树的插入步骤大相径庭，通过每个节点的值进行比较来确定新的节点要插入的位置。(注意这里存储的是键值对，pair要按照pair.first来作为key进行比较）

---2--- 当cur在往下走之前要记得保存上一结点的位置，方便后面的调整，在找到nullptr时来进行插入，请注意如果根节点为空时，将新插入的结点作为根节点

---3--- 下面进行平衡因子的调整和旋转：！！！重要

首先需要了解这样的几点规则：

  • //1.新增在左，prev平衡因子--
  • //2.新增在右，prev平衡因子++
  • //3.更新后prev平衡因子==0，说明prev所在的子树高度不变，不会再影响祖先，不用再继续沿着到root的路径往上更新
  • //4.更新后prev平衡因子==1/-1，说明prev所在的子树的高度变化，会影响祖先，需要继续沿着到root的路径更新
  • /5.更新后prev平衡因子==2/-2，说明prev所在的子树高度变化并且不平衡，对parent所在子树进行旋转调整
  • //6.如果更新到根节点，插入结束

很明显，这是个循环操作，那么就将循环条件设置为prev不为nullptr，调整_bf是否++/--，之后如果_bf==0，说明已经达到平衡，无需往后调整，如果==1/-1，说明处于半平衡需要将prev给newnode，继续向上更新，如果_bf已经==2/-2，那么就需要进行旋转了:

  1. 如果prev->_bf == 2 && newnode->_bf == 1，说明插入的节点在右子树的右子树，进行左单旋
  2. 如果prev->_bf == -2 && newnode->_bf == -1，说明插入的节点在左子树的左子树，进行右单旋
  3. 如果prev->_bf == 2 && newnode->_bf == -1，说明插入的节点在右子树的左子树，进行右左双旋
  4. 如果prev->_bf == -2 && newnode->_bf == 1，说明插入的节点在右子树的左子树，进行左右双旋
bool Insert(const pair<K, V>& kv)
{
	//建议还是采用非递归的写法，不要使用递归或者指针引用，一方面是防止栈溢出
	//stack overflow warning!一方面是锻炼代码能力
	Node* cur = _root;
	Node* prev = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			prev = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			prev = cur;
			cur = cur->_right;
		}
		else
		{
			return false;
		}
	}
	Node* newnode = new Node(kv);
	if (_root == nullptr)
	{
		_root = newnode;
		return true;
	}
	if (kv.first > prev->_kv.first)
	{
		prev->_right = newnode;
	}
	else
	{
		prev->_left = newnode;
	}
	newnode->_parent = prev;
	//插入完成后要调整父亲的平衡因子
	//要满足以下规则：
	//1.新增在左，parent平衡因子--
	//2.新增在右，parent平衡因子++
	//3.更新后parent平衡因子==0，说明parent所在的子树高度不变，不会再影响祖先，不用再继续沿着到root的路径往上更新
	//4.更新后parent平衡因子==1/-1，说明parent所在的子树的高度变化，会影响祖先，需要继续沿着到root的路径更新
	//5.更新后parent平衡因子==2/-2，说明parent所在的子树高度变化并且不平衡，对parent所在子树进行旋转调整
	//6.如果更新到根节点，插入结束
	while (prev)
	{
		if (prev->_left == newnode)
		{
			prev->_bf--;
		}
		else
		{
			prev->_bf++;
		}

		if (prev->_bf == 0)
		{
			//更新结束
			break;
		}
		else if (prev->_bf == 1 || prev->_bf == -1)
		{
			//继续向上更新
			newnode = prev;
			prev = prev->_parent;
		}
		else if (prev->_bf == 2 || prev->_bf == -2)
		{
			//不平衡的AVL，需要旋转
			//旋转需要注意的问题：
			//1.旋转的同时还要满足是搜索树
			//2.变成平衡树且降低这个子树的高度
			//3.变成平衡树后就无需向上更新了，旋转后根节点的平衡因子为0
			//旋转调整分为四种情况：
			//1.左单旋
			//2.右单旋
			//3.左右双旋
			//4.右左双旋
			//如果是左单旋，需要判断插入的节点是否位于右子树的右子树
			//如果位于右子树的左子树，需要先对右子树进行右单旋，再对根节点进行左单旋，也就是右左双旋
			//如果是右单旋，需要判断插入的节点是否位于左子树的左子树
			//如果位于左子树的右子树，需要先对左子树进行左单旋，再对根节点进行右单旋，也就是左右双旋
			//代码：
			if (prev->_bf == 2 && newnode->_bf == 1)
			{
				//说明插入的节点在右子树的右子树
				//进行左单旋
				RotateL(prev);
			}
			else if (prev->_bf == -2 && newnode->_bf == -1)
			{
				//说明插入的节点在左子树的左子树
				//进行右单旋
				RotateR(prev);
			}
			else if (prev->_bf == 2 && newnode->_bf == -1)
			{
				//说明插入的节点在右子树的左子树
				//进行右左双旋
				RotateRL(prev);
			}
			else
			{
				//最后一种情况，说明插入的节点在左子树的右子树
				//进行左右双旋转；
				RotateLR(prev);
			}
			//注意这里旋转完成后，平衡因子满足-1/0/1，不需要再向上更新
			break;
		}
		else
		{
			assert(false);//用来调试的，如果出现这种情况，说明代码有问题
			//插入之前AVL就出现了问题
		}
	}
	return true;
}

Step 4: 刨析旋转 

左单旋：

思路：

---1--- 如图，在插入了新节点后，prev->_bf变为2，newnode->_bf变为1，说明新节点插入在了根节点的右子树的右子树，很明显右子树比左子树高2

---2--- 那么此时就需要将左子树向下按1，让两边的子树保持平衡，将root设置为parent，parent->_right设置为cur，cur->_left设置为curleft，这时需要将curleft连接在parent->_right，将parent连接到cur->_left上

---3--- 接下来要对一些细节进行处理，如果parent为根节点，那么旋转后需要更新根节点

---4--- 如果curleft不存在，就不需要更改curleft的父亲了，否则需要更改

---5--- 别忘记了对parent，cur，curleft的父亲进行更改，对parent需要将其parent提前保存在ppnode中，对于cur，别忘记在最后更改其父亲结点，否则在调试时需要花费大量时间！

---6--- 更新平衡因子：在旋转过后，curleft的平衡因子不变，parent和cur的平衡因子都变为0，保持了AVL的平衡

//左单旋
void RotateL(Node* parent)
{
	Node* cur = parent->_right;
	Node* curleft = cur->_left;
	Node* ppnode = parent->_parent;
	parent->_right = curleft;
	cur->_left = parent;
	//这里curleft有可能是不存在的，那么需要特殊判断一下
	if (curleft)
	{
		curleft->_parent = parent;

	}
	//parent有可能为根结点，根节点需要改变，判断一下
	cur->_parent = ppnode;
	if (parent == _root)
	{
		_root = cur;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
	}
	parent->_parent = cur;
	cur->_bf=0;
	parent->_bf=0;
}

右单旋：

思路：（与左单旋仅仅只有部分不同）

---1--- 如图，在插入了新节点后，prev->_bf变为-2，newnode->_bf变为-1，说明新节点插入在了根节点的左子树的左子树，很明显左子树比右子树高2

---2--- 那么此时就需要将左子树向下按1，让两边的子树保持平衡，将root设置为parent，parent->_left设置为cur，cur->_right设置为curright，这时需要将curright连接在parent->_left，将parent连接到cur->_right上

---3--- 接下来要对一些细节进行处理，如果parent为根节点，那么旋转后需要更新根节点

---4--- 如果curright不存在，就不需要更改curright的父亲了，否则需要更改

---5--- 别忘记了对parent，cur，curleft的父亲进行更改，对parent需要将其parent提前保存在ppnode中，对于cur，别忘记在最后更改其父亲结点，否则在调试时需要花费大量时间！

---6--- 更新平衡因子：在旋转过后，curleft的平衡因子不变，parent和cur的平衡因子都变为0，保持了AVL的平衡

//右单旋
void RotateR(Node* parent)
{
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	Node* ppnode = parent->_parent;
	parent->_left = curright;
	cur->_right = parent;
	//这里curleft有可能是不存在的，那么需要特殊判断一下
	if (curright)
	{
		curright->_parent = parent;

	}
	//parent有可能为根结点，根节点需要改变，判断一下
	cur->_parent = ppnode;
	if (parent == _root)
	{
		_root = cur;
	}
	else
	{
		if (ppnode->_left == parent)
		{
			ppnode->_left = cur;
		}
		else
		{
			ppnode->_right = cur;
		}
	}
	parent->_parent = cur;
	cur->_bf=0;
	parent->_bf=0;
	//其实这里cur和parent的_bf一定为0了
}

左右双旋：

思路：

---1--- 对于左右双旋，触发条件是prev->_bf == -2 && newnode->_bf == 1，插入的节点在右子树的左子树 ，那么需要先以parent->_left作为根节点进行左单旋，再以parent为根节点进行右单旋,

---2--- 旋转过程复用单旋就行了，麻烦的是这里的平衡因子更新，我们对curright的_bf平衡因子进行讨论，共需要分为三种情况：

  1. 如果_bf==0，那么说明插入的结点就是curright，那么最后旋转过后parent，cur，curright的平衡因子都更新为0，达到彻底平衡
  2. 如果_bf==1，说明插入的结点在curright的右边，那么旋转过后cur->_bf = -1;
    parent->_bf = 0，curright->_bf = 0
  3. 如果_bf==-1，说明插入的结点在curright的左边，那么旋转过后cur->_bf = 0;
    parent->_bf = 1，curright->_bf = 0
//左右双旋
void RotateLR(Node* parent)
{
	//这里要更新平衡因子，分为三种情况
	//1.插入在左子树的右子树第一个，此前没有右子树
	//2.插入在左子树的右子树的右子树
	//3.插入在左子树的右子树的左子树
	Node* cur = parent->_left;
	Node* curright = cur->_right;
	int _bf = curright->_bf;
	RotateL(parent->_left);
	RotateR(parent);
	if (_bf == 0)
	{
		
		//最后curright，cur，parent的平衡因子都为0
		cur->_bf = 0;
		parent->_bf = 0;
		curright->_bf = 0;
	}
	else if (_bf == 1)
	{
		
		//说明插入在左子树的右子树的右子树
		cur->_bf = -1;
		parent->_bf = 0;
		curright->_bf = 0;
	}
	else if (_bf == -1)
	{
		
		//说明插入在左子树的右子树的左子树
		cur->_bf = 0;
		parent->_bf = 1;
		curright->_bf = 0;
	}
	else
	{
		assert(false);
	}
}

右左双旋：

思路：（与左单旋仅仅只有更新平衡因子不同）

---1--- 对于左右双旋，触发条件是prev->_bf == 2 && newnode->_bf == -1，说明插入的节点在右子树的左子树，那么需要先以parent->_right作为根节点进行右单旋，再以parent为根节点进行左单旋,

---2--- 旋转过程复用单旋就行了，麻烦的是这里的平衡因子更新，我们对curleft的_bf平衡因子进行讨论，共需要分为三种情况：

  1. 如果_bf==0，那么说明插入的结点就是curleft，那么最后旋转过后parent，cur，curright的平衡因子都更新为0，达到彻底平衡
  2. 如果_bf==1，说明插入的结点在curright的右边，那么旋转过后cur->_bf = 0;
    parent->_bf = -1，curleft->_bf = 0
  3. 如果_bf==-1，说明插入的结点在curright的左边，那么旋转过后cur->_bf = 1;
    parent->_bf = 0，curleft->_bf = 0

Step 5：检查AVL树

        写完了AVL树的插入函数，如果要检查是否正确，该怎么办？请补充接下来三个函数：

InOrder：

我们对AVL树进行中序遍历，先递归左子树，再访问当前结点，最后递归右子树，AVL树的中序遍历正常情况下输出的数据应该有序，这是二叉搜索树的共同特性！

Height：

计算一下二叉树的高度，这在后面检查是否平衡因子会用到，如果递归到空结点，那么返回0，其次判断左子树和右子树的高度，选择较高的一边进行+1

IsBalance：

检查AVL是否平衡，需要计算左子树的高度和右子树的高度，那么当前节点的_bf就是高度之差，检查实际bf与计算出来的是否相等，最后递归判断左子树和右子树是否同样满足

void InOrder()
	{
		_InOrder(_root);
	}

	//为了方便测试AVL是否平衡，写一个判断函数
	bool IsBalance()
	{
		//这里可不能直接判断平衡因子，因为平衡因子有可能出错
		//选择计算两边的高度差，如果高度差小于2，说明平衡
		//但是这只能说明当前节点的平衡，不能说明整棵树的平衡
		//所以要递归判断
		return _IsBalance(_root);
	}

	int Height()
	{
		return _Height(_root);
	}

	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;
	}

	bool _IsBalance(Node* root)
	{
		if (root == nullptr)
		{
			return true;
		}
		int leftHeight = _Height(root->_left);
		int rightHeight = _Height(root->_right);
		if (root->_bf != rightHeight - leftHeight)
		{
			return false;
		}
		return abs(rightHeight - leftHeight) < 2 &&_IsBalance(root->_left) && _IsBalance(root->_right);
	}

	void _InOrder(Node* root)
	{
		if (root == nullptr)
		{
			return;
		}
		_InOrder(root->_left);
		cout << root->_kv.first << " " << root->_kv.second << endl;
		_InOrder(root->_right);
	}

Step 6：测试AVL树

        我将使用下面的test函数来测试AVL树是否平衡：

void test_AVLTree()
{
	vector<int> v = { 16,3,7,11,9,26,18,14,15 };
	AVLTree<int, int> avl;
	for (size_t i = 0; i < v.size(); ++i)
	{
		avl.Insert(make_pair(v[i], i));
		cout << "IsBalance:"<<v[i] <<" " << avl.IsBalance() << endl;
	}
	avl.InOrder();

	cout << endl;
}

        一起来看看运行结果：

        大功告成！至此AVL树的插入功能就完美实现了~

3.AVL树的优缺点

一、AVL 树的优点
1. 严格的平衡性
  • 核心机制：通过平衡因子（右子树高度-左子树高度）约束每个节点的左右子树高度差 ≤1，确保整棵树始终处于近似完全平衡状态。
  • 查询效率：所有操作（查找、插入、删除）的时间复杂度严格稳定在 O(log n)，尤其适合读密集型场景。
2. 稳定的性能下限
  • 避免退化：普通二叉搜索树（BST）在插入有序序列时会退化为链表（最坏时间复杂度 O (n)），而 AVL 树通过动态平衡彻底杜绝了这一问题。
  • 适用场景：对实时性要求高的系统，需要严格保证响应时间。
二、AVL 树的缺点
1. 高维护成本
  • 频繁旋转：插入或删除节点后，需沿父节点链回溯检查平衡因子，若发现失衡（平衡因子绝对值≥2），立即触发旋转操作。
  • 最坏情况：单次插入可能引发 O (log n) 次旋转（如插入导致根节点失衡）
2. 存储开销
  • 额外字段：每个节点需存储平衡因子（或子树高度），占用额外内存空间。
  • 对比红黑树：红黑树仅需 1 bit 存储颜色标记，而 AVL 树通常需要 32 位整型存储高度或平衡因子。
3. 实现复杂度高
  • 代码难度：需处理四种旋转类型（LL/RR/LR/RL）及父节点指针的复杂维护，调试成本高。

“如果 AVL 树如此完美 —— 严格的平衡、稳定的 O (log n) 时间复杂度，为何像 C++ STL 的std::map、Java 的TreeMap这些经典库却选择了红黑树？难道红黑树比 AVL 树更‘聪明’吗？”

“当一个数据结构需要每秒处理百万次插入操作时，AVL 树的‘绝对平衡’竟成了它的致命弱点。而红黑树用一种看似‘偷懒’的规则，以牺牲部分平衡性为代价，换取了惊人的性能飞跃 —— 它究竟如何做到的？”

“在插入和删除操作中，AVL 树可能触发连锁旋转，导致性能抖动；而红黑树仅需最多两次旋转即可恢复平衡 —— 这是魔法，还是数学的极致优化？”

下文将揭示：
红黑树如何用 “非严格平衡” 的设计哲学，在工程实践中实现对 AVL 树的性能碾压？它的五大铁律背后隐藏着怎样的数学之美？为何它能在数据库、操作系统、语言标准库中无处不在？

（提示：红黑树的秘密，藏在对 “路径长度” 的巧妙控制中……）


http://www.kler.cn/a/598180.html

相关文章：

  • 嵌入式学习(31)-Lora模块A39C-T400A30D1a
  • Transformer中，Fisher矩阵与权重之间关系
  • 开源AI大模型、AI智能名片与S2B2C商城小程序源码：实体店引流的破局之道
  • 新闻发布时间抽取（二）
  • 微调这件小事：训练集中的输入数据该作为instruction还是input？从LLaMA-Factory的源码中寻找答案吧~
  • CSS3学习教程，从入门到精通，CSS3 布局语法知识点及案例代码（15）
  • HTML5 SVG 学习笔记
  • LeetCode 92 Reverse Linked List Ⅱ 反转链表Ⅱ
  • 中间件漏洞-WebLogic篇
  • llama源码学习·model.py[6]TransformerBlock类
  • uni-app 与webView 互相传值
  • 内网渗透技术 Docker逃逸技术(提权)研究 CSMSF
  • IDEA批量替换项目下所有文件中的特定内容
  • 监控易运维管理软件：轻松部署，高效运维
  • mysql中的游标是什么？作用是什么？
  • 地理编码/经纬度解析/经纬度地址转换接口如何用JAVA对接
  • 大模型在非小细胞肺癌预测及治疗方案制定中的应用研究报告
  • 算力100问☞第93问：算力资源为何更分散了？
  • 算法-分治
  • Linux内核，内存分布