AVL树AVL树为平衡二叉树，是一种特殊的二叉树。
其左右子树均为平衡二叉树，并与左右子树高度之差的绝对值不超过1
注意：均衡二叉树是二叉树，是对二叉树排序树的改进，提高了检索效率。
AVL树的插入节点的根二叉树相同，遵循左小右大的原则。
但在插入过程中，每次插入新节点时，都需要检查新节点的插入是否会导致原平衡二叉树失去平衡，一旦失去平衡，就需要进行平衡调整。
为了判断一棵二叉树是否为平衡二叉树，引入了平衡因子的概念。 平衡因子对树节点为一个结点的平衡因子为其左子树的高度减去右子树高度的差。 要平衡二叉树，树的所有节点的平衡因子的值只能取- 1，0，1三个值。
当平衡二叉树变成不平衡树时，它会进行平衡调整。 平衡调整请参阅LL（左左）、RR（右右）、LR（左右）、RL（右左）
在进行平衡调整之前，需要了解最小衡子树的概念。
假设在平衡二叉树中插入新节点会破坏平衡二叉树的平衡，首先找到插入新节点后失去平衡的最小树，调整该树使其成为平衡子树。 值得注意的是，失去平衡的最小树调整为平衡子树后，不需要调整原来所有其他的不平衡子树，整个二叉树就变成平衡二叉树。所谓失去平衡的最小子树是以距离插入结点最近，且以平衡因子绝对值大于1的结点作为根的子树，又称为最小不平衡子树
例如：
注意：平衡调节的四种情况LL、RR、LR、RL是不平衡状态的描述，而不是调节过程的描述。
例如，LL (左)调整，即，使新插入的节点落到最小不平衡树的根节点的左(l )子树(左)上的不平衡状态的调整称为LL调整。
例如，将LR (左右)调整称为LR调整，即调整不平衡状况，使新插入的节点落到最小不平衡树根节点的左(l )个子树(左)上。
其他RR和RL都是如此。
以上是二叉树发生不平衡的情况，下面就如何处理不平衡，即进行平衡调整的方法进行说明。
在此之前，还需要说下左转和右转：
33558 www.Sina.com/:逆时针旋转AVL树的两个节点x和y，使父节点取代自己的右边的孩子，使自己成为自己的左边的孩子。
这是一个奇怪的故事。 父亲被自己的右一个孩子逼到了下位，右一个孩子上位成功，为了弥补父亲缺少右一个孩子的悔恨，把自己的左一个孩子给了父亲。
33558 www.Sina.com/:顺时针旋转AVL树的两个节点x和y，使父节点取代自己的左孩子，使自己成为自己的右孩子。
这也是个奇怪的故事。 父亲被自己的左孩子逼到了下位，左孩子上位成功，为了弥补父亲缺少左孩子的悔恨，把自己的右孩子给了父亲。
左旋转抽象图详细信息：
这里，a、b、c是最小不平衡子树的三个节点。 三角形表示这些节点下的子树。 这里，a节点的平衡因子为2，表示此二叉树已经不均衡。 将c节点及其子树作为一个整体处理，同时临时显示以c节点为根节点的子树是平衡的，然后换成三角形c，抽象表示b的左边子。 然后变成右转的标准形状。 通过上面的右转方法调整平衡。 平衡调整成功，调换三角形c，检验平衡因子，平衡调整成功。
节点的实际操作如下。
右旋转抽象图详细信息：
其中a、b、c是最小不平衡子树的三个节点，三角形表示这些节点下的子树，其中a节点的平衡因子为-2，表示此二叉树不平衡。 将c节点及其子树作为一个整体处理，同时临时显示以c节点为根节点的子树是平衡的，然后换成三角形c，抽象地表示b的右边子代。 然后是左转的标准形状。 通过上面的左转方法调整平衡。 平衡调整成功，调换三角形c，检验平衡因子，平衡调整成功。
节点的实际操作如下图所示。
LL调整，也叫右单旋转调整抽象图详细信息：
表示lr调整的情况。 这里，a、b、c是最小不平衡部分树的三个节点，三角形表示这些节点下的部分树。 其中a节点的平衡因子为2，表示此二叉树已经不平衡。 把绿框里的东西当作一个东西对待。 即三角形BC。 将三角形1、2、3视为一体，暂不进行处理，作为三角形BC。 处理三角形BC内的情况。 即左旋转，旋转完成。 将三角形BC旋转后的内容还原，即融合的结果。 将绿框内的东西视为一体，右转时为三角形b。 进行右转，旋转完成。 将三角形b的内容恢复到种绿色框的内容，完成平衡调整。
节点的实际操作如下。
RR调整，也叫左单旋转调整抽象图详细信息
解： ①表示RL调整的情况，其中A、B、C是最小不平衡子树的三个结点，而三角形代表这些结点下的子树，其中A结点的平衡因子为-2，表示该二叉树已经不平衡。②把绿色框内的当成一个整体来处理，即三角形BC。③把三角形2、3、4当成一个整体，暂时不进行处理，设为三角形BC。④对三角形BC内的情况进行处理，即右旋转，旋转完成。⑤恢复③种三角形BC旋转后的内容，即融合④的结果。⑥把绿色框内的当成一个整体，就是左旋转的情况，设为三角形B。⑦进行左旋转，旋转完成。⑧将三角形B的内容恢复为⑥种的绿色框内容，完成平衡调整。
二叉平衡树删除结点跟二叉排序树删除结点是用同样方法处理的，不过删除后要考虑树是否平衡的问题，如果遇到失衡问题同样可以考虑用上面四种情况进行解决。
参考链接：
漫画：什么是AVL树？（修订版）