by eGust (转载请注明)
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）；
- 旋转后，节点的平衡性恢复，且高度不增加。
C#实现
1. 基本类型定义：
enum BalanceFactor {
LeftTooHigh = -2,
LeftHigher = -1,
Balanced = 0,
RightHigher = 1,
RightTooHigh = 2 }
class Node {
BalanceFactor BalanceFactor;
Node Left, Right;
TKey Key;
TValue Value;
}
struct AVLTree
{
public Node Root; // 根节点
public int Count; // 用来记录节点数量
public uint LRQueue; // 用于插入操作时表示方向
public bool Changed; // 用于判断一个操作是否使平衡性改变
}
2. 基本旋转操作：
static void RotateLeft(ref Node Node)
/*
* in : Node
* out: Node.Right
* ----------------
* N R
* \ -> /
* R N
*/
{
Node Temp = Node;
Node = Node.Right;
Temp.Right = Node.Left; // IN.Right = OUT.Left
Node.Left = Temp; // OUT.Left = IN
}
3. 旋转并计算平衡因子：
static void RotationLLCase(ref Node Node)
/* case: Right(C) Rotation
* C<<
* / (R) B-
* B< -> / \
* / C A. C-
* A.
*/
{
Node.BalanceFactor = BalanceFactor.Balanced;
RotateRight(ref Node);
Node.BalanceFactor = BalanceFactor.Balanced;
}
static void RotationLRCase(ref Node Node)
/* case: Left(A), Right(C) Rotation
* C<< C<<
* / (L) / (R) B-
* A> -> B. -> / \
* \ A / C A? C?
* B. A>
*/
{
RotateLeft(ref Node.Left);
RotateRight(ref Node);
RebalanceDoubleRotated(Node);
}
static void RebalanceDoubleRotated(Node Node)
{
Node.Left.BalanceFactor = (BalanceFactor)
(IsRightHigher(Node.BalanceFactor)*(int)BalanceFactor.LeftHigher);
Node.Right.BalanceFactor = (BalanceFactor)
(IsLeftHigher(Node.BalanceFactor)*(int)BalanceFactor.RightHigher);
Node.BalanceFactor = BalanceFactor.Balanced;
}
4. 插入递归操作：
Node Insert(TKey Key, ref Node Node)
{
if (Node == null) return (Node=NewNode(Key));
int Comp = Key.CompareTo(Node.Key);
if (Comp == 0) return (null);
if (Comp < 0)
{
if (Node.Left == null)
{
Node.IncreaseToLeft(ref Node.BalanceFactor);
PushDirection(Direction.LeftGo);
return (Node.Left = NewNode(Key));
}
BalanceFactor bf = Node.Left.BalanceFactor;
Node ret = Insert(Key, ref Node.Left, Adding);
if ((!Tree.Changed) || (bf != BalanceFactor.Balanced) ||
(Node.Left.BalanceFactor == BalanceFactor.Balanced))
return (ret);
bf = Node.BalanceFactor;
Node.IncreaseToLeft(ref bf);
PushDirection(Direction.LeftGo);
if (bf == BalanceFactor.LeftTooHigh)
{
RebalanceRotated[Tree.LRQueue & 3](ref Node);
Tree.Changed = false;
}
else Node.BalanceFactor = bf;
return (ret);
}
else { } // 与上面方向相反
}
enum Direction { LeftGo = 0, RightGo = 1 }
void PushDirection(Direction Direct)
{ Tree.LRQueue = (Tree.LRQueue<<1)|(uint)Direct; }
delegate void Rebalancer(ref Node Node);
static Rebalancer[] RebalanceRotated = new Rebalancer[4];
RebalanceRotated[0] = RotationLLCase;
RebalanceRotated[1] = RotationRLCase;
RebalanceRotated[2] = RotationLRCase;
RebalanceRotated[3] = RotationRRCase;
删除（Deletion）
先来讨论一下树高度的减少：
假设：有节点N，h(N)=h0，现在有使N节点的左树高度减少1的删除。
- 当b(N)=≮时，由于h(N)=h0，故h(N.l)=h0，(N.r)=h0-1；删除后，h(N.l)=h(N.r)=h0-1，所以h(N)= h0-1，高度减少，b(N)=≤；
- 当b(N)=⊥时，由于h(N)=h0，故h(N.l)=h0-1，(N.r)=h0-1；删除后，h(N.l)=h0-2，h(N.r)=h0-1，所以h(N)= h0-1，高度不变，b(N)=≯；
- 当b(N)=≯时，由于h(N)=h0，故h(N.l)=h0-1，(N.r)=h0-2；删除后，h(N.l)= h(N.r)=h0-2，所以h(N)= h0-1，高度减少，b(N)=⊥。
可以看出，当原来的平衡性不为⊥且删除后为⊥时，高度减少了（此外还有一种是叶子节点变为空节点的情况）。
删除操作和BST的删除一样，如果是叶子节点则直接删除；否则，取出删除节点的右子树中的最小值，替换掉删除节点（或左子树的最大值）。但在AVL Tree中，还要进行回溯调整；由于这里设计的AVL Tree并未提供父节点的方法，所以同样，这里采用递归设计。
在前一节中[Note 1]讲到，左子树插入后出现根节点不稳定，则左子节点只能有≮、≯两种情况。但在删除中，还会出现左子节点平衡性为⊥的第三种情况。
(C) b(B)=⊥。图上很清楚，对D节点进行一次右旋即可。旋转后，原节点D被B代替，而B和D节点都恢复了稳定；和删除前相比，根节点高度没变。
总结
- 一个节点删除数据，当子节点高度减少时，平衡性向反方向增加；
- 出现节点不稳定的情况时，要进行旋转调整以保持节点的平衡性；
- 与插入旋转相同的旋转后，节点的平衡性恢复，且高度减少；
- 除插入的4种情况外，另有两种情况，即删除前减少方向的子节点平衡；旋转后稳定性恢复，但不平衡，且高度未减少。
C#实现
1. 基本删除操作：
static bool RebalanceRemovedLeft(ref Node Node)
{ // 返回值表示高度是否减少了
IncreaseToRight(ref Node.BalanceFactor);
if (Node.BalanceFactor != BalanceFactor.RightTooHigh)
return (Node.BalanceFactor == BalanceFactor.Balanced);
BalanceFactor bf;
if (Node.Right != null) bf = Node.Right.BalanceFactor;
else bf = BalanceFactor.Balanced;
if (bf == BalanceFactor.LeftHigher)
RotationRLCase(ref Node);
else
{
Node.BalanceFactor = (BalanceFactor)(
IsBalanced(bf) * (int)BalanceFactor.RightHigher);
RotateLeft(ref Node);
IncreaseToLeft(ref bf);
Node.BalanceFactor = bf;
}
return (true);
}
2. 删除递归操作：
Node ExtractMinLeaf(ref Node Node)
{
Node ret;
if (Node.Left == null)
{
ret = Node;
Node = Node.Right;
Tree.Changed = true;
} else {
BalanceFactor bf = Node.Left.BalanceFactor;
ret = ExtractMinLeaf(ref Node.Left);
Tree.Changed = ((Tree.Changed) && ((Node.Left == null) || (
((bf != BalanceFactor.Balanced) &&
(Node.Left.BalanceFactor == BalanceFactor.Balanced))
)) && (Node.RebalanceRemovedLeft(ref Node)));
}
return (ret);
}
Node ExtractNode(TKey Key, ref Node Node)
{
int Comp = Key.CompareTo(Node.Key);
if (Comp == 0)
{
Node ret = Node;
if (Node.Right == null)
{
Node = Node.Left;
Tree.Changed = true;
return (ret);
}
BalanceFactor bf = Node.Right.BalanceFactor;
Node = ExtractMinLeaf(ref Node.Right);
Node.Left = ret.Left;
Node.Right = ret.Right;
Node.BalanceFactor = ret.BalanceFactor;
Tree.Changed = ((Tree.Changed) && ((Node.Right == null) || (
((bf != BalanceFactor.Balanced) &&
(Node.Right.BalanceFactor == BalanceFactor.Balanced)))
) && (Node.RebalanceRemovedRight(ref Node)));
ret.Left = ret.Right = null;
return (ret);
}
if (Comp < 0)
{
if (Node.Left == null) return (null);
BalanceFactor bf = Node.Left.BalanceFactor;
Node ret = ExtractNode(Key, ref Node.Left);
Tree.Changed = ((Tree.Changed) && ((Node.Left == null) || (
((bf != BalanceFactor.Balanced) &&
(Node.Left.BalanceFactor == BalanceFactor.Balanced)))
) && (Node.RebalanceRemovedLeft(ref Node)));
return (ret);
}
else { } // 与上面方向相反
AVL Tree的遍历
和其它BST的遍历相同，递归的就不说了；非递归版本可以用栈（Stack）来实现，这里是伪代码：
[nothing] PushAllLeft {Node}:
while ( Node ≠ null ):
<Stack>:Push{Node}
[Node] <- Node.Left
[Node] GetNext {}:
[Result] <- <Stack>:Pop{}
PushAllLeft {Result.Right}
Lookup:
PushAllLeft{Root}
while ( not Emtpy{Stack} ):
Do Look: [Current] <- GetNext{}
关于AVL Tree的性能
尽管从网上各种资料来看，AVL Tree与R-B Tree （Red-Black Tree，红黑树，也是一种BST，平衡度不及AVL Tree高） 相比，在统计上不似乎及 R-B Tree ，而且 R-B Tree 的应用也大有取代 AVL Tree 的趋势。但从我在 Delphi 2009 上写的版本来看，AVL Tree不论在空间上还是速度上都比 R-B Tree 有优势。200万个节点的插入、搜索显示，R-B Tree 的插入时间要比 AVL Tree 多花 16.7%，而在搜索上多花 7.7%；在空间占用上，AVL Tree 只需要记录平衡性的一个不超过 4 bits 的 Balance Factor，而 R-B Tree 则需要一个父指针和一个 1 bit 的 Color Flag。由于我的 Tree 结构需要一个 Extraction 操作，Removal 再在其基础上完成，而网上的 R-B Tree 资料似乎都没有 Extraction ，所以对 Removal 的测试暂时搁置了。但基于前面的测试结果，我不打算实现 R-B Tree 了，当然如果在使用中栈（Stack）资源比较紧张的话， R-B Tree 会是一个好选择的。
留言列表
