AVL树——深入显出，一目了然

欢迎转载，请附出处：
http://blog.****.net/as02446418/article/details/47306419
以前总对AVL树有疑惑，到底什么时候左旋什么时候右旋，什么时候双旋，双旋和单旋的情况到底是什么样的呢？
看完本篇博客，相信你也能够一目了然了。
这里声明一下
左旋为：逆进针旋转。
右旋为：顺进针旋转。

情况：
（1）LL：插入一个新节点到根节点的左子树（Left）的左子树（Left），导致根节点的平衡因子由1变为2
（2）RR：插入一个新节点到根节点的右子树（Right）的右子树（Right），导致根节点的平衡因子由-1变为-2
（3）LR：插入一个新节点到根节点的左子树（Left）的右子树（Right），导致根节点的平衡因子由1变为2
（4）RL：插入一个新节点到根节点的右子树（Right）的左子树（Left），导致根节点的平衡因子由-1变为-2

处理办法：
（1）LL情况需要根右旋解决，如下图的情况1和2
（2）RR情况需要根左旋解决，如下图的情况3和4
（3）LR情况需要左右旋（先左子树左旋转，后根部右旋转）解决，如下图情况5和6
（4）RL情况需要右左旋（先右子树右旋转，后根部左旋转）解决，如下图情况7和8

直接上图。