AVL（Adelson-Velskii 和 Landis）树是带有平衡条件的二叉查找树。这个平衡条件必须要容易保持，而且必须保证树的深度是 。最简单的想法是要求左右子树具有相同的高度，这种想法并不强求树的深度要浅。
另一种平衡条件是要求每个节点都必须要有相同高度的左子树和右子树。如果空子树的高度定义为 -1（通常就是这么定义的），那么只有具有 个节点的理想平衡树（perfectly balanced tree）满足这个条件。因此。虽然这种平衡条件保证了树的深度小，但是它太严格，难以使用，需要放宽条件。
一颗 AVL 树是其每个节点的左子树和右子树的高度最多差 1 的二叉查找树。（空树的高度定义为 -1。）大致上讲，一个 AVL 树的高度最多为 ，但是实际上的高度只比
稍微多一些。
因此，除去可能的插入外（我们将假设懒惰删除），所有的树操作都可以以时间 执行。当进行插入操作时，我们需要更新通向根节点路径上那些节点的所有平衡信息，而插入操作隐含着困难的原因在于，插入一个节点可能破坏 AVL 树的特性。如果发生这种情况，那么就要把性质恢复以后才认为这一步插入完成。事实上，这总可以通过对树进行简单的修正来做到，我们称其为旋转（rotation）。
在插入以后，只有那些从插入点到根节点的路径上的节点的平衡可能被改变，因为因为只有这些节点的子树可能发生变化。当我们沿着这条路径上行到根并平衡信息时，我们可以找到一个节点，它的新平衡破坏了 AVL 条件。我们需要在第一个这样的节点（即最深的节点）重新平衡这棵树，并递归操作，直至整棵树满足 AVL 特性。
我们把必须重新平衡的节点叫做 。由于任意节点最多有两个儿子，因此高度不平衡时，
点的两棵子树的高度差 2。这种不平衡可能出现在下面四种情况中：
- 对
的左儿子的左子树进行一次插入；
- 对
- 对
- 对
情形 1 和 4 是关于 点的镜像对称，而情形 2 和 3 是关于
点的镜像对称。因此，理论上只有两种情况，当然从编程的角度来看还是四种情形。
第一种情形是插入发生在“外边”的情形（即左—左的情形或者右—右的情形），该情形通过对数的一次单循环（single rotation）而完成调整。第二种情形是插入发生在“内部”的情形（即左—右的情形或右—左的情形），该情形通过稍微复杂些的双旋转（double rotation）来处理。这些都是对树的基本操作，它们多次用于平衡树的一些算法中。
无论是单循环还是双循环，编程人员都必须记住：树的其余部分必须知晓该变化。
除几种情形外，编程的细节是相当简单的。为将关键字是 X 的一个新节点插入到一棵 AVL 树 T 中，我们递归地将 X 插入到 T 的相应的子树（称为 ）中。如果
的高度不变，那么插入完成。否则，如果在 T 中出现高度不平衡，那么我嫩根据 X 以及 T 和
中的关键字做适当的单旋转或者双旋转，更新这些高度（并解决好与树的其余部分的连接），从而完成插入。由于一次旋转足以解决问题，因此仔细地编写非递归程序一般说来要比编写递归程序快很多。然而，要想把非递归程序编写正确是相当困难的，因此许多程序人员还是用递归的方法实现 AVL 树。
另一种效率问题涉及高度信息的存储。由于真正需要的实际上就是子树高度的差，应该保证它很小。如果我们真的尝试这种方法，则可用两个二进制位（代表 +1、0、-1）表示这个差。这么做将避免平衡因子的重复计算，但是却丧失某些简明性。最后的程序多多少少要比在每一个节点存储高度时复杂。如果编写递归程序，那么速度恐怕不是主要考虑的问题。此时，通过存储平衡因子所得到的些微的速度优势很难抵消清晰度和相对简明性的损失。不仅如此，由于大部分机器存储的最小单位是 8 个二进制位，因此，所有的空间量不可能有任何差别。8 位使我们能够存储高达 255 的绝对高度。既然平衡树是平衡的，当然也就不可想象这会不够用。
一些例程的实现逻辑
一些声明
#ifndef _AVvlTree_H
struct AvlNode;
typedef struct AvlNode *Postion;
typedef struct AvlNode *AvlTree;
AvlTree MakeEmpty(AvlTree T);
Postion Find(ElementType X, AvlTree T);
Postion FindMin(AvlTree T);
Postion FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(Postion P);
#endif /* _AvlTree_H */
/* Place in the implementation file */
struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
一个快速的函数返回节点的高度（这个函数必须处理 NULL 指针的情形）
static int
Height( Position p)
{
if (P == NULL)
return -1;
else
return P->Height;
}
基本的插入例程（SingleRotateWithLeft 把左边的树变成右边的树，并返回指向新根的指针。SingleRotateWithRight 做的工作恰好相反）
AvlTree
Insert(ElementType X, AvlTree T)
{
if( T == NULL)
{
/* Create and return a one-node tree. */
T = malloc( sizeof(struct AvlNode))
if (T == NULL)
FatalError("Out of space!!!")
else
{
T-> = X; T->Height = 0;
T->Left = T->Right = NULL;
}
}
else
if( X < T->Element)
{
T->Left = Insert(X, T->Left);
if (Height(T->Left)-Height(T->Right) == 2)
if(X < T->Left->Element)
T = SingleRotateWithLeft( T );
else
T = DoubleRotateWithLeft( T );
}
else
if (X > T->Element)
{
T->Right = Insert(X, T->Right);
if(Height( T->Right) - Height(T->Left) == 2)
T = SingleRotateWithRight( T );
else
T = DoubleRotateWithRight( T );
}
/*Else X is in the tree already; we'll do nothing */
T->Height = Max( Height(T->Left), Height( T->Right)) + 1;
return T;
}
单旋转
static Position
SingleRotateWithLeft( Postion K2)
{
Postion K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
K2->Height = Max(Height(K2->Left),Height(K2->Right)) + 1,
K1->Height = Max(Height(K1->Left),K2->Height)+1;
return K1; /* New Root */
}
双旋转
/* This function can be called only if K3 has a left child */
/* child and K3's left child has a right child */
/* Do the left-right double rotation */
/* Update heights, then return new root */
static Position
DoubleRotateWithLeft( Postion K3)
{
/* Rotate between K1 and K2 */
K3->Left = SingleRotateWithRight( K3->Left );
/* Rotate between K3 and K2 */
return SingleRotateWithLeft(K3);
}
对 AVL 树的删除多少要比插入复杂。如果删除操作相对较少，那么懒惰删除恐怕是最好的策略。
网友评论