(数据结构）平衡二叉树

概念：平衡树，又称AVL树，她也是一棵二叉查找树。
目的：为了将查找的时间复杂度保证在O(logN)范围内。
在AVL树中，每次插入或者删除某些数据之后，有时候需要对二叉树的高度做一些调整，就是为了保证平衡。这个平衡的要求是左右子树的高度差小于等于一，也就是内部的所有节点的左右子树的高度查都要小于等于一。
如图：

这个就符合平衡二叉树的要求；
再看下一个例子：

这个就不符合平衡二叉树的要求，因为A的左右子树高度差大于一，C的左右子树高度差也大于一，需要有所调整，才能符合要求。

那么如何调整呢？
我们要本着高度差小于等一的目的去调整，一共有四种方法：
调整二叉树首先要明白最小不平衡子树，是指最接近平衡因子绝对值大于1的节点做根的子树。要找到哪一个节点是不平衡的，然后又是哪一个节点导致不平衡的发生，就是找这两个节点。如上图中，我们发现A是不平衡点，而 F 是导致不平衡的那个节点，那么做出调整后的效果是：

第一种调整规则：RR型（右右型）
不平衡点 C 在 被破坏平衡的 A 的右子树的右子树中，所以是RR型，我们只需要将左边补一个节点就好了，那么常见的操作是直接将 C 作为根节点，A 补在左子树，因为 A 小于 C ，所以就完成了。如上图

第二种调整规则：LL型（左左型）

不平衡点 C 在 被破坏平衡的 A 的左子树的左子树中，所以是LL型，我们只需要将右边补一个节点就好了，那么常见的操作是直接将 B 作为根节点，A 补在右子树，因为 A 大于 B ，符合查找树的要求，所以就完成了。如下图

第三种调整规则：LR型（左右型）

不平衡点 C 在 被破坏平衡的 A 的左子树的右子树中，所以是LR型，我们需要 C 作为根节点，A 补在右子树，因为 A 大于 C ，符合查找树的要求，所以就完成了。如下图

第四种调整规则：RL型（右左型）

不平衡点 C 在 被破坏平衡的 A 的右子树的左子树中，所以是RL型，我们需要 C 作为根节点，A 补在左子树，因为 A 小于 C ，符合查找树的要求，所以就完成了。如下图