平衡的二叉搜索树 (AVL)

性质

可以为空
具有 n 个结点的 AVL 树，高度为 O (log n)
如果 T是一棵 AVL树，那么它的左右子树 TL、TR 也是 AVL 树
- 并且 | hL-hR|≤1
- hL、hR 是它的左右子树的高度

平衡因子

平衡因子，bf (x) :
Bf (x) = h(左孩子) - h(右孩子)
结点平衡因子可能取值为 0，1 和 -1

AVL 树结点的插入

插入与 BST 一样:新结点作叶结点调整后的状态

结点原来是平衡的，现在成为左重或右重的，修改相应前驱结点的平衡因子
结点原来是某一边重的，而现在成为平衡的了
- 树的高度未变，不修改
结点原来就是左重或右重的，又加到重的一边
- 不平衡
- “危急结点”

不平衡的情况

AVL 树任意结点 a 的平衡因子只能是 0，1，-1
a 本来左重，a.bf==-1，插入一个结点导致 a.bf 变为-2
- LL 型:插入到 a 的左子树的左子树，左重+左重，a.bf 变为-2
- LR 型: 插入到 a 的左子树的右子树 •左重+右重，a.bf 变为-2
类似地， a.bf==1，插入新结点使得 a.bf 变为2
- RR 型:导致不平衡的结点为 a 的右子树的右结点
- RL 型:导致不平衡的结点为 a 的右子树的左结点

AVL 树的效率

检索、插入和删除效率都是 O(1og2 n)
具有 n 个结点的 AVL 树的高度一定是 O(log n)
AVL 树适用于组织较小的、内存中的目录
- 存放在外存储器上的较大的文件
B树/B+树，尤其是B+树

调整平衡

AVL 树结点的删除

删除是插入的逆操作。从删除结点的意义上来说，AVL 树的删除操作与 BST 一样AVL 树的删除是比较复杂过程，下面具体讨论一下删除的过程。

AVL树需要调整的地方
- 删除结点后可能导致子树的高度以及平衡因子的变化
- 沿着被删除结点到根结点的路径来调整这种变化
需要改动平衡因子，则修改之
如果发现不需要修改则不必继续向上回溯
- 布尔变量 modified 来标记，其初值为 TRUE
- 当 modified = FALSE 时，回溯停止

AVL 树的高度

n 个结点的 AVL 树的最大高度不超过 Klog2 n，这里 K 是一个小的常数

伸展树

一种自组织数据结构
- 数据随检索而调整位置
- 汉字输入法的词表
伸展树不是一个新数据结构，而只是改进 BST 性能的一组规则
- 保证访问的总代价不高，达到最令人满意的性能
- 不能保证最终树高平衡

展开 (splaying)

访问一次结点 (例如结点 x) ，完成一次称为展开的过程
- x 被插入、检索时，把结点 x 移到 BST 的根结点
- 删除结点 x 时，把结点 x 的父结点移到根结点
像在 AVL 树中一样，结点 x 的一次展开包括一组旋转 (rotation)
- 调整结点 x、父结点、祖父结点的位置
- 把 x 移到树结构中的更高层

伸展树的调整过程

一系列双旋转（左旋zag，右旋zig），直到结点x到达根结点或者根结点的子结点
如果结点x到达根结点的子结点，进行一次单旋转使结点 x 成为根结点
- 这个过程趋向于使树结构重新平衡
- 使访问最频繁的结点靠近树结构的根层，从而减少访问代价

Splay 树的操作

struct TreeNode {
    intkey;
    ELEMvalue;
    TreeNode *father, * left, *right;
};
Splay(TreeNode *x, TreeNode *f); // 把 x 旋转到祖先 f 下面
Splay(x, NULL);                 //把x旋转为根
Find(int k) ;
Insert(int k);
Delete(TreeNode *x) ;      //删除x节点
DeleteTree(TreeNode *x);  //删除x子树

void Splay (TreeNode *x, TreeNode *f) { 
    while (x->parent != f) {
        TreeNode *y = x-> parent, *z = y-> parent;
        if (z != NULL) { // 祖父不空
        if (z->lchild == y) {
            if (y->lchild == x)
            { Zig(y); Zig(x); } // 一字型双右旋
            else { Zag(x); Zig(x); } // x左旋上来，接着右旋
        }else{
            if (y->lchild == x)
            { Zig(x); Zag(x); } // x右旋上来，接着左旋
            else { Zag(y); Zag(x); }// 一字型双左旋
           } 
       }else{
        if (y->lchild == x) Zig(x);   //右单旋
        else Zag(x); } 
    }
    if (x->parent == NULL) Root = x;
}

删除大于 u 小于 v 的所有结点

把 u 结点旋转到根
把v旋转为u的右儿子
删除 v 结点的左子树

void DeleteUV(TreeNode* rt, TreeNode* u, TreeNode* v ) {
    Splay(u, NULL); 
    Splay(v, u); 
    DeleteTree(v->lchild); 
    v->lchild = NULL;
}

利用这个操作我们可以实现对区间的查询和删除操作，效率很高。

伸展树的效率

n 个结点的伸展树,进行一组m次操作 (插入、删除、查找操作) ，当 m≥n 时，总代价是 O(m logn)
伸展树不能保证每一个单个操作是有效率的
即每次访问操作的平均代价为 O(log n)

伸展树的应用

伸展树作为一种时间效率很高、空间要求不大的数据结构，有很大的用武之地。下面就通过一个例子说明伸展树在解题中的应用。

例：营业额统计 Tur nover ( 湖南省队 2002 年选拔赛) 题目大意 Tiger 最近被公司升任为营业部经理，他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger 拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于节假日，大减价或者是其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或是很低，这就证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：

该天的最小波动值= min { | 该天以前某一天的营业额-该天的营业额 | }

当最小波动值越大时，就说明营业情况越不稳定。而分析整个公司的从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助 Tiger 来计算这一个值。

注：第一天的最小波动值为第一天的营业额。

数据范围：天数 n≤32767，每天的营业额 ai≤1,000,000。最后结果 T≤231。

初步分析题目的意思非常明确，关键是要每次读入一个数，并且在前面输入的数中找到一个与该数相差最小的一个。

我们很容易想到 O(n2)的算法：每次读入一个数，再将前面输入的数一次查找一遍，求出与当前数的最小差值，记入总结果 T。但由于本题中 n 很大，这样的算法是不可能在时限内出解的。而如果使用线段树记录已经读入的数，就需要记下一个 2M 的大数组，这在当时比赛使用 TurboPascal 7.0 编程的情况下是不可能实现的。而前文提到的红黑树与平衡二叉树虽然在时间效率、空间复杂度上都比较优秀，但过高的编程复杂度却让人望而却步。于是我们想到了伸展树算法。

算法描述进一步分析本题，解题中，涉及到对于有序集的三种操作：插入、求前趋、求后继。而对于这三种操作，伸展树的时间复杂度都非常优秀，于是我们设计了如下算法：

开始时，树 S 为空，总和 T 为零。每次读入一个数 p，执行 Insert(p,S)，将 p 插入伸展树 S。这时，p 也被调整到伸展树的根节点。这时，求出 p 点左子树中的最右点和右子树中的最左点，这两个点分别是有序集中 p 的前趋和后继。然后求得最小差值，加入最后结果 T。

解题小结由于对于伸展树的基本操作的平摊复杂度都是 O(log n)的，所以整个算法的时间复杂度是 O(nlog n)，可以在时限内出解。而空间上，可以用数组模拟指针存储树状结构，这样所用内存不超过 400K，在 TP 中使用动态内存就可以了。

编程复杂度方面，伸展树算法非常简单，程序并不复杂。虽然伸展树算法并不是本题唯一的算法，但它与其他常用的数据结构相比还是有很多优势的。下面的表格就反映了在解决这一题时各个算法的复杂度。从中可以看出伸展树在各方面都是优秀的，这样的算法很适合使用。

改进的二叉搜索树-AVL树与伸展树(Splay)