平衡树介绍
前几篇的文章我们介绍了一下二叉树和二叉搜索树。现在假设我们要建立一棵BST，依次插入下列数据：
20, 33, 50, 61, 87, 99
那么按照BST的规则我们可以得到下列的BST：
如果你问我，这是一棵二叉搜索树吗？这肯定的。但是它更像什么？链表！有什么区别呢？数据结构不同，链表只包含一个指向下一个节点的指针，而这个包含的还有指向左节点的指针。这个时候我们看看，我们之前定义的方法效率有没有变化？当然有，而且效率会被大大降低。因为我们之前执行的方法都是要遍历左右子树的，而这种树压根就没有左子树，遍历左子树显得太多此一举。举个例子，我们之前写过一个函数 isContains()，它的作用是遍历二叉搜索树，然后找到对应的节点。如果它是正常的二叉搜索树的结构，那么执行该方法的算法复杂度就是O（logN），但是如果是上图所示的结构那么就是链表的遍历为O(N)。
只有在树的每一层左右子树高度相同的情况下，用于实现BST查找算法才能达到理想的性能.因此我们应该想办法避免上述情况的发生，尝试将上面的类型转换成我们常见的二叉树。但是有时候这样的结构同样会带来一系列的问题，如下图：
这棵树的要求满足上面的左右子树高度相同，但是仅限于在树根上的满足。对比上图并没有改变什么。所以们还要满足这样的一个条件：保证每个节点必须有相同高度的左右子树（因此只有具有2k-1节点的完美平衡的树才能满足条件），如下图所示 ：
所以我们给平衡二叉树下个定义：
它类似二叉搜索树，唯一不同的就是，对于每一个节点，它的左右子树的高度差不超过1.（那么如果树空呢？左右子树为0，当然也是平衡二叉树，而且高度定义为1）
下图列举了一些平衡和非平衡二叉树的图例：
先来分析一下为什么下面这三棵不是平衡树。最左边的那棵树，左子树的高度为3，右子树为1。后面两棵树不平衡在于，对于根节点他们的高度差符合，但是它的子节点不平衡（例如图二中，树根下面的空心的节点，它左子树高度为2，右子树高度为0）。
平衡二叉树和AVL算法
刚刚提到，如果我们应用BST，在最坏的情况下，我们插入和查找的算法复杂度都是O（N），因为那时候变成了线性查找。树状结构也就没什么意义了。要完全发挥BST的性能优点，最好的办法就是避免最坏情况的发生。换句话说我们只要时刻保持树的高度平衡，那么就永远不会出现最坏的情况。
第一个树平衡算法是由俄罗斯数学家Georgii Adelson-Velskii和Evgenii Landis于1962年发表的。算法的名称就用两位科学家的名字首字母命名为AVL算法。因此AVL是一个平衡树算法，AVL树又称为高度平衡树。
先看下图，下图中，是一棵平衡树:
现准备在这颗树中，插入子节点6。按照插入的规则，我们可以得到下图：
当我们插入一个节点到AVL树中时，我们必须更新平衡树的信息，比如节点树啊，深度等等
- 我们也必须适当的维护AVL树的平衡结构！ （这是很棘手的一个问题），假设我们考虑在上面的树中插入数字6，显然这会扰乱节点8处的平衡。
- 事实证明，树的简单修改（称为旋转）可以恢复AVL的平衡属性
- 插入之后，只有插入路径上的节点可能会改变它们的平衡，因为只有那些节点改变了它们的子树。我们可以根据平衡条件重新平衡。（比如插入6，只会对8路径之后的平衡造成破坏，而左子树跟根节点那边的平衡却完全不受影响）
AVL算法分析
假设现在存在一棵非平衡的二叉树α，我们要调用某个节点使其达到平衡状态。因为任何节点至多有两个孩子，二叉树不平衡要求α的两个子树的高度相差两以上，所以可能有四个违规情况：
- 插入到α的左侧子的左侧子树中。
- 插入α的左侧子元素的右侧子树中。
- 插入到右侧子树的左侧子树中。
- 插入右侧子树的右侧子树
看下图，假设三角形代表二叉搜索树中已经平衡的部分，那么上面出现不平衡的部分情况1 跟4对应下面的两幅图，这类问题称为外部问题（“outside” cases ），即L-L,R-R(Left-left,right-right).
情况2跟3对应的分别是这样的情况，即内部问题（“inside” cases ），L-R,L,R
针对外部问题，我们采用单旋转的方法（single rotation）
我们先看这样一幅图：
图中X三角形比其他的三角形比较大，意思是X部分代表更大的子树，你可以把X,Y想象成两个节点（X = Y+Z），Z为两个串起来的节点。显然k2违反了AVL属性，因为高度X已经变得比Z更深了2层.所以我们我们想把X上升一个水平，Z下降一个水平，这样这棵树就平衡了。具体的做法是：
我们这样想象：抓住k1摇晃，想象这是一个天平，存在重力。好，那么k1现在是新的根。 在图中，k2> k1（因为k1在k2的左子树中），所以k2成为k1的右边孩子。 X和Z分别保持为k1和k2的左边和右边的孩子。 Y可以放置为K2的左边的孩子，这样的话BST的顺序要求得以满足。如下图：
下面用实际例子解决一下问题：
解释：我们尝试在一棵平衡的BST中插入一个新的节点6，按照BST的规则，应该在7的左侧插入（如左边的图）。那么这样就造成了树的不平衡，因为8 7 6出现了LL结构，但是其他的地方的平衡却不受影响，因此我们可以将其他的地方想象成一个大三角形，我们只需要处理8 7 6这三个地方的不平衡问题（因为影响的是8以后的平衡）。按照刚刚提到的做法，我们把7这个节点提起来，向8的右侧旋转，作为这棵子树的树根，所以6在7的左侧，8在右侧，变成右边的额图，这样二叉树就平衡了。
同样的，RR问题的解决方式是一样的，就不再多提了（拿着k2向k1的左侧旋转）：
针对内部问题我们采用双旋转法（Double Rotation）
现在假设我们遇到下面左图这样的情况：
这个时候，不平衡点出现在k2，如果我们按照上面的步骤，进行单旋，那么会造成右图的问题。原因就是Y的深度太大，直接进行单侧旋转会使得深度加深适得其反。这个时候我们采用双旋转法解决这个问题。
-
看成是一次复杂的旋转，同样是上图，与其我们看成三棵树（xzy），还不如把这里看成4棵树，即将y分开，以k3作为节点连上。我们既不能让k1成为树根，也不能让k2成为树根，那么我们就让k3成为新的树根：
-
看成是两次简单的单旋转法，我们同样的可以两次旋转，这里我们看到，k1是不平衡的，所以我们先将k3向右旋转，再将k1向左旋转
附注：pro in cpp 中对AVL算法的解释
我们上篇的文章介绍过什么叫平衡二叉树，以及我们是怎么样实现二叉树的平衡的。其中AVL树就是其中的一种算法。现在回顾一下，我们说过导致树不平衡的插入方式有四种。现在我们用实例来说明，假设你要创建一个BST，其中里面的元素是元素周期表中的元素。
现在按照元素周期表的顺序建立平衡二叉搜索树。我们先插入第一个元素H，这很简单，因为一开始树为空。接下来我们调用之前我们写过的addNode函数，向里面插入我们的He元素，因为He元素在H元素的后面，所以插入的结果如下：
为了追踪所得的树是否为平衡树，AVL算法为每一个节点与某一个整数相关联，且这个整数的值为右子树的高度减去左子树的高度。这个值称为该节点的平衡因子（the balance factor of the node）
所以，对于节点H，右子树高度为1，左子树为0，平衡因子为1 - 0 = 1. 对于节点He来说，左右子树高度都为0，自然平衡因子为0.所以我们把这样的情况用下图表示：
所以，对于节点H，右子树高度为1，左子树为0，平衡因子为1 - 0 = 1. 对于节点He来说，左右子树高度都为0，自然平衡因子为0.所以我们把这样的情况用下图表示：
此时，这棵树是平衡的，因为**左右子树的高度差小于2（即每个节点中的平衡因子的绝对值 < 2）,**那么我们继续往里面插入Li元素，我们查阅周期表我们可以得到Li元素在He元素之后，那么应该这样表示：
此时，根节点不在平衡，因为它的右子树的高度为2，左子树高度为0.因此我们需要重构此树使得这棵树得以平衡。此时我们将He作为新的根节点，H作为左孩子，Li作为右孩子，得到下图就平衡了：
那么，问题来了，你怎么知道，或者说你怎么知道这样的操作就能使得原本不平衡的树变得平衡呢？
单侧旋转
如果你认真看看上图的变换，就能发现，中间的He元素往上升高，变成新的根节点。而H元素想做下降称为He的左孩子，Li不动：
参与旋转操作的两个节点称为旋转的轴。 在由元素H，He和Li组成的示例中，围绕H-He轴执行旋转。 由于此操作将节点向左移动，因此此图所示的操作称为左旋转（left rotation）。 如果树在相反方向上（即左边）不平衡，则可以应用称为右旋的对称操作，其中所有操作都简单地反过来过来。 例如，接下来的两个元素的符号（Be和B）分别被添加到树的左边。 要重新平衡树，必须围绕Be-H轴执行右旋，如下图所示：
因此，单侧旋转可以记为，左侧右旋，右侧左旋。
双侧旋转
然而，单侧旋转的操作并不是总能将树重构成平衡二叉树。试想一下，如果我们在上述的树上插入C元素，此时树的状态是这样的：
位于根部的He元素此时失衡，因为平衡因子的绝对值为2，如果此时你利用刚刚所说的单侧旋转，应该旋转He-Be杠杆，那么会得到下面的结果：
旋转之后，所得到的二叉树仍与之前一样处于不平衡的状态，唯一的不同点在于根节点的不平衡状态此时出现在右子树。
为什么会出现这个问题呢？原因在于，参与旋转的节点具有相反符号的平衡因子（He -2,Be +1）。当出现这种情况的时候，一次的单侧旋转是不够的，为了解决这个问题，我们必须想办法使得参与旋转的两个节点的平衡因子的符号相同。那么怎么样使得参与旋转的两个节点的平衡因子的符号相同呢？很简单，我们想想，平衡因子的符号取决于右子树的高度减去左子树的高度，如果左右子树通过旋转对调，那么平衡因子的符号也相应取相反数。 因此在旋转不平衡节点之前，沿相反方向旋转其子节点。 这个操作让参与旋转的父母和孩子的平衡因素相同的符号，这也就意味着第二次旋转将会成功。所以实际上是进行两次单侧旋转。
以上图刚刚插入C元素为例子，我们可以看到，He元素的平衡因子与Be元素的平衡因子符号相反，那么我们就不能直接进行单侧旋转，我们就对Be子树进行调整，使得杠杆的符号一致。具体做法是：沿相反方向旋转其子节点。
之前我们对He-Be杠杆进行右旋的，那么我们就对其子节点进行左旋：
此时旋转之后的结果是，这棵树依旧不处于平衡状态，但是我们已经做到了杠杆符号一致，那么此时再进行一次正常的单侧旋转(杠杆为He - H，想象一下用手提起元素H)，也就是右旋，得到平衡的二叉树AVL：
因此，双侧旋转要两次旋转，一次调整杠杆符号，一次单侧旋转。
AVL树的特点
在描述这些树的论文中，Adelson-Velskii和Landis展示了他们的树平衡算法的以下特性：
- 如果你向一棵AVL树插入新节点中，则始终可以通过执行至多一次操作来恢复其平衡，该操作可以是单次旋转或双次旋转。
- 完成旋转操作后，旋转轴上子树的高度始终与插入新节点之前的高度相同。 此属性可确保树中任何更高级别的平衡因素都不会发生变化。
C++代码有空再贴上。考试暂时不看此代码，但是考原理。