平衡二叉树之节点删除
教书育人很重要，但也时刻告诫自己不要忘记IT男这个身份，再忙也要抽时间学习编程知识以及总结过去积累的经验。计算机算法，操作系统、计算机网络以及编译原理是成为计算机高手的内功。可能大多数人会觉得开发App，电脑软件，写个网站等这才是高手，其实相反，这些码农往往拿不到更高的薪水。掌握算法以及计算机底层的原理，是助你迈上更高台阶的关键，也是你拿到鹅厂这样的互联网大公司程序员岗位offer的必备技能【IT男并不是一定会修电脑，我们忙着打代码呢】。
讲了这么多废话，也只是跟大家骚聊下算法的重要性。不久前小编分享了平衡二叉树的创建以及插入操作，类似于添加操作，从平衡二叉树中删除节点也分为两步，第一步完成节点的删除，第二步找到因为删除而导致不满足平衡二叉树要求的子树并对其进行调整。虽然平衡二叉树的结点删除操作的代码比较复杂，但是经过认真分析后，可以发现删除过程只有以下3种情况：
① 被删除的节点为叶子节点，就找到了要删除的节点
② 被删除的节点为只有一棵子树的节点就找到了要删除的节点【也就是被删的结点只有左子树或只有右子树】
③ 被删除的节点既有左子树，又有右子树
我们需要知道这么一点，左子树上节点的删除相当于我们在右子树上插入了一个新节点，右子树上节点的删除相当于在左子树上插入了一个新节点，根据这一点，我们进行判断并采取对应的平衡调整操作。
我们按照这三种情况来一步步分析：
（1）被删的结点是叶子结点
我们来看第一个例子
图1
我们来删除节点14，发现这是个叶子节点，直接删除，可以发现节点14的父节点10达到平衡，再往上，发现根节点20也处于平衡状态，平衡因子为0。故删除节点后不需进行任何调整，得到的二叉平衡树如下：
图2
我们来看例子2
图3
我们将上图中的节点7删除，可以发现这是一个叶子节点。我们直接删除。得到下面的二叉树。
图4
可以发现，原本节点7的父节点8的平衡因子为0，达到平衡。故继续向上查找，发现节点8的父节点20的左子树高度与右子树高度差值为2，也就是该节点20失衡。需要进行调整。这个地方要进行何种调整呢？我们说过，在左子树上删除节点其实就相当于在右子树上插入节点。我们找到节点20的右子树上的子节点30，发现节点30的左子树高度比右子树高，这就相当于在节点20的右子树节点30的左子树下插入了一个新的节点。这就需要进行RL型调整。先进行右旋调整，将节点30绕节点25顺时针旋转，得到下图。
图5
接下来进行左旋，得到下图，这就是调整后的树的形状。
图6
我们来看例子3
图7
我们将上图中节点8删除，得到下图：
图8
可以观察到该树处于失衡状态。节点20处于平衡状态，节点25的左右子树高度差为2，需要进行调整。刚我们说过，在左子树上删除节点其实就相当于在右子树上插入节点。但要如何调整还取决于该失衡节点的右孩子的左右子树的高度差。我们找到节点20的右子树上的子节点30，发现节点30的左右子树高度一样，因此我们只需进行RR型调整，也就是左旋一次，根据节点30进行逆时针旋转。调整后的树如下：
图9
故删除叶子节点的几个步骤如下：
① 将该结点直接从树中删除；
② 其父节点的子树高度的变化将导致父结点平衡因子的变化，通过向上检索并推算其父结点是否失衡；
③ 如果其父结点未失衡，则继续向上检索推算其父结点的父结点是否失衡...如此反复②的判断，直到根结点；如果向上推算过程中发现了失衡的现象，则进行④的处理；
④ 如果其父结点失衡，则判断是哪种失衡类型[LL、LR、RR、RL]，并对其进行相应的平衡化处理。如果平衡化处理结束后，发现与原来以父节点为根结点的树的高度发生变化，则继续进行②的检索推算；如果与原来以父结点为根结点的高度一致时，则可说明父结点的父结点及祖先结点的平衡因子将不会有变化，因此可以退出处理。
（2）被删的结点只有左子树或只有右子树
我们来看看例子1
图10
在该平衡树中，我们要删除的节点是值为29的节点。我们用该节点的左子树替换该节点，然后删除值为29这个节点。得到树的形状如下：
图11
可以看到该树已经处于平衡状态。不需要进行处理。
如果我们将值为40的节点删除，先用其右子树与之替换，然后删除该节点，可以得到如下的形状：
图·12
接下来的操作其实也就是删除叶节点的操作。
可以发现该树失衡，删除右子树的节点相当于在左子树上插入新的节点。我们找到值为50的节点，找到其父节点，节点值为30。然后找到其左孩子，节点值为25。发现该节点的右子树比左子树高度高，也就是相当于在左子树的右子树上插入节点。因此我们这里要进行LR型调整。先进行左旋，也就是绕值为29的节点进行逆时针旋转，得到下图：
图13
接下来进行右旋，得到下图。
图14
因此删除节点有左子树或右子树的处理步骤如下：
① 将左子树（右子树）替代原有删除结点的位置；
② 结点C被删除后，则以C的父结点B为起始推算点，依此向上检索推算各结点（父、祖先）是否失衡；
③ 如果其父结点未失衡，则继续向上检索推算其父结点的父结点是否失衡...如此反复②的判断，直到根结点；如果向上推算过程中发现了失衡的现象，则进行④的处理；
④ 如果其父结点失衡，则判断是哪种失衡类型[LL、LR、RR、RL]，并对其进行相应的平衡化处理。如果平衡化处理结束后，发现与原来以父节点为根结点的树的高度发生变化，则继续进行②的检索推算；如果与原来以父结点为根结点的高度一致时，则可说明父结点的父结点及祖先结点的平衡因子将不会有变化，因此可以退出处理
（3）被删的结点既有左子树又有右子树
处理最初的步骤如下：
① 如果该节点的平衡因子为0或者1，则找到其左子树中具有最大值的节点max（我们只讨论有序平衡二叉树，并且有序平衡二叉树中任意一个节点的左子树上的所有节点的值小于该节点的值，右子树上所有节点的值大于该节点的值），将max的内容与x的内容交换（只替换保存的真正的数据，不替换指针，平衡因子等用于管理目的的信息），并且max即为新的要删除的节点。由于树是有序的，因而这样找到的节点要么是一个叶子节点，要么是一个没有右子树的节点。
② 如果该节点的平衡因子为-1，则找到其右节点中具有最小值的节点min，将min的内容与x的内容交换，并且min即为新的要删除的节点。由于树是有序的，因而这样找到的节点要么是一个叶子节点，要么是一个没有左子树的节点
通过上面的操作后，我们需要对值替换后的节点进行删除，根据树的性质，我们可以得到我们要输出的节点只有两种情况，叶子节点或者是只有一棵子树的节点。删除后的调整操作按照我们前面已经讲的两种方法去调整。
来看一个简单的例子：
图15
我们从该平衡树中删除节点20，我们分析得到节点20的平衡因子为1，因此我们从节点20的左子树中找到最大值，最大值为节点15。我们对两个节点的值进行替换。得到的树的形状如下所示：
图16
接下来删除节点20，得到下图。
图17
观察，发现原先删除的节点20的父节点10的平衡因子BF=2，处于失衡状态。因此需要对以10为根节点的子树进行调整【这个地方进行删除操作时，相当于在以10为根节点的左子树的右子树上进行插入操作】，也就是进行LR调整。要先进行一次左旋操作，得到下图
图18
再进行一次右旋操作。最后得到的树的形状如下：
图19
虽然平衡二叉树的结点删除操作的代码比较复杂，但是经过认真分析后，可以发现删除过程只有以上3种情况，牢牢把握住以上3点，理解并实现平衡二叉树的删除操作不是太难。
有误请指正，感激不尽。下面是一段简洁的代码，总代码上篇简书以有贴图，这里只放相关代码截图。
图20
