详解平衡二叉树的失衡类型划分及调整策略设计
神奇少女祝XiXi 人气:11. 平衡二叉树
平衡二叉树
对于树中的每个节点要求：
- 左子树和右子树的深度差不超过1
- 左右子树都是平衡二叉树
平衡因子 = 左子树深度 - 右子树深度
==> 在一棵平衡二叉树中，所有节点的平衡因子只可能有三种取值：-1, 0, 1
2. 失衡原因分析及失衡情况分类
平衡二叉树是一种特殊的二叉排序树，插入新节点的方法与在二叉排序树中插入节点相同：先查找，然后在查找失败的位置插入新节点。
但是在一棵平衡二叉树中新插入一个节点可能会导致树的失衡，因此每次插入新节点之后要对树进行调整。
书上和网上的资料很多，但大部分都只给出了最终的结论，没有给出为什么要这样做的原因，现在我试图用自己的方式来理解AVL树的调整方法：
1. 在平衡二叉树中新插入节点会造成树中某些节点平衡因子的改变，从而有失衡的风险。
==> 只有插入路径上的节点的平衡因子可能会改变。
==> 在插入路径上的节点中，只有那些原本的平衡因子为1, -1的节点可能会失衡（平衡因子变为2）。
==> 原本平衡因子为1的节点失衡后平衡因子会变为2；原本平衡因子为-1的节点失衡后平衡因子会变为-2。并且这两种情况是对称的。
2. 在插入路径上可能会有多个节点失衡，但是高层节点的失衡是由低层节点的失衡造成的，因此存在一个最低失衡节点，只要将这个最低失衡节点调整平衡，并且保证以该节点为根的子树的高度和原来一样，那么高层节点的失衡就会自动恢复。
3. 所谓对失衡节点的调整，其实就是在已知一些子树和节点相互之间的大小关系以及他们的高度等信息时用这些子树和节点重新组装成一棵满足平衡二叉树要求的树。
下面仅考虑最低失衡节点原本的平衡因子为1的情况：
==> 该节点失衡后平衡因子变为2，说明新节点的插入导致该节点的左子树的高度增加了1，这也间接说明了新节点插在了该节点的左子树上。
==> 插在该节点的左子树上有两种可能的情况：①该节点原本就没有左孩子，②该节点原本是有左孩子的。
==> 情况①不可能存在，因为该节点原本的平衡因子为1，而 平衡因子 = 左子树深度 - 右子树深度，所以左子树的深度至少为1。
我们来重新梳理一下目前掌握的结论：
新节点（记为S）一定插在最低失衡节点（记为A）的左子树上，并且A原本一定有左孩子（记为B）。因为S的插入导致以B为根的子树整体高度增加1，从而导致了A节点的失衡。
还有另外一个重要的结论是：B原本的平衡因子一定为0，证明如下：
首先，因为B原本是平衡的，所以其平衡因子只有三种可能的取值：-1, 0, 1。
1. 如果B原本的平衡因子为-1或1，并且插入S之后以B为根的子树整体高度增加1，那么有以下两种可能的情况：
在这两种情况下，插入新节点之后B都会失衡，这样的话A就不是最低失衡节点了，与假设矛盾，因此这两种情况都不成立。
2. 如果原本B的平衡因子为0，则有以下两种情况，这两种情况都成立：
综上，B原本的平衡因子一定为0，证毕。
至此，我们将A原本的平衡因子为1时的可能的情况分成了两种：
Case1就是所谓的 "LL型"，Case2就是所谓的 "LR型"。
根据A和B的平衡因子可以很容易地得出结论：BL、BR、AR的高度相等。证明如下：
B原本的平衡因子为0
==> BL的高度与BR相等，记为n
==> 以B为根的子树原本的高度为n+1
==> 插入S后以B为根的子树高度变为n+2
插入S后A的平衡因子为2
==> (n+2) - depth(AR) = 2
==> depth(AR) = n = depth(BL) = depth(BR)，证毕。
有了这些信息之后，开始制定调整策略。
3. 失衡调整策略
首先，对于调整策略有几点要明确的：
1. 调整对象：以最低层失衡节点为根的子树
2. 调整目标：①恢复平衡（根节点平衡因子<=1） ②高度不变（高度恢复为失衡前的高度）
3. 调整依据（调整约束）：满足二叉排序树的大小关系（即任意一个节点的左子树上的节点都小于该节点，右子树上的节点都大于该节点）
（3.1）LL型
Step1: 先分析失衡后 子树BL，BR，AR和节点相互之间的大小关系：
虽然插入S后以A为根的子树失衡了，但是仍然满足平衡二叉树的约束，即：
(BL+S) < B < (BR) < A < (AR)
加括号代表这棵树上的所有节点。
Step2: 记插入S前以A为根的子树的高度为H，则插入S后：
depth(BR) = depth(AR) = H-2
depth(BL+S) = H-1
Step3: 根据上述结论设计调整策略如下：
0. 记录A的父亲节点FA，如果A为根节点则FA=NULL；
1. 以A为根节点，B->right和A->right分别作为左子树和右子树构建新树TreeA；
2. 以B为根节点，B->left和TreeA分别作为左子树和右子树构建新树TreeB；
3. 如果FA==NULL，则令root指向B；
否则，如果FA->left == A则令FA->left指向B，如果FA->right == A则令FA->right指向B。
在该调整策略中：调整后仍满足Step1得出的大小关系，并且调整后树高仍为H。
观察该策略发现，其实相当于以B为轴，对A做了依次顺时针旋转。这也就是我们常说的 “右旋”。
（3.2）LR型
按照和LL型相同的分析方法，当进行到Step3的时候会发现：如果满足了Step1得出的大小关系，就无法得出使得树高不变的策略。
所以，我们需要对LR型的情况做进一步细化：
对LR型的进一步细分：
因为新节点S插在了B的右子树上，那我们就先分为两种情况：①失衡前B的右子树为空，②失衡前B的右子树不为空。
这里和之前不同，情况①时可能成立的。之前在对"A失衡前左子树是否为空"进行讨论时的前提限制是：A失衡前的平衡因子为1，所以A的左子树不可能为空。但是B失衡前的平衡因子是0，所以它失衡前的右子树可以为空。如果B失衡前右子树BR为空，根据之前的结论，可以得出BL、AR也为空。
对于情况②，既然失衡前B的右子树不为空，不妨设B的右孩子为C节点，因此根据S是插在了C节点的左子树还是右子树上又可以将情况②再分为两种子情况。
最终我们将LR型细分为3种子情况：
之后在对每一种子情况按照和LL型相同的分析方法分析其调整策略，结论如下：
观察后发现，这三种调整策略可以归纳为一种：
0. 记录A的父亲节点FA，如果A为根节点则FA=NULL；
1. 以B为根节点，B->left和C->left分别作为左子树和右子树构建新树TreeB；
2. 以A为根节点，C->right和A->right分别作为左子树和右子树构建新树TreeA；
3. 以C为根节点，TreeB和TreeA分别作为左子树和右子树构建新树TreeC;
4. 如果FA==NULL，则令root指向C；
否则，如果FA->left == A则令FA->left指向C，如果FA->right == A则令FA->right指向C。
观察该策略，是不是很像：先对B做一次逆时针旋转，再对A做一次顺时针旋转 ？这就是我们常说的 “先左旋后右旋”。
（3.3）判断失衡类型
至此，对于LL型和LR型的失衡调整策略就已经设计出来了，下面还有一个问题就是怎么判断究竟是哪一种失衡类型呢？
这个问题其实很简单，根据失衡后A和B的平衡因子就可以做出判断：
A的平衡因子等于2, B的平衡因子等于1 ==> LL型
A的平衡因子等于2, B的平衡因子等于-1 ==> LR型
对于RR型和RL型的失衡策略和判断失衡类型可以按照同样的方法得出，由于本文的目的在于对这些结论是如何得出的进行解释，至于具体结论网上有很多的资料可以参考，就不再赘述。在此分享一下耿国华老师主编的《数据结构——C语言描述》，这本书里面有非常非常详细的讲解和完整代码，可以供大家参考。
4. 在AVL树中插入节点的完整步骤
最后，再梳理一下在一棵AVL树中插入一个新节点的完整步骤：
1. 查找新节点S应插入的位置，并将S节点插入（插入方法与在二叉排序树中插入一个节点相同）；
同时记录：
- 距S的插入位置最近且平衡因子等于1或-1的节点A => 如果新节点的插入引起失衡的话，A即为最低层失衡节点；
- 以及节点A的父亲节点FA => 用于之后将调整后的失衡子树插入树中。
2. 修改从A到S路径上各节点的平衡因子。
解释：只需要修改从A到S路径上各节点的平衡因子，而不是整条查找路径上所有节点的平衡因子，原因是：根据我们之前设计的调整策略调整之后，失衡子树的高度不变，因此在最低层失衡节点之上的节点的平衡因子都不会受到影响，所以不必更改。
3. 确定节点B（B是A节点的孩子，根据S节点的大小与A节点的大小之间的关系确定是A的左孩子还是右孩子）
根据A、B的平衡因子判断是否失衡，如果失衡的话进一步判断出失衡类型。
4. 根据失衡类型执行相应的调整策略。
5. 更新调整后从A到S路径上各节点的平衡因子。
后记
之前在学这部分内容的时候基本上是靠背，一直不理解为什么会分成这几种类型以及为什么这种类型就要按这样的方法处理。我也一直没有找到对此有解释的资料，大部分书上和网上的资料都只是给出了结论，所以只好自己摸索，并将自己试图理解的思路记录下来和大家分析。
如果有纰漏还望指正。
参考书籍：《数据结构——C语言描述》耿国华著
加载全部内容