12-平衡二叉树
平衡二叉树
平衡二叉树就是对二叉查找树的优化升级，它要求每个节点的左右子树的高度相差不大于1
1.平衡二叉树的查找
平衡二叉树和二叉排序树的查找是一摸一样的。
2.平衡二叉树的顺序输出
平衡二叉树的中序遍历和二叉排序树一样，都是可以输出一个有序的数列。
3.平衡二叉树的插入
平衡二叉树在插入数据时，当发生了高度的不平衡时，会采取4种旋转操作：LL,RR,LR,RL（左左，右右，左右，右左）旋转，我们来一一分析这4种旋转方式。
RR调整
针对右孩子的右子树引起的不平衡
tree12.jpg
调整策略
- 右孩子c左上旋转作为根节点
- 根节点a左下旋转作为c的左子树
- c的左子树作为a的右子树
tree8.jpg
LL调整
针对左孩子的左子树引起的不平衡
tree13.jpg
调整策略
- 左孩子b右上旋转作为根节点
- 根节点a右下旋转作为b的右子树
- b的右子树作为a的左子树
tree9.jpg
LR调整
针对左孩子的右子树引起的不平衡
tree14.jpg
调整策略
- 根节点的左孩子进行一次RR调整
- 根节点进行一次LL调整
tree10.jpg
RL调整
针对右孩子的左子树引起的不平衡
tree15.jpg
- 根节点的右孩子进行一次LL调整
- 根节点进行一次RR调整
tree11.jpg
平衡调整的总结
现在我们将平衡二叉树的调整归纳成一种简单且好理解的记忆方式
- LL失衡，我们称之为LL调整，策略是对产生失衡的节点进行两次右右旋转，第一次是对失衡节点的左孩子进行右上旋转，第二次是对失衡节点进行右下旋转。
- RR失衡，我们称之为RR调整，策略是对产生失衡的节点进行两次左左旋转，第一次是对失衡节点的右孩子进行左上旋转，第二次是对失衡节点进行左下旋转。
- LR失衡，我们称之为LR调整，策略是对产生失衡的节点进行左右旋转，第一次是对失衡节点的左孩子进行LL调整，第二次是对失衡节点进行RR调整。
- RL失衡，我们称之为RL调整，策略是对产生失衡的节点进行右左旋转，第一次是对失衡节点的右孩子进行RR调整，第二次是对失衡节点进行LL调整。
注意点，LL失衡和RR失衡直接两次旋转，而LR失衡和RL失衡，是分别进行两次LL和RR的组合调整。
实战演练
现在我们有一关键字序列16,3,7,11,9,26,18,14,15，我们来逐个插入构建一棵平衡二叉树。
- 插入数字16，直接插入
tree31.jpg
2.插入数字3，插入后不失衡，所以不调整。
tree32.jpg
3.插入数字7，插入后如左图，发现失衡，失衡点是16，此时的失衡是LR失衡，根据总结规律，先对失衡点的左孩子进行RR调整，然后再对失衡点进行一次LL调整。
tree33.jpg
4.插入数字11，插入后，不失衡。
tree34.jpg
5.插入数字9，插入后如左图，发现失衡，此时失衡节点有两个节点16和节点7，因为代码设计是递归的判断失衡，所以从从下往上的调整，所以对失衡点16调整，此时16的失衡是LL失衡，先对失衡点16右孩子进行一次LL调整，发现竟然平衡了。所以不用继续调整了。
tree35.jpg
6.插入数字26，插入后，节点7发生了失衡，失衡是RR失衡。所以进行RR调整。
tree36.jpg
7.插入数字18，此时节点16出现了RL失衡，所以进行RL的调整策略。
tree37.jpg
8.插入数字14，此时二叉树平衡。
tree38.jpg
9.插入数字15，此时节点16发生了LR失衡，进行LR调整。
tree39.jpg
好了，上面就是一个完整的插入过程，可能你会注意到一个特殊情况，就是再插入一个节点时，平衡二叉树失衡点会不只一个，这个时候选择哪个进行调整？结合代码的思路分析，因为二叉树是递归创建的，它是由根节点往叶子节点向下递归创建的，所以检测平衡只能是逆向的，由靠近叶子的向根节点逐层调整，当发现平衡时，就不用调整了。
4.平衡二叉树的删除
平衡二叉树的删除操作分为三大部分，第一大部分是先找打这个节点，第二大部分是按照二叉排序树的删除规则进行删除(可看前面二叉排序树),第三大部分是从该删除点一直上溯到根节点逐个的判断是否失衡，根据失衡条件进行调整平衡二叉树。下面是步骤
- 按照二叉排序树的查找规则，去找待删除的节点，没找到直接退出。
- 根据二叉排序树总结删除规则的三条，去选择对应的删除步骤进行删除操作。
- 从删除该节点的位置开始，一直上溯到根节点，判断是否失衡，如果失衡根据对应失衡，进行相应的调整处理。
删除演示
1.删除26，如下图所示，元素26无左右孩子，直接删除，从此处开始，上溯到根判断是否失衡，发现18节点失衡，是LL失衡，进行LL调整，后面到根都平衡，不用调整。
tree45.jpg
2.删除15，如下图所示，按照规则，15左右孩子都有，所以可以先向左走一步，再一直向右走，直到此节点无右孩子，来到了14，将14放在待删除的15位置上，如下图中间，此时从该点开始回溯到根进行调整，发现14失衡，和RL失衡，进行RL调整策略。此时发现调整完毕结束。
tree46.jpg
3.删除18，如下图所示，18只有一个左孩子16，按照删除规则，将该左孩子直接放在待删除的18位置上。此时整个二叉树上溯到根节点都是平衡的，不用调整，结束。
tree47.jpg
删除操作也讲述完毕，好累。大家多看看步骤，根据步骤去画画图就可以很好的理解了。
