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，我们来逐个插入构建一棵平衡二叉树。

1. 插入数字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

删除操作也讲述完毕，好累。大家多看看步骤，根据步骤去画画图就可以很好的理解了。