有时候我们蒙住眼睛就可以欺骗自己，世界很黑，很安全
前言
上一篇 数据结构预算法系列——查找(二) 主要讲的是二叉查找树，但二叉查找树在最坏（极不平衡）的情况下，查找效率也很低，所以我们的问题是：如何让二叉查找树平衡起来以提高查找的效率。本篇我们来认识查找效率较高的平衡二叉树（AVL树）。
认识平衡二叉树
平衡二叉树 ，是一种二叉排序树，其中每一个节点的左子树和右子树的高度差至多等于 1
平衡二叉树的前提是它必须是一颗二叉排序树，然后再加上一个高度平衡的条件。那怎么才算高度平衡呢？高度平衡就是指这棵树要么是一棵空树，要么它的左子树和右子树都是平衡二叉树， 左子树和右子树的深度之差的绝对值不超过 1 。我们将二叉树上结点的左子树深度减去右子树深度的值称为平衡因子 BF，那么平衡二叉树上所有结点的平衡因子只可能是 -1、0、1。 只要二叉树上有一个结点的平衡因子的绝对值大于 1，则该二叉树就是不平衡的。
来看一个例子：（图片摘自网络）
平衡二叉树实现原理
平衡二叉树构建的基本思想就是在构建二叉排序树的过程中，每插入一个结点时，先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树。在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
拿上图来说，在插入节点6的时候，检查到此时节点8的平衡因子为2，树失去了平衡，故此时的最小不平衡子树为以8为根节点的树 。我们需要调整最小不平衡子树各节点的关系，此时有左旋与右旋两种操作，即逆时针旋转与顺时针旋转。
对于上图由8-7-6组成的最小不平衡子树，我们采取右旋操作，如下图：
经过旋转，树又重新回到平衡状态。那么问题来了，什么时候采取左旋操作，什么时候又采取右旋操作呢？
这里是要着重介绍的地方，因为插入方式的不同，需要做不同的旋转操作。
左左局面（LL）
左子树左节点插入新节点，将P节点右旋
🔶：平衡因子； ⬜：节点名称。 下同
右右局面（RR）
右子树右节点插入新节点，将P节点左旋
左右局面（LR）
左子树右节点插入新节点，先将C节点左旋，再将P节点右旋
右左局面（RL）
右子树左节点插入新节点，先将C节点右旋，再将P节点左旋
总结
总共4中插入情况：无非就是左子树插入左右节点与右子树插入左右节点4种，P(parent)节点与C(children)节点的平衡因子为同号时，只需旋转P节点一次；P(parent)节点与C(children)节点的平衡因子为异号时，需旋转两次，且先旋转C节点再旋转P节点。
小记：
- 左左局面（
LL），P右旋； - 右右局面（
RR），P左旋； - 左右局面（
LR），C左旋，P右旋； - 右左局面（
RL），C右旋，P左旋；
节点删除
平衡二叉树的实现原理就是节点插入操作，查找操作同二叉排序树，都是采用二分查找法，最后就剩最麻烦的删除操作了。下面列举三种情况：
情况一：删除叶子节点，无影响
下图删除叶子节点5或3，都不会影响平衡，直接删除
情况二：删除叶子节点，失衡
下图若删除的是叶子节点8，删除后失衡，则需要旋转
情况三：删除内部节点
与二叉排序树的节点删除操作相同，用中序遍历结果中当前要删除节点的直接前驱或后继来替换，详细原因在上一篇《数据结构与算法系列——查找(二)之BST树》中删除操作小节已做过说明，不再赘述。同样替换节点后，也会出现两种情况：无影响和有影响。方便理解，以最小树结构配图理解：
无影响
删除节点
4，中序遍历下节点4的直接前驱为3，直接后继为5，直接替换，此种情况下无影响
有影响
删除节点
6，中序遍历下节点6的直接前驱为5，直接后继为8，直接替换，此种情况下有影响，需旋转要删除节点的平衡因子为
1要删除节点的平衡因子为
-1
我们从图中可以发现在删除内部节点时，这个替换节点的选择还是很重要的。
结语
关于平衡二叉树的理解，就到这里，如有错误或遗漏请大家指出。至于代码的实现，留坑，有时间和精力再搞。
本文使用 mdnice 排版
