前言
在讲平衡二叉树（AVL）之前，需要先理清二叉搜索树BST（Binary Search Tree）的基本概念。二叉搜索树，重点记两条：
- 二叉。每个结点的度≤2，这也是“二叉”的由来。
- 左＜中＜右。左中右三个结点满足：左＜中＜右。同理可推断：左子树任意结点<中<右子树任意结点。
AVL
对于二叉搜索树BST，其平均效率为O(log n)，最坏情况为O(n)，就是说在给定的数据本来就有序的时候，直接构造的二叉搜索树就会变成链表，效率退化为O(n)。
如何避免这种情况呢？平衡二叉树（AVL）给出了答案。
平衡二叉树首先是二叉搜索树，其次满足所有节点的左子树高度与右子树高度之差的绝对值小于等于1，以此让树保持均衡。其中左子树的与右子树的差值称作平衡因子，AVL每个节点的平衡因子能且只能出现3个值（-1,0,1）。观察上图这棵树，根节点10的平衡因子为1，节点17的平衡因子为-1，所以这棵树是平衡二叉树。
再观察下面这颗树，结点10的平衡因子是-2，所以这颗树不满足AVL的要求。
AVL的构建、插入、删除过程与二叉搜索树一致。在构建过程中，当结点的平衡因子不在-1,0,1中时，称为失衡。失衡其实很好理解，失衡失衡，失去平衡，就像跷跷板，左边一个小孩，右边一个大人，跷跷板就会失衡；或者是天平，只有两边重量一致，才会保持平衡。失衡的时候，需要一系列旋转操作进行调整，只有在平衡的时候，达到AVL，二叉树的查找效率才是最优的。调整的目标可以理解为降低整体二叉树的高度，找到新的平衡。调整的策略就是旋转，左旋和右旋。
左旋
AVL有两个基本的旋转操作，称为左旋和右旋。左旋也称为逆时针旋转，下图结点4是失衡的状态，平衡因子为-2。
此时可以将失衡节点左旋，即逆时针旋转，结点4成为其原右子结点7的左子结点，得到下面调整之后的树。4-7原来的关系为“中右”，现在的关系为“左中”。
此时这棵树是平衡的，调整前后，都是满足BST的要求的树。其中序遍历（左中右）的结果是一样的。但是旋转过后，明显这棵树更加均衡了，即树的高度降低了。
复杂点的左旋
刚刚的树是很简单的，接下来看一个复杂点的。下图结点5的平衡因子是-2。此时需要左旋，但是结点5是有左子结点的，结点5的右子结点9，也是有左子结点6的，此时左旋怎么操作呢？
此时左旋结点5的时候，实际关注的，有3个结点：结点5，结点9（结点5的右子结点），结点6（结点9的左子结点）。此时的操作可概括如下：
- 将结点5置为结点9的左子结点
- 将结点6置为结点5的右子结点
得到下图的树。按照二叉搜索树的性质，每个结点可以有左右子结点，每个“左中右”的大小顺序为“左＜中＜右”，当我们需要将某一结点（如结点5）的高度降低时，将其置为其右结点的左子树，是不违背“左＜中＜右”的原则的。
对于结点5，结点5与结点9原来的关系为“中(5)-右(9)”，现在变为“左(5)-中(9)”，左中右变更为左中右，中右和左中都符合“左＜中＜右”的原则。记住左中右变更为左中右，结点5在这个关系中由中变为左，也能更好的帮助我们理解左旋的名称由来。
对于结点6，其原本是原结点9的左子结点，也属于原结点5的右子树，可以概括为：“结点6在结点5的右侧，结点6在结点9的左侧”，有一条规则，“冲突的左孩变右孩”，怎么理解呢？结点5需要变更为结点9的左孩，结点9有一个左孩结点6，此时就冲突了，因此结点6变更为结点5的右孩。参照冲突的左孩变右孩处理，我们维持了“结点6在结点5的右侧，结点6在结点9的左侧”这一关系。
左旋，冲突的左孩变右孩这条规则的理解非常重要，左旋操作难点就是冲突结点的处理，只要理解了这条规则，所有的左旋操作都不再困难。看下图，总结一下，结点5出现了平衡因子等于-2，不满足AVL性质（平衡因子的绝对值小于等于1），需要对节点5进行左旋操作，左旋操作的要义为：待旋转结点逆时针旋转，其与原右子结点关系变化为：中右->左中，同时冲突的左孩变右孩，最终得到调整之后的树。
右旋
接下来我们看右旋，下图结点10的平衡因子=2，有左子树而无右子树。
此时我们需要将结点10向右旋转，或者说顺时针旋转，将结点10变成其左结点7的右子结点。那么7和10的关系由左中变成中右，其总体的“左中右”大小关系是保持不变的。
复杂点的右旋
如图结点14处于失衡的状态，其平衡因子为2。结点14有左子树，且其左子结点有右子结点，直接右旋会产生冲突。此时我们应该如何右旋呢？
参照左＜中＜右的原则，当结点14右旋时，结点14会变成其结点6的右结点，结点9（原本为结点6的右子结点）即成为了结点14的左子结点，得到如下的树。此处结点9的变化是比较大的，结点9在此次旋转中也被称为冲突的结点，它的位置被结点14占了，对于冲突结点9的处理，同样有一个口诀“冲突的右孩变左孩”。
此刻我们总结本地对于结点14的处理，当结点14的平衡因子大于1的时候，对节点14进行右旋操作：
- 结点14变成结点6的右子结点
- 结点9变成结点14的左子结点
至此，基本的旋转已经搞清楚了，可以概括为：左旋，逆时针旋转，冲突的左孩变右孩；右旋，顺时针旋转，冲突的右孩变左孩。那么新的问题来了，什么时候左旋？什么时候右旋？结点失衡的类型，可以概括为4种情况。
LL型
如图按照BST的要求，新插入结点3，可以看到根节点14目前是失衡的，新插入的结点3在14的左孩子的左子树上，我们将这种失衡成为LL型。
LL型的特征为：失衡结点14的平衡因子是2，失衡节点14的左孩子6的平衡因子是1，此时需要对失衡结点14进行右旋即可完成调整。
我们可以从图形上来理解这种调整策略，把整棵树当做一个天秤，根结点14是支点，结点3加入之前是基本平衡的，结点3加入后明显不平衡了，左边明显高于右边，这个时候我们要把右边壮大起来，让右边有更多的结点。二叉搜索树的特征是左＜中＜右，根节点一定是大于左边的结点的，要壮大右边的节点数，那么根节点要下沉到右子树里面，左子树的结点需要成为新的根节点。通俗地说，失衡的时候，我们要把偏重一边的结点转移到偏轻一侧，以达到新的平衡。
RR型
如图看到一棵树，结点5的平衡因子是-2，新结点是在其右孩子的右子树上，这种失衡称为RR型。从图形上来理解，现在是右侧偏重，所以要壮大左子树，同时根节点需更新为右侧的结点。
对于RR型的调整，我们需要将结点5进行左旋。
LR型
下图中，新插入结点6，结点9的平衡因子为2，处于失衡状态，新结点出现在失衡结点的左孩子的右子树上，称为LR型。
LR型的调整相对复杂。LR型的策略为：左旋左孩子，然后右旋。先看左旋左孩子的结果：
然后再右旋：
回顾一下LR的调整过程，我们的目标是平衡整棵树，只要以L开头的，就会需要壮大右子树。所以失衡节点9需要右旋，但是因为新加的结点6在失衡结点9的左子结点5的右子树，相当于左子结点5的右侧偏重，所以先要把结点5左旋。
RL型
如图结点8是新结点，此时结点5发生了失衡，平衡因子为-2，新结点在失衡结点的右子结点的左子树上，这种失衡为RL型。
通过对于RL型的理解，我们能推断RL型的策略，先右旋右孩子，然后左旋失衡结点。右旋右孩子：
再左旋失衡结点：
失衡类型总结
LL，RR，LR，RL，全面概括了在插入新结点过程中，出现失衡结点的4种失衡类型。判断的依据就是新结点与失衡结点的关系，具体判断需要根据新结点在失衡结点的左孩子还是右孩子，以及新结点在失衡结点的孩子结点的左子树还是右子树，来确定是LL/RR/LR/RL的那一种类型。也可以用平衡因子去判断，加入新结点，新结点往上层结点进行遍历，同样有4种情况：
- 如果失衡结点的平衡因子是2，且其左孩子平衡因子是1，那么是LL型；
- 如果失衡结点的平衡因子是2，且其左孩子平衡因子是-1，那么是LR型；
- 如果失衡结点的平衡因子是-2，且其右孩子平衡因子是1，那么是RL型；
- 如果失衡结点的平衡因子是-2，且其右孩子平衡因子是-1，那么是RR型；
在实际过程中，插入一个结点可能导致多个祖先节点失衡，比如下图结点3和结点6。
此时只需要调整距离结点9最近的失衡结点即可，调整完后其他结点会自动平衡。
构造一颗AVL树
接下来我们来构造一颗AVL树，给定数据
14/9/5/17/11/12/7/19/16/27。按顺序添加，前两个结点是不需要思考的，先添加结点14作为根节点，再插入9作为左孩子，在插入结点5，按照BST的规则，作为结点9的左孩子。
此时出现了失衡，失衡结点是14，属于LL型，应用规则将14右旋，得到下图。
剩下数据为17/11/12/7/19/16/27接着插入17，没有失衡结点。
剩下数据为11/12/7/19/16/27接着插入11，依旧没有失衡结点。
剩下数据为12/7/19/16/27，接着插入12，此时再次出现了失衡的情况。
结点9的平衡因子是-2，结点14的平衡因子是1，属于RL型，先右旋右孩子14。
再左旋失衡结点9，再次得到一颗平衡二叉树。
剩下数据为7/19/16/27，接着插入7，此时再次出现了失衡的情况。结点9的平衡因子是2，节点5的平衡因子是-1，属于LR型。先左旋左孩子，再右旋失衡结点。
左旋左孩子5。
再右旋结点9。
剩下数据为19/16/27，接着插入19，没有失衡发生。
剩下数据为16/27，接着插入16，没有失衡发生，直到插入27，发现有两个结点失衡。结点11，结点14相继发生失衡，调整距离近的结点14，结点14的平衡因子为-2，其右孩子的平衡因子是-1，属于RR型，需要左旋结点14。
左旋结点14，得到下图的树，再次满足了AVL的要求，也验证了在因为插入某一结点导致有多个结点失衡的时候，只需要处理距离最近的结点即可。
上面提到的是插入新结点，需要注意的是，这条规则（插入新结点导致多个失衡，只需要处理最近的失衡结点）并不适用于删除操作。如果删除某个结点导致AVL失衡，需要依次对每个祖先进行检查并且旋转调整。
总结
平衡二叉树（AVL）是二叉搜索树的一种，其强调左右子树的严格平衡，以达到O(log n)的最佳查找效率。当操作结点导致AVL失衡的时候，需要找到距离新结点最近的失衡结点，并且判断失衡类型（LL、LR、RL、RR），进行旋转的平衡调整操作。插入只需要调整一次，而删除可能需要调整多次。