二叉平衡树（AVL树）从演变、平衡、旋转加练习题逐步分析，看不会过来打我
想要了解AVL树，就得了解它是怎么演化来的，它并不是凭空创造的一个新数据结构，而是发现其他数据结构的不完美而演变过来的。
二叉查找树
我想二叉排序树结构的起源一定是来源于生活，二叉树只有一个根节点，每个节点最多有两个子节点，并且左边的子节点一定小于该节点，右边的子节点一定大于该节点。
二叉查找树的前提是数据是有序的，假如我要查找0002这个值，那我需要遍历3次，也就是树的深度，每遍历一层，数据就减少一半，所以查找的时间复杂度为O(logn)。
但下面这种情况就让查找的时间复杂度退化到了O(n)：
为了解决这个问题，平衡二叉树诞生了，也叫AVL树：
AVL树（平衡二叉树）
平衡二叉树，平衡至关重要，那么什么是平衡呢？
假设有一棵树，它的结构如下图：
它的左边树的高度left_height = 1，右边树的高度right_height = 2，高度差right_height - left_height = 1，如果高度差小于2，那么说明该树就是平衡的，再看下面这个图：
它的左边树的高度left_height = 1，右边树的高度right_height = 3，高度差right_height - left_height =2，如果高度差不小于2，那么说明该树就是不平衡的。
平衡（Balance）：
两边树的高度差小于2。
当发生不平衡的情况，怎么办呢？怎么让树平衡呢？所以就有了旋转：
####旋转：
- 左旋
- 右旋
- 先左后右
- 先右后左
右旋
-
例1：
先来看右旋，如下图：
这棵树是不平衡的，左边的高度是2，右边是0。根节点0005顺时针旋转（右旋）90度，变成如下图：
- 例2：下面这棵树也是不平衡的，左边高度是3，右边高度是1。
根节点0005顺时针（右旋）旋转90度，如下图：
- 例3： 下面这棵树相比前两个复杂一些，也是不平衡的，左边高度是3，右边高度是1。
根节点0008顺时针旋转（右旋）90度，如下图：
再来个动图，你就都明白了：
左旋
-
例1
上面这种情况，也是不平衡的，右边的高度是2，左边高度是0，根节点逆时针旋转（左旋）90度：
-
例2：
以上也是不平衡的，右边的高度是3，左边高度是1，根节点0009逆时针旋转（左旋）90度：
-
例3：
上面的图中，左边的高度是1，右边的高度是3，所以也是不平衡的，根节点逆时针旋转（左旋）90度：
再来个动图：
先右旋再左旋
-
例1：
先右旋，0012右旋到0011的右下方，0008再连接到0011上：
上图这种情况在左旋的例1中出现过，大家应该记得吧
再左旋，根节点0008逆时针旋转90度：
-
例2：
先右旋，0018顺时针旋转90度，0009再连接到0016上，
以上这种情况在左旋例2演示过
再左旋，根节点0009逆时针旋转90度：
-
例3
以上这张图明显是不平衡的，0018节点先右旋，得到如下图：
再左旋，0009根节点左旋：
总结：先右旋的时候，找到超长的这条链，根节点的下一节点就是要右旋的节点，左旋的时候就是根节点左旋。
先左旋再右旋
-
例1：
上图中，该树是不平衡的，问题发生在0006身上，所以找到这条链上的根节点的下一个节点，也就是0005，先左旋：
上图依然是不平衡的，再右旋：
-
例2：
先找到问题链 0050->0040->0045->0042，然后找到这条链的根节点的下一节点0040，左旋：
还是不平衡，再找到根节点0050，右旋：
-
例3：
如上图，依然是不平衡树，首先找到问题链0050->0040->0045->0048，再找到该链路的根节点的下一节点0040，左旋：
依然不平衡，找到根节点0050，右旋：
练习
假设依次插入12，4，1，3，7，8，10，9，2，11，6，5 画出最终的AVL平衡树
-
先插入12
-
再插入4
-
再插入1
-
再插入3
-
再插入7
-
再插入8
-
再插入10
-
再插入9
-
再插入2
-
再插入11
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2dx4TVd5-1596250767328)(https://tva1.sinaimg.cn/large/007S8ZIlgy1ghb3q42748j30te07pmy1.jpg")]
-
再插入6
-
再插入5
总结
AVL树（二叉平衡树）的演变、平衡、旋转到这里基本都说完了，下篇文章讲一讲红黑树。