数据结构(八)--平衡二叉树

该来的总会来，平衡二叉树果然又来了…

出现背景 前文已经研究过普通的二叉树， 为什么要用二叉树呢？因为二叉树的结构可以实现二分法查找的效果。

你比如前文介绍的满二叉树：如下图所示，

如果你想要查找4号元素，你只需要遍历3次即可。

所以在理想情况下，二叉树可以优化遍历。遍历时的时间复杂度基本上为0(logn)。但是考虑一种情况，在按顺序插入数据的情况下，二叉树会退化成链表结构 如下图所示：

此时，因为是按照一定顺序插入，所以最后形成的二叉树结构是呈一种线性的，相当于一个有序的链表。

此时如果遍历查询，在时间复杂度上和链表是等同的(0(n))。

那如何避免二叉树退化呢？首先考虑下不让二叉树退化是什么意思？也就是目的

不让二叉树退化是说即便是在顺序插入的情况下，也不能让其成为线性结构。这就是目的，也就是说避免二叉树在某些情况下成为线性链表

那么为了实现这个目的，应该如何做呢？尽量将其调整为满二叉树形式或者向满二叉树靠近，但是满二叉树对每层的节点个数都有固定要求，如果单纯的就是调整为满二叉树也不现实。

所以我们要将二叉树尽量调整为左右子树高度差最多不超过1的平衡二叉树。

这也就是平衡二叉树的作用了。 所以，接下来为了避免二叉树的退化，我们需要明白二叉树什么时候需要调整，要怎么调整。 也就是做两件事

when?何时调整？判断二叉树是不是平衡二叉树

how?如何调整？将非平衡的二叉树调整为平衡二叉树

识别平衡二叉树 既然要将不平衡的二叉树进行调整，那么什么样的树是平衡的？什么样的树是不平衡的？

一定要按照平衡二叉树的性质来区分判断：左子树和右子树的高度差不能超过1 如下图所示

按照性质来判断，看二叉树中的每个分支节点是否平衡

图1：三个节点中两个叶子节点0,2，叶子节点是说没有子节点的节点，所以叶子节点没有左右子树，所以叶子节点永远是平衡的，不需要考虑。有一个分支节点1是根节点，左子树高度为1，右子树高度为1，高度差为0。所以是平衡二叉树

图2：共有四个节点，其中有两个叶子节点0,3是平衡的不需要考虑。分支节点有1和2，需要分析其平衡性.针对节点1来说左子树高度是1，右子树高度是2，高度差为1，所以节点1是平衡的。针对节点2来说左子树高度是0，右子树高度是1，高度差是1，所以节点2是平衡的.既然除叶子节点外其他节点都是平衡的，所以图2是平衡的。

图3：所有节点都是平衡的，所以是平衡二叉树。不再仔细分析，可以自己尝试。

接下来再来分析几个不是平衡二叉树的二叉树

图4:0,5是叶子节点不需要考虑。节点1的左子树高度为1右子树高度为0所以为平衡节点。节点2左子树高度为2右子树高度为3所以为平衡节点。节点3左子树高度为0右子树高度为2所以为非平衡节点。节点4左子树高度为0,右子树高度为1，所以为平衡节点。综上图4不是平衡二叉树。

所以，看一个二叉树是不是平衡的，就看二叉树的每个节点是不是平衡点，也就是看每个节点(叶子节点除外，不需要判断)的左右子树的高度差是不是小于1.

调整二叉树 在正确的区分了二叉树是不是平衡二叉树后，也就是我们明确了二叉树何时需要调整。那么接下来我们就要试着将不平衡的二叉树调整为平衡的二叉树。

也就是要掌握如何将非平衡的二叉树，调整为平衡二叉树

调整的做法不可能是增加节点或者是减少节点。而是对二叉树进行一个旋转的操作。

也就是说既然节点失衡，那就说明左右高度差大于1，此时可以通过旋转来让调整左右子树的高度。

旋转分为两种，左旋和右旋。何时左旋何时右旋呢？先来看个示例

先来声明一下，我这里的左旋和右旋意思是向左旋转还是向右旋转，也就是右旋表示顺时针旋转，左旋表示逆时针旋转。而不是指代的是左子树旋转或是右子树旋转。

左旋 如下图9所示：

图9中，最低失衡节点为2，失衡原因是因为节点4的存在。节点4位于失衡节点的右子树。所以对节点2进行逆时针旋转。

节点3代替节点2的位置，节点2作为节点3的左子节点，节点3原先的左子节点（如果有子节点）作为节点2的右子节点

右旋 如图6所示

图6中，最低失衡节点为节点2，失衡原因是因为节点0的添加。 节点0位于节点2的左子树，左子树高度为2右子树高度为0。

所以需要从左子树移动一些节点到右子树，也就是向右旋转。 将失衡节点2向右旋转，作为节点2的子节点1的子节点。

如图7所示，旋转后为平衡二叉树

前边的左旋和右旋是最基本的，简单的操作。而且也是针对简单的情况。

左子树右旋中：最低失衡节点的左子树比右子树的高度大于1，并且最低失衡的节点只有左子树，并且左子树中只有左子节点，没有右子节点

右子树左旋中，最低失衡节点的右子树比左子树的高度大于1，并且最低失衡的节点中只有右子树，右子树中只有右子节点。 来看一些复杂的情况

左子树失衡，失衡节点是右子节点 如图所示

按照之前的逻辑，最低失衡节点处于其父节点的左子树，那么就让左子树右旋。旋转后如图b所示，依旧不平衡而且问题也没有任何的改善。这种情况下应该怎么调整呢？

为什么拿最低失衡节点的子节点代替失衡节点位置不行？因为该子节点在左子树中的顺序不是出于中间位置，因为该子节点小于父节点，也小于其右子节点。所以让其右子节点代替父节点位置。如下图所示

同样，针对右子树失衡，失衡节点是左子节点的也很类似，就不再画出。

但前面这几种情况，都有一个特点，那就是失衡的节点都只有一个子节点，如果有两个子节点该如何处理？其实没啥影响，只要找准失衡节点和失衡原因即可。

总结 在调整二叉树时，要确认两个东西，一个是旋转方向，一个是旋转轴。

旋转方向共有两种，顺时针旋转和逆时针旋转，那么究竟是哪种旋转方式由什么决定？由最低失衡节点以及左右子树高度决定。也就是找到最低失衡节点和失衡原因。

如果节点失衡是因为左子树高度>右子树高度，那就说明需要把左子树的节点旋转到右子树，也就是向右旋转，即顺时针旋转

如果节点失衡是因为右子树高度>左子树高度，那就说明需要把右子树节点旋转到左子树，也就是向左旋转，即逆时针旋转。

旋转方向确定后，接下来就是确定旋转轴了，其实也就是找到用哪个节点来代替原先的最低失衡节点。

首先，失衡原因就是左右子树不平衡，我们需要尽量调整成以失衡节点为轴成对称的形状，那么也就是说我们是需要找到失衡节点所在子树的中间位置的节点，并让其代替失衡节点，找到中间位置后，就可以保证失衡节点所在子树可以成为平衡树。

其实理论上是这么说，但是实际操作起来也是挺困难的，为了更简单的实现，我们可以尽量找某个极值，这样只需要改变层数较多的那个子树即可。不理解的话接着看。

查找位置有个规律： 如果造成失衡的节点位于最低失衡节点的左子树中，那么就找到该左子树中的最大值节点，来代替最低失衡节点。

如果造成失衡节点位于最低失衡节点的右子树中，那么就找到该右子树中的最小值节点，来代替最低失衡节点。

可以通过前边儿的例子来来验证下理论。接下来举几个稍微复杂的例子来验证。

示例： 如图所示

首先找到二叉树的最低失衡节点为4，接下来找到二叉树的失衡原因是节点1的存在。节点1是位于节点4的左子树，所以是需要顺时针旋转。

接下来寻找旋转轴，也就是包括4在内的左子树的最大值。因为节点1是节点4的左子树中的节点，循环遍历左子树，找到最大值节点为3

分析完毕后，执行旋转过程

用节点3代替节点4的位置，也就是说节点3.parent=节点4.parent

节点3的左右子节点的确定：节点3的右子节点为4，左子节点为原先4的子节点2,调整后的二叉树如图b所示,但是仍旧是不平衡的，现在失衡节点为2

同理，因为失衡节点2的左子树失衡，所以找到左子树中的最大值，并用该节点代替2。该节点的右子节点为2，左子节点为2的左子节点0，也就是重复第二步的过程。调整后如图c所示，成功

所以啊，只要找准最低失衡节点以及旋转轴也就是需要替换最低失衡节点的节点，问题就迎刃而解了。

找最低失衡节点，那就是找从最底层（叶子节点层）往最高层（root层）中最先出现左右子树高度差大于1的节点。

找替代节点就是找极值点，如果是左子树失衡，那就找左子树中的最大值，因为当左子树失衡时就表示我们不需要处理右子树，所以找到左子树的最大值，之后把右子树赋给该节点的右子节点即可。

同理，如果是右子树失衡那就找右子树中的最小值。

ok,接下来分析完毕后就可以进行代码实现了。

但是本文还留了一个疑问，那就是如何寻找最低失衡节点。在找到最低失衡节点后，只需要找到对应的极值，并进行旋转。但难点依旧是最低失衡节点的确定