15 平衡二叉树（AVL）：平衡如此重要，怎么做到的？
你好，我是王健伟。
上节课我们讨论了“二叉查找树”这个话题，最后提到，为了提高查找效率，应该尽可能地让二叉查找树的高度变得最小。也就是说，在创建二叉查找树的时候，要尽可能让二叉查找树保持左右节点的平衡。这就是“平衡二叉树”的由来。
平衡二叉树作为后续红黑树学习的铺垫，很容易被人忽略。这节课，我们就来捋清“达到平衡”的思路，避免在写代码的时候手忙脚乱，也为后续的学习打好基础。
什么是平衡二叉树？
平衡二叉树也叫平衡二叉搜索树，英文名是Balanced Binary Tree，简称AVL树（平衡树）。AVL名字取自于发明平衡二叉树的两个人名字（Adelson-Velsky 以及 Landis）中的字母。平衡二叉树，首先是一棵二叉查找树，在构建这棵二叉查找树的过程中进行平衡化的处理形成平衡二叉树。
要理解平衡二叉树，就要先引入平衡因子BF（Balance Factor）的概念：该节点左子树的高度减去右子树的高度。有的资料上也会用右子树高度减去左子树高度，也是可以的。
所以，一棵平衡二叉树上任一节点的平衡因子只能是-1、0、1三个值中的一个。观察图1左侧二叉查找树各个节点的平衡因子值，显然就是一棵平衡二叉树。而右侧就不是。
平衡二叉树有两个性质。左子树和右子树都是平衡二叉树，而且任一节点的左子树和右子树的高度之差不超过1。
目前，要解决的主要问题是在插入一个新的节点后，保持原有二叉查找树的平衡。比如图2中，当插入新节点（值为72）时，插入路线上所经过的所有节点的平衡因子都发生了改变，二叉树不再保持平衡，退化成了普通的二叉查找树。那么，为了提高查找效率，就要对二叉树进行平衡性调整。
基础实现代码可以参考课件中针对类模板AVLNode的定义和类模板AVLTree，包括其中的构造函数AVLTree()和析构函数~AVLTree()的定义。
插入操作后的平衡性调整
一般来说，插入、删除这两种操作会改变平衡二叉树的平衡性。
当一棵平衡二叉树不再平衡时，就退化成了一棵二叉查找树，为了提高查找效率，必须对该二叉树进行平衡性调整。平衡性调整相关代码的实现方法并不唯一，这里我会选择比较传统和比较好理解的方式来进行代码实现，后续还会提供一个代码相对简单但理解起来难度更大的代码实现方法。
在图2中，插入新节点72后，节点60、80、70的平衡因子因为不在-1到1之间，从而打破了这棵二叉树的平衡。那么就从插入的新节点72回溯，经过节点75，找到第一个不平衡的节点70，对以这个节点为根的子树（包含节点70、75、72）进行平衡性调整就可以了。
这里将以节点70为根的这棵需要进行平衡性调整的子树称为“最小不平衡子树”。之所以称为“最小”，是因为任何其他不平衡子树所包含的节点数量，比如节点80、70、90、75、72这棵子树，都比这棵“最小不平衡子树”包含的节点数量多。
只要将这棵“最小不平衡子树”调整平衡，其他不平衡节点的平衡因子都会恢复到原来的值。如图3所示。
也就是说，只要将最小不平衡子树进行平衡性调整，整个二叉查找树就会恢复平衡。
在图3中，将最小不平衡子树（包含节点70、75、72）进行了平衡性调整——将节点72作为了子树的新根（后面会详述平衡性调整的过程），将节点70作为72的左子树，将节点75作为72的右子树。这样调整后，节点60和节点80的平衡因子也从-2、2恢复到-1、1了。
换句话说，本来图2左侧图中节点80的左子树（包括节点70、75）的深度为2，但因为加入了节点72，导致80的左子树深度变为3，通过图3的平衡性调整，节点80的左子树的深度又恢复回了2，所以自然就可以得到结论——“只要将最小不平衡子树进行平衡性调整（高度复原），整个二叉查找树就会恢复平衡”。
平衡性调整是通过对该二叉树进行“旋转”操作来达成的。旋转被分为四种旋转方式，分别为左旋转，右旋转，先左后右旋转，先右后左旋转。其中前两个又叫做单旋转，后两个又叫做双旋转。每一次旋转，都会导致孩子节点变成父亲节点，父亲节点变成孩子节点，这一点印象通过后面的学习会进一步加深。
而对于最小不平衡子树（将该子树命名为A）的产生又分为四种情况。
- 在A的“左孩子的左子树”中插入节点导致A不平衡（简称LL：L代表左Left）。此时需要通过“右旋转”来调整平衡。
- 在A的“右孩子的右子树”中插入节点导致A不平衡（简称RR：R代表右Right）。此时需要通过“左旋转”来调整平衡。
- 在A的“左孩子的右子树”中插入节点导致A不平衡（简称LR）。此时需要通过“先左后右旋转”来调整平衡。
- 在A的“右孩子的左子树”中插入节点导致A不平衡（简称RL）。此时需要通过“先右后左旋转”来调整平衡。
这里，你可以先实现一下基本的插入元素操作代码。在插入操作的实现中，需要借助以往实现过的栈代码来保存插入的节点路径信息，因此要把相关的链栈实现代码引入进来。
在类模板AVLTree的定义中，增加InsertElem()成员函数(参见课件)。当然，此时的InsertElem()成员函数还没写完整，其中还有与平衡性调整相关的代码后面再增加。
接下来，我们分别看一下这四种产生最小不平衡子树的情况。
在A的“左孩子的左子树”中插入节点导致A不平衡（简称LL）
结构图较为抽象，我也给你列举了一些具体的例子参考。
想一想，想要图5中的最小不平衡子树恢复平衡要怎么做呢？通过右旋转的方式，可以理解为左边长了就向右转，用语言描述只需要一句话：
将失衡的节点A（95）也就是最上边这个失衡的节点向右侧旋转来作为节点B（60）的右孩子，当然，如果节点A有右孩子，那么该右孩子也要跟着节点A一起旋转。如果节点B原来有右孩子，则首先将节点B这个右孩子作为节点A的左孩子。
针对图5中的三个二叉排序树，重新调整为平衡二叉树后如图6所示：
观察图5与图6的调整过程，不难得到几个结论。
- 插入新节点导致失衡前这个子树有多高，调整平衡后这个树就会恢复为多高。
比如图5中间的图形，本来高度为3，增加新节点20后，高度变为4并失衡，重新调整平衡后树的高度又恢复为3。
- 将一棵最小不平衡子树进行平衡性调整平衡后，这棵调整后的子树的根的平衡因子变为0。
比如图5右侧的图形，最小不平衡子树的根节点是95，失衡前该节点的平衡因子是1，失衡后该节点的平衡因子是2，进行平衡性调整后，这棵调整后的子树的根变成了节点60，同时这个根（节点60）的平衡因子为0（不用理会原来是多少）。
上面的结论同样适用于RR、LR、RL的情况，所以还是要好好理解。你可以多在纸上演练几遍平衡性调整的过程，理清思路。接下来，我们就要说说平衡性调整的程序编写思路了。
那从写程序的角度来看，当插入一个新节点导致原来的平衡二叉树失衡后，会发生什么呢？
首先，新插入的节点的平衡因子自然是0,因为新插入的节点肯定是叶子节点。
其次，沿着新插入的节点向上逐个找寻父节点并调整父节点的平衡因子。虽然理论上来说，插入路线上经过的所有节点的平衡因子都会发生改变，但是一旦找到最小不平衡子树并对这个子树调整平衡后，其他不平衡的节点的平衡因子都会恢复到不平衡之前的原值。这意味着此时“插入路线上所经过的所有没调整平衡因子的节点的平衡因子”不需要再调整了，因为他们应该保持原值。这句话有点难，该怎么理解呢？我们可以结合图7进一步解释一下。
- 图7左侧图，节点95和60的平衡因子是1，当插入新节点20时，导致这棵二叉排序树失衡，此时理论上来说节点95和节点60的平衡因子都应该变为2，如图7中间图。
- 但写程序时会从下向上（用一个循环）修改节点的平衡因子——新插入的节点20为叶子节点，平衡因子自然为0，然后将节点40的平衡因子从0修改为1，接着将节点60的平衡因子从1修改为2，此时注意节点95的平衡因子还没有被修改，依然保持为1。因为节点60的平衡因子为2，显然节点60、40、20是一棵最小不平衡子树，要进行平衡性调整，调整后的新子树以节点40为根并且节点40的平衡因子变为0，节点60的平衡因子也变为0，如图7右侧图。
- 此时，整个二叉排序树就平衡了，平衡性调整结束，不再需要修改节点95的平衡因子，还是保持原值1（图7左侧图中的就是原值）即可。
这样，沿着新插入的节点向上逐个找寻父节点并调整父节点的平衡因子这件事就完成了。
此时，整个二叉排序树平衡，平衡性调整结束，不再需要修改节点95的平衡因子，还是保持原值1（图7左侧图中的就是原值）即可。
将LL插入导致失衡的二叉排序树重新调整为平衡的简明表示图如图8所示：
在代码实现上，我们引入RotateRight成员函数来针对LL插入导致的失衡来调整平衡，具体可以参考课件。
为了能够对这个成员函数进行测试，需要对前面InsertElem成员函数的如下语句中扩充一些代码。
如果你看到了课件中的代码，会发现“根相关指针的调整”代码段理解起来稍微有点难度，这里解释一下。
- 观察图5与图6，将二叉排序树调整平衡后，二叉排序树的根发生了改变，从节点95更改为节点60，这是通过代码行root = parent;来完成的。
- 观察图7，将二叉排序树调整平衡后，二叉排序树的根没有改变，依旧是节点95，但节点95的左孩子原来指向的是节点60，现在要更改为指向节点40，这是通过代码行pParentPoint->leftChild = parent;或者pParentPoint->rightChild = parent;来完成的。
在main主函数中加入代码，可以通过更改array数组，在其中放入不同的数据来测试图5和图7情形下程序对二叉排序树平衡性的调整是否正确。
AVLTree<int> mybtr;
int array[] = { 95,60,120,40,20 };
int acount = sizeof(array) / sizeof(int);
for (int i = 0; i < acount; ++i)
mybtr.InsertElem(array[i]);
你可以自行增加一段中序遍历代码来输出平衡二叉树的各个节点内容，以确定平衡调整的正确性。
在A的“右孩子的右子树”中插入节点导致A不平衡（简称RR）
结构图较为抽象，我也给你列举了一些具体的例子参考。
那么如何通过左旋转（右边长了就向左转）让图10中的最小不平衡子树恢复平衡呢？用语言描述只需要一句话：
将失衡的节点A（40）也就是最上边这个失衡的节点向左侧旋转，作为节点B（70）的左孩子。当然，如果节点A有左孩子，那么该左孩子也要跟着节点A一起旋转。如果节点B原来有左孩子，则首先将节点B这个左孩子作为节点A的右孩子。
针对图10中的三个二叉排序树，重新调整为平衡二叉树后如图11所示。
将RR插入导致失衡的二叉排序树重新调整为平衡的简明表示图如图12所示。
在代码实现上，我们引入RotateLeft成员函数来针对RR插入导致的失衡来调整平衡，具体可以参考课件，参考前面LL插入导致失衡的代码，这里其实很好写，你可以尝试一下。
为了能够对这个成员函数进行测试，继续在InsertElem成员函数的如下语句中扩充一些代码。
在main主函数中加入代码，可以通过更改array数组，在其中放入不同的数据来测试图10情形下程序对二叉排序树平衡性的调整是否正确。
AVLTree<int> mybtr;
int array[] = { 40,20,60,95,120 };
int acount = sizeof(array) / sizeof(int);
for (int i = 0; i < acount; ++i)
mybtr.InsertElem(array[i]);
在子树A的“左孩子的右子树”中插入节点导致A不平衡（LR）
图14所示的几棵二叉查找树都属于在A的“左孩子的右子树”中插入节点导致失衡的情形。
那么如何通过先左后右旋转让图14中的最小不平衡子树恢复平衡呢？简单来说，就是通过一次左旋转先让节点95、60、70处于一条直线上，然后再通过一次右旋转（前面讲解过）让失衡子树恢复平衡。
这里可能有些复杂，我们尝试描述一下。
- 将节点B（节点60）也就是从上向下数第二行的节点向左侧旋转，让其向左下方下落，如果节点B有左孩子则该左孩子也要跟着节点B一起旋转，那么节点B的右子树（以70为根，可以称70这个节点为节点C）就被提起来顶替了节点B的位置。得到的效果就是节点B（节点60）变成了其原右孩子（节点70）的左孩子。值得一提的是，这里存在两种情况：如果节点C（节点70）原来有左孩子，则将这个左孩子变成节点B（节点60）的右孩子；如果节点C（节点70）原来有右孩子，则这个右孩子要跟着节点70一起旋转。
- 将失衡的节点A（节点95）也就是最上边这个失衡的节点向右侧旋转来作为新节点B（节点70）的右孩子。这里也存在两种情况：如果节点70原来有右孩子，则将这个右孩子变成节点95的左孩子；如果节点95原来有右孩子，则这个右孩子要跟着节点95一起旋转。
针对图14中的三个二叉排序树，重新调整为平衡二叉树后如图15所示。
将LR插入导致失衡的二叉排序树重新调整为平衡的简明表示图如图16所示。
在代码实现上，我们引入RotateLeftRight成员函数来针对LR插入导致的失衡来调整平衡，具体可以参见课件。
为了能够对这个成员函数进行测试，继续在InsertElem成员函数的如下语句中扩充一些代码。
在main主函数中加入代码，通过更改array数组，在其中放入不同的数据来测试图15情形下程序对二叉排序树平衡性的调整是否正确。
AVLTree<int> mybtr;
int array[] = { 95,60,120,40,50 };
int acount = sizeof(array) / sizeof(int);
for (int i = 0; i < acount; ++i)
mybtr.InsertElem(array[i]);
在子树A的“右孩子的左子树”中插入节点导致A不平衡（RL）
这种情况与LR正好相反，先来看一下结构示意图。
下图18所示的几棵二叉查找树都属于在A的“右孩子的左子树”中插入节点导致失衡的情形：
那么如何通过先右后左旋转让图18中的最小不平衡子树恢复平衡呢？简单说来就是通过一次右旋转先让节点60、120、95处于一条直线上，然后再通过一次左旋转（前面讲解过）让失衡子树恢复平衡。
这里可能有些复杂，我们尝试描述一下。
- 将节点B（节点120）也就是从上向下数第二行的节点向右侧旋转让其向右下方下落，如果节点B有右孩子则该右孩子也要跟着节点B一起旋转，那么节点B的左子树（以95为根，可以称95这个节点为节点C）就被提起来顶替了节点B的位置。得到的效果就是节点B（节点120）变成了其原左孩子（节点95）的右孩子。值得一提的是，这里存在两种情况：如果节点C（节点95）原来有左孩子，则这个左孩子要跟着节点95一起旋转；如果节点C（节点95）原来有右孩子，则将这个右孩子变成节点B（节点120）的左孩子。
- 将失衡的节点A（节点60）也就是最上边这个失衡的节点向左侧旋转来作为新节点B（节点95）的左孩子。值得一提的是，这里存在两种情况：如果节点95原来有左孩子，则将这个左孩子变成节点60的右孩子；如果节点60原来有左孩子，则这个左孩子要跟着节点60一起旋转。
针对图18中的三个二叉排序树，重新调整为平衡二叉树后如图19所示。
将RL插入导致失衡的二叉排序树重新调整为平衡的简明表示图如图20所示。
在代码实现上，我们引入RotateRightLeft成员函数来针对RL插入导致的失衡来调整平衡，具体可以参考课件。
你可以考虑一个问题，如果代码写熟练了的话，是否可以将这两次旋转合并为一次，不非得分开两次进行书写，这个尝试，就留给你了。
为了能够对这个成员函数进行测试，继续在InsertElem成员函数的如下语句中扩充一些代码。
在main主函数中加入代码，通过更改array数组，在其中放入不同的数据来测试图19情形下程序对二叉排序树平衡性的调整是否正确。
AVLTree<int> mybtr;
int array[] = { 60,40,70,120,95 };
int acount = sizeof(array) / sizeof(int);
for (int i = 0; i < acount; ++i)
mybtr.InsertElem(array[i]);
当然，二叉查找树插入操作后的平衡性调整及实现代码并不是只有上面这一种写法，只不过上面这种写法从理解的角度相对好理解。
在课件目录“二叉平衡树_增加节点平衡性调整_另一种实现方法”中，我提供了一位网友公开出的另一种二叉查找树进行节点插入操作后的平衡性调整实现代码供你参考，代码量相对较小，但是因为用到了递归调用，所以理解难度要稍微大一些。
这个实现代码中通过引入二叉树节点高度的概念取代平衡因子的概念，来调整二叉树的平衡；同时，其“先左后右旋转”与“先右后左旋转”没有写成单独的成员函数，而是通过先后调用“左旋转（rrRotation）、右旋转（llRotation）”以及“右旋转、左旋转”成员函数来实现的。你可以通过跟踪调试的手段对代码的实现步骤加深理解。
小结
通过上节课的学习，你已经知道，为了提高查找效率，在创建二叉树的时候，要尽可能让二叉树的节点保持左右平衡，这就引出了本节所讲述的平衡二叉树。
这节课，我们认识了平衡二叉树的基本概念、性质，也引入了平衡因子BF（Balance Factor）的概念，书写了平衡二叉树的基础实现代码。接下来，我们就要考虑针对平衡二叉树的节点插入操作了。
这就涉及一个比较复杂的话题——“插入操作后的平衡性调整”。平衡性调整这件事有一个最普遍的结论，那就是“只要将最小不平衡子树进行平衡性调整（高度复原），整个二叉查找树就会恢复平衡”。
对于具体如何进行平衡性调整，我这里说了很多理论和思想性的东西，尽量保证了介绍的详细和全面性。四种旋转方法分别是左旋转、右旋转、先左后右旋转、先右后左旋转，它们可以应对各种不同形状的二叉查找树。我也分别提供了这四种旋转方法的实现代码，这里需要你加强记忆，面试官最喜欢考这个东西。
在“插入操作后的平衡性调整”话题中，我阐述了四种产生最小不平衡子树的情形，给出了详细的讲解图形、恢复平衡的调整方法，并且针对每一种情形都循序渐进地提供了详尽的实现代码。这里注意，我提供代码的目的是保持课程的完整性，并不是要求你一定要记下来，你只需要简单理解，做到有印象，和别人聊到这个话题的时候能聊上几句就行了。如果将来真在工作中遇到这些细节知识，你再来现回忆现查也是来得及的。
课后思考
有这样一组数据：
现在，希望用这组提供的数据生成一棵平衡二叉树，请你在纸上画一画看如何手工把这个二叉树设置平衡，需要经历几次平衡性调整，分别是哪种平衡性调整，最终得到的平衡二叉树是什么样子的？
欢迎你在留言区分享自己的思考。如果觉得有所收获，也可以把课程分享给更多的朋友一起交流进步，我们下节课见。
- 摩诃不思议 👍（0） 💬（1）
"平衡二叉树也叫平衡二叉搜索树，英文名是 Balanced Binary Tree，简称 AVL 树（平衡树）。" 这里是一个明显的错误。 AVL 树是平衡二叉搜索树的其中一种实现。😅
2023-06-18 - ꯭@꯭T꯭ 👍（2） 💬（0）
1. 全部按照二叉查找树的方式插入 2. 右旋转point 12 3. 左旋转point 7 4. 左旋转point 8 5. 右旋转point 3，左旋转point 1 总共旋转了4次： 7 / \ 4 10 / \ / \ 2 6 8 11 / \ / \ \ 1 3 5 9 12
2024-07-07