####简要说明####
AVL平衡树是一种自平衡的二叉查找树，其相比普通的二叉查找树不同之处在于，对于树中的任何一个节点，其左子树和右子树的高度之差不能超过 1 。如果一个节点没有左子节点，认为他的左子树为空树，即左子树的高度为 0。另外如果该节点没有右子节点，同样认为他的右子树为空树。
####树的高度####
对于普通的二叉查找树，当树是一棵完全二叉树，其高度最低，但最差的情况它能够退化成一条链，高度能够达到 n, 比如如果树中的元素是按升序或者降序插入时就会退化为一条链。
那么对于有 n 个节点的 AVL树，其最大高度是多少呢？这个高度值通常决定了该数据结构的优劣。因为如果它最差情况下也会退化为一条链，那么针对普通的二叉查找树他就可能没有什么明显的优势了。
但有幸在最差情况下，一个含有 n 个节点的 AVL平衡树其高度仍然是 O(log(n)) 的。这里引述维基百科上提供的证明。
首先将原问题作一个小小的转换，原问题是希望求出含有 n 个节点的 AVL平衡树最大高度是多少，这里转化为对于一个高度为 h 的 AVL平衡树其最少含有多少个节点。
根据 AVL树的性质，其每个节点的左子树和右子树高度差值不超过 1 。那么考虑根节点，因为其高度为 h ，所以其应该至少有一棵子树的高度为 h - 1。而另一棵子树的高度可以为 h - 1，也可以为 h - 2。假设高度为 h 的AVL平衡树最少含有 f(h) 个节点。那么 f(h) = f(h-1) + f(h-2)。也就是 fabonacci 数。求得 f(h) = Φ(h+2) / √5 - 1。如果 令 f(h) = n ，求得 h = logΦ (√5 + (n + 1)) - 2 ，其中 Φ 为 (√5 + 1) / 2 = 1.618 。所以说含有 n 个节点的 AVL平衡树第最大高度仍然是 O(log(n)) 的。这样就保证了 AVL平衡树的查找时间是 O(log(n)) 的。注：以上证明都是引自维基百科。
####节点插入####
对于一棵AVL平衡树，插入一个新的节点。首先按照普通二叉树的插入方法，将节点插入到合适的位置。插入之后，从该节点往上回溯直到根节点，检测该路径上哪些节点是失去平衡的然后进行调整。
这里进行回溯，是因为只有从插入节点到根节点路径上的点受到了影响。其他节点其左右子树是没有发生改变的。所以对其他节点不需要进行额外的考虑。
在回溯的过程中检测每一个节点，如果左右子树的高度之差（取绝对值）大于 1。那么说明该节点失去平衡了。需要进行调整。对于一个失去平衡的节点，可以断定，他肯定有儿子节点和孙子节点。因为他没有儿子节点，说明他是叶节点，如果他没有孙子节点，那么他的左右子树的高度之差应该最多为 1 。即当其只有左子节点或只有右子节点的情况。
好吧，至此，我要开始猥琐的盗图了。注：以下图示都来自 geeksforgeeks。
如果一个节点失去平衡，总共会有一下四种情况。
####简要分析####
结合第一幅图示进行简单分析。如果插入的节点在 T1 上，可以得到这几个等式。这里用 H()表示一棵树高度。那么 H(T1) = H(T2) + 1 , H(T4) = H(T1) , H(T3) = H(T4)。
首先说第一个等式。因为插入的节点在 T1 。如果 H(T1) <= H(T2) 那么说明插入前和插入之后 z 的右子树的高度都没有发生变化，都为 H(T2) + 2。插入之前是平衡的，那么插入之后也应该是平衡的。但此时树不平衡说明该条件不成立。但因为节点 x 是平衡的，综合两者。 H(T1) = H(T2) + 1。
再说第二个等式。插入之前节点 z 是平衡的，插入之后失去平衡，说明 T1的高度肯定是在插入之后增加了 1 。此时 z 节点的左子树高度和右子树的高度之差应该为 2。因为如果差值大于 2，说明插入之前就不平衡，即 H(T2) + 2 = H(T4) + 2。其中 H(T1) + 2 是节点 z 的左子树的高度。所以 H(T4) = H(T1)。
再说第三个等式。首先可以肯定节点 z 的高度应该有应该由以 x 为根的子树决定，否则根据题意，节点 z 就不会失去平衡。这也说明节点 y 的左子树的高度比其右子树的高度大。但因为节点 y 是平衡的，所以左子树的高度应该比右子树大 1 。所以 H(T1) + 1 = H(T3) + 1 。其中 H(T1) + 1 为节点 y 的左子树的高度。根据等式二 H(T3) = H(T1) = H(T4)。
这里得出这三个等式，是为了说明对于不同的情况经过左旋或者右旋之后能够使得该节点达到平衡。
以下四幅图示中，都是假设 z 是第一个失去平衡的节点，y 是节点 z 的一个子节点，而且导致 z 失去平衡的原因是因为以 y 为根的子树高度比节点 z 的另一棵子树高（暗含插入的节点是在以 y 为根的子树上）。 节点 x 是节点 y 的子节点，且导致以 y 为根的子树高度增加的原因是以 x 为根的子树高度增加了 （暗含插入的节点在以 x 为根的子树上）。
####1. left left case #### 第一幅图示，不管插入点在 T1 还是 T2，经过对节点 z 右旋之后，编程图示右边的子树。该子树都是平衡的。因为 T1 和 T2 的高度差为 1 。 T3 和 T4 的高度相等。
T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
####2. left right case #### 二幅图示，如果插入点在 T2 上，那么根据前面的分析， H(T2) = H(T3) + 1 = H(T1) = H(T4) 。先对节点 y 左旋，再对节点 z 右旋之后得到的子树是平衡的。同时如果插入的节点在 T3 上，根据前面的分析，经过两次旋转得到的子树也是平衡的。
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
####3. right right case #### 第三幅图示，不管插入的点在 T3 或者 T4 那么对节点 z 进行左旋之后得到的子树都是平衡的，因为根据分析， T3 和 T4 的高度差值为 1 。而 T1 和 T2 的高度是相等的。
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
####4. right left case #### 第四幅图示，如果插入的节点在 T2 ，那么根据前面的分析 H(T2) = H(T3) + 1 = H(T4) = H(T1) 。先对节点 y 进行右旋，再对节点 z 进行左旋得到的子树是平衡的。同理如果插入节点在 T3 上，经过两次旋转，得到的子树也是平衡的。
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z x
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
对于 节点 z 失去平衡，可能的情况就是以上四种，不同的情况按照图示上的方法进行调整之后都能使节点达到平衡。
####节点删除#### 节点的删除也是先用普通二叉查找树的方法对节点进行删除，然后在被删除的位置向上回溯，检测从被删除的位置到根节点的路径上是否有节点失去平衡，如果有，则进行调整。
####简要分析#### 以下四幅图示中，都是假设 z 是第一个失去平衡的节点，y 是节点 z 的一个子节点，而且导致 z 失去平衡的原因是因为以 y 为根的子树高度比节点 z 的另一棵子树高（暗含删除的节点在 z 的另一棵子树上，即不在以 y 为根的子树上）。 节点 x 是节点 y 的子节点，以 y 为根的子树高度由以节点 x 为根的子树决定，即以 x 为根的子树要大于或等于 T3 的高度。
按照类似与节点插入的方法对第一幅图示进行分析，
如果 H(T1) >= H(T2) ，因为以 y 为根的子树应该比 T4 的高度大 2 。所以 ( H(T1) + 2 ) - H(T4) = 2 ，即 H(T1) = H(T4)。同时因为以 x 为根的子树的高度应该大于等于 T3 的高度，所以 H(T1) + 1 - H(T3) >= 0 。即 H(T1) >= H(T3) - 1 ，同时因为节点 y 是平衡的（因为删除的点在 T4上，删除前后节点 y 的平衡性不应该发生改变）。所以 ( H(T1) + 1) - H(T3) <= 1 。即 H(T1) <= H(T3)。所以综合得到 H(T3) - 1 <= H(T1) = H(T4) <= H(T3)。同时 H(T1) = H(T2) 或者 H(T1) = H(T2) + 1 。
####1. left left case#### 第一幅图示，经过对节点 z 右旋之后，编程图示右边的子树。该子树都是平衡的。因为 T1 和 T2 的高度差为 1 。 T3 和 T4 的高度差不超过 1 。
T1, T2, T3 and T4 are subtrees.
z y
/ \ / \
y T4 Right Rotate (z) x z
/ \ - - - - - - - - -> / \ / \
x T3 T1 T2 T3 T4
/ \
T1 T2
####2. left right case#### 第二幅图示，如果 H(T2) >= H(T3) ，那么根据前面的分析， H(T1) - 1 <= H(T2) = H(T4) <= H(T1), 同时 H(T2) = H(T3) 或者 H(T2) = H(T3) + 1 。先对节点 y 左旋，再对节点 z 右旋之后得到的子树是平衡的。因为 T1 和 T2 的差值不超过 1 。同时 T3 和 T4 的差值也不超过 1 。
如果 H(T3) >= H(T2) 。得到 H(T1) - 1 <= H(T3) = H(T4) <= H(T1), 同时 H(T3) = H(T2) 或者 H(T3) = H(T2) + 1 。旋转之后，节点 z 是平衡的，因为 T3 和 T4 的个高度相等，但 T1 和 T2 的高度之差是可能达到 2 的，当 H(T1) = H(T3) + 1, H(T3) = H(T2) + 1 时。
那么是哪里出问题了？其实此时如果细心能看到，如果上面的 H(T1) = H(T3) + 1 成立，根本不会进入第二种情况，我们可以直接当成第一种情况处理，因为满足左边子树的高度大于等于右边子树的高度，直接当成 left left case。经过一次旋转就行了。所以如果进入这一种情况，我们可以限制以 x 为根的子树的高度大于 T1 的高度。即如果 H(T3) >= H(T2) 那么 H(T1) = H(T3) = H(T4)，同时 H(T3) = H(T2) 或者 H(T3) = H(T2) + 1 。如果 H(T2) >= H(T3) ， 则 H(T1) = H(T2) = H(T4), 同时 H(T2) = H(T3) 或者 H(T2) = H(T3) + 1 。两种情况最后旋转得到的子树都是平衡的。
z z x
/ \ / \ / \
y T4 Left Rotate (y) x T4 Right Rotate(z) y z
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
T1 x y T3 T1 T2 T3 T4
/ \ / \
T2 T3 T1 T2
####3. right right case#### 第三幅图示和第一幅图示是对称的，如果 H(T3) >= H(T4) 。可以得到 H(T2) - 1 <= H(T3) = H(T1) <= H(T2)，同时有H(T3) = H(T4) 或者 H(T3) = H(T4) + 1 。那么对节点 z 进行左旋之后得到的子树是平衡的，因为 T1 和 T2 的差值不超过 1 。 T3 和 T4 的差值不超过 1 。同理可得 H(T3) >= H(T4) 时旋转得到的子树也是平衡的。
z y
/ \ / \
T1 y Left Rotate(z) z x
/ \ - - - - - - - -> / \ / \
T2 x T1 T2 T3 T4
/ \
T3 T4
####4. right left case#### 第四幅图示，根据对第二幅图示的分析，我们可以认为必须要以 x 为根的子树的高度大于 T4 ，才会进入第四种情况，否则可以直接按第三幅图示的情况进行处理 ，则如果 H(T2) >= H(T3) ，可以得到 H(T2) = H(T1) = H(T4)，同时 H(T2) = H(T3) 或者 H(T2) = H(T3) + 1 。那么先对节点 y 进行右旋，再对节点 z 进行左旋得到的子树是平衡的。因为 T1 和 T2 高度相同，T3 和 T4 的高度差不超过 1 。同理如果 H(T3) >= H(T2) ，也可以得到经过两次旋转之后的子树是平衡的。
z z x
/ \ / \ / \
T1 y Right Rotate (y) T1 x Left Rotate(z) z x
/ \ - - - - - - - - -> / \ - - - - - - - -> / \ / \
x T4 T2 y T1 T2 T3 T4
/ \ / \
T2 T3 T3 T4
对于 节点 z 失去平衡，可能的情况就是以上四种，不同的情况按照图示上的方法进行调整之后都能使节点达到平衡。
####总结####
基本上说明了， AVL平衡树的维护过程，源码实现在这里 ，写的较恶。
####引用####
AVL Tree | Set 1 (Insertion)
AVL Tree | Set 1 (Deletion)