数据结构第七节：AVL树（初阶）

【本节要点】

AVL树的概念

AVL树结点的定义

AVL数的旋转

AVL树的插入

AVL树的验证

AVL树（Adelson-Velsky and Landis Tree） 是一种自平衡二叉搜索树（BST），通过严格限制节点的高度差（平衡因子）来保证高效的操作性能。本文将深入讲解其核心概念、节点结构、旋转操作及实现细节，适合算法初学者理解。

一、AVL树的概念

1.1 定义与特性

AVL树是首个自平衡二叉搜索树（BST），其核心特性体现在严格的高度控制上：

• 平衡因子约束 ：每个节点的左右子树高度差绝对值不超过1，平衡因子（BF）= 右子树高度 - 左子树高度
• 动态平衡机制 ：通过旋转操作维持平衡，树高始终为O(logN)
• 时间复杂度优势 ：所有基本操作（插入/删除/查找）的时间复杂度稳定为O(logN)

# ASCII树形结构示例
        A (BF=0)
       / \
(BF=-1)B   C(BF=1)
     /     \
    D       E

1.2 应用场景

二、AVL树节点的定义（C++实现）

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;  // 平衡因子
    
    // AVL树结点的构造函数
	AVLTreeNode(const pair<K, V>& kv)
		:_kv(kv)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _bf(0)
	{}
};

三、AVL树的旋转操作

旋转是AVL树维持平衡的核心机制，共四种类型：LL、RR、LR、RL。以下通过示例图解析旋转逻辑。

3.1 旋转触发条件

当插入或删除节点导致某节点 |BF| > 1 时，需执行旋转。

例如：插入节点后，根节点的 BF(A) = 2 （失衡）。

3.2 四种旋转类型

1. 左左：右单旋

场景：新节点插入较高左子树的左侧

步骤：

• 将60右旋为30的新右子树，。
• 更新60、30的高度。
• 调30-60-b的连接关系。

2. 右右：左单旋

场景：新节点插入较高右子树的右侧

3. 左右：先左单旋再右单旋

场景：新节点插入较高左子树的右侧

右左：先右单旋再左单旋

新节点插入较高右子树的左侧

旋转类型对照表

四、AVL树的插入操作

插入流程 步骤：

定位插入位置 ：按二叉搜索树规则找到空节点位置。

自底向上更新祖先节点的平衡因子 ：

• 若插入后 BF == 0 ：树平衡，插入完成。
• 若 BF == ±1 ：继续向上更新，可能引发祖父节点失衡。
• 若 BF == ±2 ：执行对应旋转（LL/RR/LR/RL）。

递归处理

五、AVL树的验证

验证其为二叉搜索树： 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

验证其为平衡树：

• 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
• 节点的平衡因子是否计算正确

总结

AVL树通过严格的平衡约束，在动态数据场景下提供稳定的 O(logN) 操作效率。其核心在于旋转操作的灵活应用，但实现复杂度较高。实际工程中，Red-Black树因旋转规则更简单，常作为替代方案，但AVL树仍是理解自平衡BST的基础模型。

以上就是 AVL树初阶知识 的了解，接下来我会 继续更新进阶知识 ： AVL树的模拟实现 。 制作不易，请大家多多点赞收藏啦！！