二叉平衡树构建图解（AVL树二叉平衡树详解与实现）
二叉平衡树构建图解（AVL树二叉平衡树详解与实现）出现这种情况的原因是节点的 右侧的右侧较深 这时候 不平衡节 点需要 左旋 。再细看过程。RR平衡旋转(左单旋转)这只是针对在底部，对于可能出现的平衡要首先搞清楚：所以针对四种不平衡， 可能出现在底部，也可能出现在头，也可能出现在某个中间节点导致不平衡。 而我们只需要研究其首次不平衡点， 解决之后整棵树即继续平衡 。当然，在实际解决肯定会带上 递归 的思想解决问题。#四种平衡旋转方式
AVL树概念
- AVL树是 带有平衡条件的二叉查找树 。这个平衡条件必须要 容易保持 。而且要保证它的深度是O(logN).
- AVL的条件是左右树的高度差（ 平衡因子 ）不大于1；并且它的每个子树也都是平衡二叉树。
- 对于平衡二叉树的最小个数， n0=0 ; n1=1 ; nk=n(k-1) n(k-2) 1 ;(求法可以类比斐波那契！)
难点：AVL是一颗二叉排序树，用什么样的规则或者规律让它能够在 复杂度不太高 的情况下 实现动态平衡 呢？
不平衡概况
如果简单的以单节点看，大致有上面 四种 情形，并且他们的最后结果也是有的有所相近。只是：上下会变动。 该在左面的还在左面，改在右面的还在右面 。
这只是针对在底部，对于可能出现的平衡要首先搞清楚：
所以针对四种不平衡， 可能出现在底部，也可能出现在头，也可能出现在某个中间节点导致不平衡。 而我们只需要研究其首次不平衡点， 解决之后整棵树即继续平衡 。当然，在实际解决肯定会带上 递归 的思想解决问题。
#四种平衡旋转方式
RR平衡旋转(左单旋转)
出现这种情况的原因是节点的 右侧的右侧较深 这时候 不平衡节 点需要 左旋 。再细看过程。
- 再左旋的过程中， root(oldroot) 节点下沉， 中间节点(newroot) 上浮.而其中 中间节点(newroot) 的右侧依然不变。
- 它上浮左侧所以需要指向 根节点(oldroot) (毕竟一棵树)。但是这样 newroot 原来左侧节点 H 空缺。而我们需要仍然让 整个树完整并且满足二叉排序树的规则 。
- 而刚好 本来oldroot右侧指向newroot变成oldroot被newroot左侧指向 。所以 oldroot右侧空缺 ，刚好这个位置 满足 在oldroot的右侧。在newroot的左侧。 .所以我们将H插入在这个位置。
- 其中H可能为 NULL 。不过不影响操作！
而左旋的代码可以表示为：
LL平衡旋转(右单旋转)
而右旋和左旋相反，但是思路相同，根据上述进行替换即可！
代码：
RL平衡旋转(先右后左双旋转)
产生不平衡的条件原因是：
- root节点右侧左侧节点的深度高些 ，使得 与左侧的差大于1 .这个与我们前面看到的左旋右旋不同的是因为它的结构不能直接变一下就可以完成。
- 因为对于右左结构， 中间的最大，两侧的最小 。但是下面的比上面大( 下面在上面右侧 )所以如果平衡的话，那么 右左的R.L 应该在中间，而 R 应该 在右侧 。原来的root在左侧。
- 所以节点的变化浮动比较大，而且需要 妥善处理各个子节点的移动 使其满足 二叉排序树的 性质！
- 期间考虑树高度变化即可！
这种双旋转其实也很简单。不要被外表唬住。基于前面的单旋转，双旋转有 两种 具体 逻辑思路 。
思路1：两次旋转RR LL
根据上图所圈的，先对底部使得底部的大小关系变化，使其在满足二叉平衡树的条件下还满足RR结构的二叉树。所以只需要对 右节点R先进行右旋 再对ROOT进行左旋即可。
思路2：直接分析
根据初始和结果的状态，然后分析各个节点变化顺序。手动操作这些节点即可！
- 首先根据 ROOT R R.L 三个节点变化。R.L肯定要在最顶层。左右分别指向ROOT和R。那么这其中 R.left，ROOT.right 发生变化(原来分别是R L和R)暂时为空。而刚好根据 左右大小关系 可以补上 R.L的左右节点 。
- 这样思考整棵树也可以完成平衡，但是要考虑 树的高度变化 。
代码为：(注释部分为方案1)
LR平衡旋转(先左后右单旋转)
根据上述RL修改即可
java代码实现
- 首先对于节点多个 height 属性。用于计算高度(平衡因子)
- 插入是 递归插入 。递归一个来回的过程，去的过程进行插入。 回的过程进行高度更新。和检查是否平衡。 不要写全局递归计算高度，效率太低下。事实上高度变化只和插入和平衡有关，仔细考虑即不会有疏漏！总结测试情况：
- AVL的理解需要时间，当然笔者的AVL自己写的 可能有些疏漏 ，如果有问题还请各位 一起探讨 ！
- 当然，除了插入，AVL还有 删除 等其他操作，(原理相似。删除后平衡)有兴趣可以一起研究。
