严蔚敏的书 看的不是太明白，转一个
AVL-Tree，又称高度平衡树（High-Balanced Tree），是一种自平衡二叉查找树（Self-Balancing Binary Search Tree），最初由 G.M. Adelson-Velsky 和 E.M. Landis 于1962年表，并因此得名。这里不打算做细致的概念性介绍，直接分析数据结构的原理与实现。
本文内容假设读者对二叉树（Binary Tree）这种数据结构有所了解，知道树的高度（Height）等概念，并且对二叉查找树（Binary Search Tree）在搜索、插入、删除中的优点和不足已有所认识。
AVL Tree的原理实际上只有一条原则：任何一个节点的左右两个子树的高度差不大于1。对于一般的二叉查找树来说，除非输入数据受到严格控制，否则插入操作很容易产生不平衡。为解决插入过程中的不平衡，AVL Tree通过旋转（Rotations）操作来完成树的自动平衡工作。如何确定一个节点的平衡性呢？AVL Tree需要一个平衡因子（Balance Factor）来记录节点的平衡性，用以标志一个节点是处于平衡状态、左子树更高或者右子树更高。当一个节点处于平衡、左子树比右子树高1或者右子树比左子树高1这三种情况之一时，这个节点被认为处于稳定状态，不需要调整。
【约定】
- 节点（Node）：用A、B、C、D、E等字母来表示；
- 节点包括：左子树（Left Child）、右子树（Right Child）、平衡因子（Balance Factor）、数据（Data），共四个部分；
- [Node].l、[Node].r 分别表示节点 [Node] 的左子树、右子树；
- ≮、⊥、≯ 分别表示稳定状态中的 左子树高1、平衡、右子树高1；
- ≤、≥ 表示不稳定状态，即左边过高、右边过高；
- h([Node]) 表示 [Node] 节点的高度；
- b([Node]) 表示 [Node] 节点的平衡性；
- ＝ 表示两个 值/表达式 相等。
由于BST在左右两个方向上是对称的，所以后面的讨论都只针对一种情况进行，另一个方向上的则可同理得出。
插入（Insertion）
首先我们要了解的是，在不同情况下，节点的高度和平衡因子会发生变化呢？
假设：有节点N，h(N)=h0，现在有使N节点的左树高度增加1的插入。
(a) 当b(N)=≮时，由于h(N)=h0，故h(N.l)=h0-1，(N.r)=h0-2；插入后，h(N.l)=h0，h(N)=h0+1，高度增加，b(N)=≤；
(b) 当b(N)=⊥时，由于h(N)=h0，故h(N.l)=h0-1，(N.r)=h0-1；插入后，h(N.l)=h0，h(N)=h0+1，高度增加，b(N)=≮；
(c) 当b(N=≯时，由于h(N)=h0，故h(N.l)=h0-2，(N.r)=h0-1；插入后，h(N.l)=h0，h(N)=h0+1，高度不变，b(N)=⊥。
当N为叶节点时（h(N)=1，即N的左右子节点都为空），则只能发生情况(b)。显然，平衡性的变化可以在插入过程中由子节点的结果递归得出。
在插入后，以下三种情况都是稳定的：
不稳定这两种情况：
当出现这两种不稳定的情况时，我们就需要进行旋转（Rotations）。旋转的作用是改变原有的树的结构，但不破坏树的性质（事实上几乎所有的自平衡BST都会采用这几种旋转方式）。下面是一个典型的AVL旋转（左子节点的值小于父节点）：
继续前面假设的情境，由于(b)、(c)两种情况下，节点是稳定的，不需要调整；所以下面对情况(a)即插入后N的平衡因子为≤的情况进行讨论。[Note 1]
考虑N的左子节点的平衡因子变化：因为N的左子树高度增加了，所以N才需要调整，这意味着，N的左子节点L的平衡因子发生了变化。由于(a)情况是现在正在讨论的，问题是递归解决的，所以可以先不用考虑；而在(c)情况下L的平衡因子不会发生变化，L的高度不变，现在的环境不成立；所以L的变化只可能是情况(b)，即插入前的平衡性为⊥，插入后为其它两种平衡性之一（在递归中我们可用此判断是否需要进行旋转）。下面分两种情况进行讨论，即插入后L的平衡因子分别为≮、≯。
假设有节点D：插入前b(D)=≮，h(D.r)=h0；令B=D.l，则b(B)=⊥，h(B)=h0+1， h(B.l)=h(B.r)=h0。插入后，则h(B)= h0+2，b(D)=≮，需要根据插入后b(B)的情况进行调整（见下图）：
- b(B)=≮。这种情况比较简单，图上很清楚，对D节点进行一次右旋即可。旋转后，原节点D被B代替，而B和D节点都恢复了平衡；和插入前相比，根节点高度没变；
- b(B)=≯。图中很难看出来插入后b(C)=⊥，下面先证明：因为插入前h(C)=h0+1，故Max[h(L), h(R)]=h0，则h(L)<=h0，h(R)<=h0；又因为h(L)<=h(B)=h0，h(R)<=h(D)=h0，所以插入后，h(B)=Max[h(B.l), h(L)]=h0，h(D)=Max[h(D.r), h(R)]=h0，则b(C)=⊥得证。又因为插入后h(B)=h(D)=h0+1，所以旋转后与插入前的根节点的高度相同。
但插入后b(B)、b(D)需要根据插入前b(C)的情况来讨论：
- 插入前b(C)=⊥：则h(L)=h(R)=h0；插入后，b(B)=b(D)=⊥；
- 插入前b(C)=≮：则h(L)=h0，h(R)=h0-1；插入后，b(B)=⊥，b(D)=≯；
- 插入前b(C)=≯：则h(L)=h0-1，h(R)=h0；插入后，b(B)=≮，b(D)=⊥。
这种情况的旋转虽然看起来比较复杂，但却可以看成两个连续的单次旋转：
总结
- 一个节点插入数据，当子节点高度增加时，平衡性向该方向增加；
- 出现节点不稳定的情况时，要进行旋转调整以保持节点的平衡性；
- 旋转有两种基本操作，单次左旋转和单次右旋转；
- 当节点不稳定时，根据其平衡性倾斜方向、该方向子节点的平衡性倾斜方向可分为4种情况：LL、LR、RL、RR（左左、左右、右左、右右）；分别对应右单旋（Single: Right Rotate），左右双旋（Double: Left-Right Rotate），右左双旋（Double: Right-Left Rotate），左单旋（Single: Left Rotate）；
- 旋转后，节点的平衡性恢复，且高度不增加。
