扫码获取 VIP 码
添加管理员微信获取 VIP 码
平衡二叉树，又称AVL树，是一种特殊的二叉排序树。它的名字来自两位苏联数学家阿德尔森·维尔斯基和兰迪斯，两人在一九六二年首次提出了这种带有自我平衡能力的数据结构，AVL正是两人姓氏首字母的缩写。在软考软件设计师的考试大纲里，平衡二叉树属于数据结构与算法部分的核心考点，几乎每年上午题都会以不同形式出现。
平衡二叉树的定义十分简洁，一句话就可以概括：一棵二叉树中任意一个结点的左子树与右子树高度之差都不超过一，这棵树就是平衡二叉树。这里的"高度之差"有一个专门的名词，叫作平衡因子。平衡因子的计算方式是左子树高度减去右子树高度，取值被严格限定在负一、零、正一三者之间。一旦某个结点的平衡因子越出这个区间，比如变成了正二或者负二，整棵树就失去了平衡性质，必须通过调整来恢复。
这个定义虽然只有短短一句话，但其中蕴含的要点却非常丰富。第一点，平衡性是对"每一个"结点提出的要求，而不是只针对根结点。很多初学者以为只要根结点左右两侧高度看上去差不多，整棵树就算平衡了，这其实是一个严重的误解。平衡二叉树要求沿途经过的每一个结点都必须满足平衡因子绝对值不超过一。哪怕只有一个内部结点左右子树高度相差两层，整棵树就已经不再是一棵合格的平衡二叉树。第二点，平衡二叉树首先必须是一棵二叉排序树，也就是说它继承了二叉排序树的全部性质：左子树所有结点的关键字小于根结点，右子树所有结点的关键字大于根结点，左右子树本身又各自是二叉排序树。平衡性是在这个排序性质之上额外附加的一条约束，它不能脱离排序性质独立存在。
第三点，也是考生最容易忽略的一点，就是平衡二叉树并不要求左右子树完全等高，而是允许高度差不超过一。这意味着平衡二叉树允许存在一定程度的不对称，只要这种不对称被控制在一层的范围内就可以。这个"不超过一"的宽容度，是平衡二叉树区别于严格平衡树的关键。
平衡因子是理解AVL树的入口，也是软考选择题里反复出现的高频考点。它的定义是一个结点的左子树高度减去右子树高度，通常记为BF，即平衡因子等于左子树高度减右子树高度。对于一棵平衡二叉树，任何一个结点的平衡因子只能是负一、零、正一这三个值。平衡因子等于正一，说明左子树比右子树高一层；等于负一，说明右子树比左子树高一层；等于零，说明左右子树高度完全相同。命题人特别喜欢围绕平衡因子的取值区间设置陷阱，比如给出一个结点左右子树高度相差二的情况，问此时平衡因子是多少、树是否仍然平衡，答案显然是失衡了，平衡因子已经达到了正二或负二。
这里需要特别强调一个细节：平衡因子描述的是"高度差"，而不是"结点数差"。左子树有五个结点、右子树有三个结点，这棵树完全可能是平衡的，因为决定平衡性的是子树的高度而非结点的个数。高度是路径上边的条数或者结点的层数，而不是结点数量的多寡。一棵子树结点数量很少，但若被组织成一条很长的单链，高度依然可以很大。这一点很容易和完全二叉树、满二叉树的概念混淆，也是命题人惯用的挖坑方向。
还需要注意平衡因子与树的高度的区别。树的高度通常定义为从根结点到最远叶子结点的路径长度，不同教材在具体计数上略有差异，但平衡因子的计算必须使用统一的高度定义。考生做题时应先确定题目采用的高度定义，再用同一套定义去计算左右子树高度并求出平衡因子，避免结果错误。
平衡二叉树是二叉排序树的一个子集，换句话说，每一棵平衡二叉树都必然是二叉排序树，但并不是每一棵二叉排序树都是平衡二叉树。二叉排序树的形态高度依赖于插入顺序：如果关键字按照从小到大或者从大到小的顺序依次插入，二叉排序树就会退化成一棵单链形状的树，此时查找一个结点的时间复杂度从理想的对数级别退化到线性级别，查找效率大幅下降。平衡二叉树的诞生正是为了解决这个退化问题，它通过强制约束每个结点左右子树的高度差不超过一，保证整棵树的高度始终维持在关于结点数量的对数数量级，从而让查找、插入、删除操作的时间复杂度稳定在对数级别。
理解这一层关系，就能明白为什么教材里要把平衡二叉树放在二叉排序树之后讲解。二叉排序树解决的是"如何组织数据以支持快速查找"的问题，平衡二叉树解决的是"如何保证二叉排序树始终不退化"的问题。前者给出了数据结构的基本框架，后者给出了维持框架效率的自我调节机制。二者一脉相承，缺一不可。在软考的命题体系里，平衡二叉树与二叉排序树的关系也经常被拿来直接考查，比如问"平衡二叉树一定是二叉排序树吗"或者"二叉排序树一定是平衡二叉树吗"，前者的答案是肯定的，后者的答案是否定的。
平衡二叉树的核心机制，归结起来就是一句话：在插入或删除结点导致树失衡之后，通过有限次的旋转操作，让树重新回到平衡状态，同时不破坏二叉排序树的中序有序性质。要理解这个机制，必须先弄清楚失衡是如何产生的。
当我们在平衡二叉树中插入一个新结点时，新结点总是作为叶子结点挂在某个位置上。插入之后，从这个新结点沿着路径向上回溯到根结点，沿途每一个祖先结点的平衡因子都可能发生变化。对于绝大多数祖先结点，左右子树高度差仍然在负一到正一的范围内，不会引发问题。但总有某个祖先结点，由于新结点的加入，它的某一侧子树高度增加了一，导致平衡因子从正一变成正二，或者从负一变成负二，这时这个结点就成为失衡结点，整棵树由此失去平衡。
这里有一个关键结论需要记住：在插入操作中，新结点只会让沿途祖先结点的某一侧子树高度增加一，因此任何一个祖先结点的平衡因子在插入之后最多只可能增加或减少一。这意味着，如果插入之前整棵树是平衡的，那么插入之后最多只会出现一个平衡因子绝对值达到二的失衡结点。这个结论保证了调整操作最多只需要针对一个结点展开，不会出现连锁反应。这正是AVL树调整高效性的理论根基。
在插入导致失衡的场景中，一个重要的概念是最小失衡子树。所谓最小失衡子树，是指以"离新插入结点最近的、平衡因子绝对值超过一的结点"为根的子树。这个定义里有"最近"两个字，它划定了需要调整的范围。离新结点越远的祖先，受插入影响越晚显现；而离新结点最近的那个失衡祖先，其内部结构最需要立即调整。只要把这个最小失衡子树调整平衡，它上面的所有祖先结点自然也就恢复了平衡。
理解最小失衡子树的意义在于，它告诉我们旋转操作的作用范围是局部的、有限的。一次插入最多只需要调整一个最小失衡子树，通过一至两次旋转即可完成，不需要对整个树做大规模的翻动。这个局部性保证了AVL树调整操作的高效。与之形成对比的是，某些平衡机制在调整时可能需要沿着路径向上逐层传播，甚至可能引发多次调整，而AVL树由于引入了最小失衡子树的概念，把调整范围压缩到了一个局部子树内。
旋转是平衡二叉树自我修复的唯一手段，它本质上是一种改变树局部结构、同时保持中序遍历序列不变的操作。AVL树的旋转归纳起来只有四种基本形态，分别对应四种失衡情形：LL型、RR型、LR型、RL型。其中LL型和RR型属于单旋，LR型和RL型属于双旋。
单旋的本质是"提拉"：把失衡子树中的一个孩子结点提升为新的根，让原来的根降级成为它的孩子，从而把偏高的一侧"压平"一截。双旋的本质则是两次单旋的组合，先对失衡结点的某个孩子做一次方向相反的单旋，把"拐弯"的失衡形态先转化成直线的单旋形态，再做一次单旋完成平衡。无论单旋还是双旋，旋转前后树的中序遍历序列保持不变，这是旋转操作正确性的根本保证。
从实现的角度看，旋转操作本质上只是若干个指针的重新赋值，时间复杂度为常数级别。正是因为旋转如此廉价，AVL树才敢于在每次插入或删除后都检查并执行必要的旋转，用极小的代价换取整棵树高度的严格控制。
四种失衡形态的命名规则非常直观，它描述的是新插入结点相对于失衡结点的位置走向。失衡结点的左子树的左子树一侧插入导致失衡，称为LL型；右子树的右子树一侧插入导致失衡，称为RR型；左子树的右子树一侧插入导致失衡，称为LR型；右子树的左子树一侧插入导致失衡，称为RL型。前两种是"直线型"失衡，后两种是"拐弯型"失衡。下面逐一拆解每种形态的处理方式。
LL型失衡指的是，在失衡结点的左孩子的左子树上插入了新结点，导致失衡结点的平衡因子变为正二。这种情况下，失衡结点、它的左孩子、左孩子的左孩子三者大致沿着一条左斜线排列，因此称为LL型。处理LL型失衡只需要一次右旋，也叫顺时针旋转。右旋的操作是：以失衡结点的左孩子作为新的子树根，让失衡结点成为这个左孩子的右孩子，同时把左孩子的原右子树移交为失衡结点的左子树。经过这样一次右旋，原本偏
本篇完！