07 AVL 树
用二叉树的遍历来消除递归。
前面说了模拟系统函数调用的方法消除递归，现在再说说利用遍历消除递归的方法。
先看两个递归函数。
void MergeSort(int [] array,int left,int right){
if(right<=left) return;
int mid=(left+right)/2;
MergeSort(array,left,mid);
MergeSort(array,mid+1,right);
Merge(array,left,mid,mid+1,right);
}
void QuickSort(int[] array,int left,int right){
if(right<=left) return;
选择枢轴，把它放到正确的位置，并把比它小的放到它的左边，比它大的放到右边;
QuickSort(左边的数组);
QuickSort(右边的数组);
}
这两个递归函数都调用自身两次。这和二叉树的遍历有什么关系呢？
两次递归把整个代码分成三部分。比如：归并排序。
part1 int mid=(left+right)/2;
递归调用1 MergeSort(array,left,mid);
part2 空
递归调用2 MergeSort(array,mid+1,right);
part3 Merge(array,left,mid,mid+1,right);
函数的执行过程是：进入part1（当前节点），进入递归调用1（左孩子），part2（当前节点），进入递归调用2（右孩子），进入part3（当前节点）。
哦，有点遍历的意思了，但遍历是每个节点访问一次，你都访问3次了！part2是空，就算少一次，还有part1和part3呀！先我们不看part1，那么就是一个后序的遍历。
QuickSort比较简单part2和part3本来就是空的，所以它是个先序的遍历。
现在我们来看看为什么MergeSort对应一个后续遍历？即为什么part1可以不理睬？
MergeSort的目的就是把输入――array[left….right]中的数从小到大排序并放到array[left…right]中。我们要处理的数据是array数组，而part1的int mid=(left+right)/2;和array是没有关系的。
AVL树
一般书讲AVL树，一上来就是插入节点有两种情况（对称又两种），怎么旋转使它平衡；删除又有四种情况，怎么旋转使它平衡。却没有说明为什么插入有两种不平衡的情况？为什么没有3种4种？
先看插入节点。
首先当然是用BST的插入算法找到插入的位置。另外从根到插入节点路径上所有的节点（即插入节点的祖先们）都可能被用到，所以在查找的过程中要把他们都保存下来。
从被插入节点一直向上走，因为原来的树是平衡的（注意，这里说的平衡是只满足AVL性质，即左右子树的高度之差的绝对值不超过1，而不是说树是最优平衡的），所以它遇到的节点的平衡因子只能是0,+1或-1。如果遇到的是0，则插入一个节点后它的平衡因子就会变成-1或+1，但树的高度加1，所以还要继续向上走。如果遇到的是+1或-1，那么可能变成0,+2或-2。如果变成0了，那么树还是平衡的，并且树的高度不再增加，所以不用再向走上了。如果变成2，则出现第一个不平衡的节点。
既然不平衡了，那么我们就想办法使它平衡。注意，除了使它平衡外，最好它的高度还不变，这样我们就不用向上走了。
总结一下：我们从被插入节点一直向上走，遇到0就把它变成+1或-1（左上是+1，右上是-1），并继续向上走；遇到+1或-1则分两种情况：一是变成0，一是变成+2或-2。但不管哪种情况都不用再向上走了（变成0树高肯定不变，变成+2或-2我们假设在使它平衡的同时还不增加树高，后面我们会发现只是可行的）。
假设向上第一个不平衡的节点（即平衡因子由+1或-1变成+2或-2的节点）为P，由于对称性我们假设它由+1变成+2。（万一没有节点从+1或-1变成+2或-2呢？那么有两种情况：有节点从+1或-1变成0；一直到了根了。无论哪种情况树都已经平衡了。）
则原来的树一定是下面的形状。图上用括号括起来的是节点的平衡因子。
P(+1)
/ (h) Q(0)
/ (h) (h)
为什么Q的平衡因子是0？因为根据前面的分析，从被插入节点一直向上P是第一个平衡因子是+1或-1，其余的都是0。
因此插入后又有两种情况：Q的左子树变成高为h+1;Q的右子树变成高为h+1。
我们来分别讨论。
先讨论右子树增高的情况（先看简单的）。插入后的树变成下图的形状。
P(+2)
/ (h) Q(+1)
/ (h) (h+1)
树不平衡了！哪不平衡？P的右子树Q（的右子树）太高了！所以要把它弄上去。当然不能随便弄上去，要保持BST树的性质。这就是所谓的RR旋转。旋转的结果是：
Q(0)
/ P(0) (h+1)
/ (h) (h)
结果很好，比原来还平衡，而且树的高度不变（旋转前后都是h+2）。
再来看左子树增高的情况，如下图。
P(+2)
/ (h) Q(-1)
/ (h+1) (h)
如果我们还是依葫芦画瓢把Q弄上去的话，则会变成下面的树：
Q(-2)
/ P(+1) (h)
/ (h) (h+1)
还是不平衡！因为这次不平衡的元凶不是Q的右子树而是左子树，因此我们要把Q的左子树的根弄上去。
把Q的左子树也画出来的树如下：
P(+2)
/ (h) Q(-1)
/ R(+1) (h)
/ (h-1) (h)
注意R为-1的情况与+1是一样的；R不能为0，为什么？（因为原来R是0，在向上走的过程中被变成了+1或-1）。
我们先把R弄上去：
P(+2)
/ (h) R(+2)
/ (h-1) Q(0)
/ (h) (h)
R又太高了，再把它也弄上去：
R(0)
/ P(-1) Q(0)
/ \ / (h) (h-1) (h) (h)
这下总算平衡了，而且经过两次旋转后，树的高度不变，还是h+2。
这就是所谓的RL旋转。
除此之外还有对称的LL和LR旋转。
接着来看AVL树删除节点的方法。
在这之前先来复习一下BST删除节点的算法。
分三种情况：删除叶子；被删除的节点有一个孩子；被删除的节点有两个孩子。
删除叶子最简单，直接把它的父亲节点的指针置成空就可以了。如下图：
15 15
/ \ 删除16 / 4 20 --------> 4 20
/ / /
1 16 1
删除只有一个孩子的节点也不难，把它的父亲指向它的孩子就可以了。
15 15
/ \ 删除20 / 4 20 --------> 4 16
/ / /
1 16 1
删除有两个孩子的节点有点麻烦。有两种方法――归并删除法和拷贝删除法。
归并删除的思路是：先安排被删除节点的左孩子，这和只有一个孩子的节点的删除是一样的；然后把被删除节点的右孩子插入到合适的位置（也就是被删除节点左子树的最右节点）。
15 10
/ \ 删除15 / 10 30 ---------> 5 11
/ \ / \ 5 11 20 40 12
\ 12 30
/ 20 40
上面的例子说明删除一个节点可能使得树的高度反而变高了。
拷贝删除的思路是：在被删除节点的左子树（或右子树）找到最大也即最右的节点（或最小的节点），左子树最右的节点最多只有一个孩子。把删除有两个孩子的节点转变成删除最多一个孩子的节点。然后把这个节点拷贝到真正被删除的节点里。
15 12
/ \ 删除15 / 10 30 ---------> 10 30
/ \ / \ / \ / 5 11 20 40 5 11 20 40
\
12
它的好处是树的高度不会增加。而且，真正被删除的节点为根的子树的高度是一定减少的。因为如果删除的是叶子，那么原来高度是1，现在变成0了；如果删除的是只有一个孩子的节点，那么它的子树替代了被删除的节点，也使树的高度少1。
在AVL树的删除中我们会用第二种方法，因为我们不希望在删除节点和树反而变高了。
我们还使按照与插入类似的分析方法。
找到第一个真正被删除的节点（叶子或一个孩子的节点），删除这个节点后这个节点的子树还是平衡的（叶子的子树是空树，一个孩子的节点它的孩子原来就是平衡的）。但删除节点后，以它为根的子树高度减一，这可能导致它的父亲不平衡。
因此我们沿着这个被删除的节点一直向上走。遇到的节点不外乎0,+1和-1三种。
如果遇到了0，则把它变成+1或-1（向右向上是+1向左向上是-1），树依然平衡，由于这时树的高度不会减少，所以不用再向上走了。
如果遇到了+1或-1，又有两种情况：变成0；变成+2或-2。
如果变成0的话树仍然是平衡的，但树的高度少一，所以还要往上走。
变成+2或-2的话树就不平衡了，需要我们通过旋转使之平衡。但平衡的同时能不能保证树的高度不减少呢（这样就不用向上走了）？通过分析我们将会发现有时树的高度会减少的。
由于对称性，我们假设某个节点P由+1变成了+2，原因是左子树变矮了。那么P的右孩子Q的平衡因子有3种情况（0,+1和-1）。
1．Q的平衡因子为1的如下图：
P(+1) P(+2) Q(0)
/ \ / \ / (h) Q(+1) (h-1) Q(+1) P(0) (h)
/ \ / \ / (h-1) (h) (h-1) (h) (h-1) (h-1)
原来的情况 左子树变矮后 把Q转上去后
通过旋转，树变平衡了，但新树的高度减少了，因此还有继续往上走。
2．Q的平衡因子为0的情况如下图：
P(+1) P(+2) Q(-1)
/ \ / \ / (h) Q(0) (h-1) Q(0) P(+1) (h)
/ \ / \ / (h) (h) (h) (h) (h-1) (h)
原来的情况 左子树变矮后 把Q转上去后
通过旋转，树平衡了，而且新树的高度不变，不用再向上走了。
3．Q的平衡因子为-1的情况。
如果我们还是把Q转上去的话，依然是不平衡的，如下图：
P(+1) P(+2) Q(-2)
/ \ / \ / (h) Q(-1) (h-1) Q(-1) P(+1) (h-1)
/ \ / \ / (h) (h-1) (h) (h-1) (h-1) (h)
原来的情况 左子树变矮后 把Q转上去后
原因和插入的RL旋转有些类似，因为Q的左子树太高了，所以我们先要把Q的左子树R转上来(Q下去)，然后R再转上去（P下去）。但R的平衡因子可能有三种情况，这会不会影响其它的节点呢？我们分三种情况讨论。
3.1 R的平衡因子是-1
如下图：
P(+1) P(+2) P(+2) R(0)
/ \ / \ / \ / \
(h) Q(-1) (h-1) Q(-1) (h-1) R(+1) P(0) Q(+1)
/ \ / \ / \ / \ / R(-1) (h-1) R(-1) (h-1) (h-1) Q(+1) (h-1) (h-1) (h-2) (h-1)
/ \ / \ / (h-1) (h-2) (h-1) (h-2) (h-2) (h-1)
原来的情况 左子树变矮后 把R转到Q上面后 把R转到P上面后
通过两次旋转，树变得平衡了，但树的高度减少。
3.2 R的平衡因子是+1。
P(+1) P(+2) P(+2) R(0)
/ \ / \ / \ / \
(h) Q(-1) (h-1) Q(-1) (h-1) R(+2) P(-1) Q(0)
/ \ / \ / \ / \ / R(+1) (h-1) R(+1) (h-1) (h-2) Q(0) (h-1) (h-2) (h-1) (h-1)
/ \ / \ / (h-2) (h-1) (h-2) (h-1) (h-1) (h-1)
原来的情况 左子树变矮后 把R转到Q上面后 把R转到P上面后
通过两次旋转，树变得平衡了，但树的高度减少。
3.3 R的平衡因子是0
P(+1) P(+2) P(+2) R(0)
/ \ / \ / \ / \
(h) Q(-1) (h-1) Q(-1) (h-1) R(+1) P(0) Q(0)
/ \ / \ / \ / \ / R(0) (h-1) R(0) (h-1) (h-1) Q(0) (h-1) (h-1) (h-1) (h-1)
/ \ / \ / (h-1) (h-1) (h-1) (h-1) (h-1) (h-1)
原来的情况 左子树变矮后 把R转到Q上面后 把R转到P上面后
通过两次旋转，树变得平衡了，但树的高度减少。
从上面的图中可以看出R的平衡因子是什么没有关系，只要把R两次转上去就可以了。
总结一下删除的过程：找到真正被删除的节点，然后从它一直向上走。
如果遇到了0，则把它变成+1或-1（向右向上是+1向左向上是-1），且不用再向上走了。
如果遇到了+1或-1并且把它变成了0(向左遇到+1，向右遇到-1)，继续向上走。
如果遇到了+1或-1并且把它(设为P)变成了+2或-2(向右遇到+1，向左遇到-1)，则分三种情况（我们只讨论了+1,-1类似）。a)P的孩子Q是+1，把Q转上去，继续往上走；b)P的孩子Q是0，把Q转上去，不用上走了；c)P的孩子Q是-1，把Q的孩子R两次转上去，继续往上走。
