二叉树算法 - 平衡二叉树的构建实现过程演示
- 1 min数据结构与算法系列（三十三）
我们在上一篇文章中分享了平衡二叉树的定义和实现原理，这一节我们来演示如何通过代码实现平衡二叉树，最后分析下平衡二叉树的算法复杂度。
实例演示
在开始之前，我们先通过一个对比来加强理解，在没有介绍平衡二叉树之前，你可能会构造出这样的一棵二叉树：
虽然这也是一棵二叉排序树，但是层数达到 8，显然可以通过平衡二叉树来降低层数，提高性能，如果把它转化为二叉排序树，会是这个样子：
层数降低了一半，变成了4层，显然性能要比之前要高。那么这个平衡二叉树是怎么构建的呢？假设插入节点的顺序是{3,2,1,4,5,6,7,10,9,8}，两个节点之前不用考虑，我们从第三个节点开始分析：
插入第三个节点 1 时，左子树高度是2，右子树高度是 0，高度差的绝对值是 2，不符合平衡二叉树的要求，需要把以 3 为根节点的子树进行右旋，到右图那个样子，左右子树高度差为 0，符合平衡二叉树要求，完成调整。同理，插入第四个节点 4 的时候，左右子树高度为 -1，符合平衡二叉树要求，继续插入第五个节点，此时又不符合平衡二叉树的要求了，这个时候右子树比较高，需要左旋：
旋转的时候以最小不平衡子树为单位，此时最小的不平衡子树是3、4、5节点构成的子树，我们以4为中心进行左旋，将树结构调整为右图所示的样子，满足了平衡二叉树的要求，停止调整。注意到我们每次新增节点的时候，会调整以每个节点为根节点的左右子树的高度差，然后从最小子树开始进行调整，直到以每个节点为根节点的子树符合平衡二叉树的要求，这样整棵树就符合平衡二叉树的要求了。
继续增加节点，当插入节点 6 时，发现根节点 2 上维护的高度差值为 -2，又不满足平衡二叉树了，这个时候，需要以 2 为中心对树进行左旋，最终调整为右图所示的结构满足平衡二叉树要求（右子树中旋转到根节点的节点对应子树需要移到旋转后二叉树的左子树中）：
继续增加节点 7，此时以 5 为根节点的最小子树不满足平衡二叉树的要求了，需要左旋：
继续增加节点 10，满足平衡二叉树要求，再插入节点 9，又不满足了：
这个时候，情况有点微妙，不像我们之前旋转的时候时候处理情况都比较简单，单纯左转满足不了需求，需要先将以10作为根节点的子树做一次右转，再将以7为根节点的子树做一次左转，让这棵不平衡子树转化为平衡子树：
这样整棵二叉树就满足平衡二叉树的要求了：
最后，我们插入节点8，此时情况和刚才类似，这个时候，我们以 9 为根节点对子树进行右旋，再以6为根节点对子树进行左旋，最终达到平衡状态：
总结一下，大体的思路是平衡因子BF的值大于1时，右旋，小于-1时左旋，如果最小不平衡子树的BF值和其子树的BF值符号相反时，需要先将子树进行旋转使两者 BF 值符号相同，再旋转最小不平衡子树。我们将单纯的左旋、右旋叫做单旋处理，将需要两次旋转处理的操作叫做双旋处理。
我们在下一篇教程中将上述实例演示转化为具体实现代码。