1.4 平衡二叉树
平衡二叉树（Balanced Binary Tree）是对二叉查找树的一种改进，又被称为AVL树。二叉查找树的查找复杂度与高度有关，但是在一些情况下，二叉查找树会退化成线性，导致复杂度变高。平衡二叉树能很好地维持二叉查找树的平衡，将复杂度维持在O（log2N）。平衡二叉树具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
AVL树编程复杂度较高。本节将讲解两种平衡树：Treap和Splay树。它们不严格平衡，但是实现相对简单。
1.4.1 Treap
由二叉查找树和堆合并构成的新数据结构被称为Treap。它的名字取了Tree和Heap各一半，又称为树堆。Treap巧妙地通过随机数实现了平衡。
1.Treap的数据结构
Treap每个节点的数据域包含2个值，即key和weight。其中，key值和原来的二叉查找树一样，满足左子树<根节点<右子树；weight值是随机产生的，在Treap中，weight值满足堆的性质，根节点的weight值不大于（或不小于）左右子节点。Treap的数据结构如图1.4所示。
Treap节点的数据结构如下所述。
图1.4 Treap的数据结构
2.Treap的操作
简单来说，为了防止二叉查找树退化成一条链，Treap为每一个节点赋予一个随机值，然后对这个随机值按照堆的性质去调整。所以，Treap的大部分操作和二叉查找树相同，不过在每一次操作后需要做出调整。这个调整的过程被称为旋转，每次旋转在不改变key值顺序的情况下，可使weight值满足堆性质。旋转分为左旋和右旋。将右子节点旋转至根，所以称为左旋，反之将左子节点旋转至根，称为右旋，如图1.5和图1.6所示。
图1.5 Treap右旋（一）
图1.6 Treap右旋（二）
左旋是右旋的镜像操作。
旋转操作的实现如下所述。
1.4.2 Splay树
Splay树又称为伸展树，也称为自适应查找树，是一种用于保存有序集合的、简单高效的数据结构。伸展树实质上是一个二叉查找树，允许查找、插入、删除、删除最小、删除最大、分割、合并等许多操作。这些操作的时间复杂度为O（log2N）。
1.Splay树的原理
伸展树的出发点是这样的：考虑到局部性原理（刚被访问的内容下次可能仍会被访问，查找次数多的内容可能下一次会被访问），为了使整个查找时间更少，被查频率高的那些节点应当经常处于靠近树根的位置。因此，可得到以下方案：每次查找节点之后对树进行重构，把被查找的节点移到树根，这种自调整形式的二叉查找树就是伸展树。每次对Splay树进行操作后，它均会通过旋转的方式把被访问节点旋转到树根的位置。
2.Splay树的基本操作
Splay树的操作是在保持Splay树有序性的前提下，通过一系列旋转操作将树中的元素X调整至树根部的操作，Zig表示右旋，Zag表示左旋。
Splay树的基本操作包括三种情况：
（1）Zig或Zag：当目标节点是根节点的左子节点或右子节点时，进行一次单旋转，将目标节点调整到根节点的位置。Splay树的Zig操作如图1.7所示。
图1.7 Splay树的Zig操作
（2）Zig-Zig或Zag-Zag：目标节点X的父节点Y的父节点是根节点，其中X和Y都是其父节点的左子节点或者都是其父节点的右子节点。Splay树的Zig-Zig操作如图1.8所示。
图1.8 Splay树的Zig-Zig操作
（3）Zig-Zag或Zag-Zig：目标节点X的父节点Y的父节点是根节点，其中X和Y，一个是其父节点的左子节点，另一个是其父节点的右子节点。Splay树的Zig-Zag操作如图1.9所示。
图1.9 Splay树的Zig-Zag操作
例如，将节点1旋转到根节点的操作示例如图1.10所示。
图1.10 Splay树的操作示例
Splay树代码实现如下所述。
1.4.3 例题讲解
例1-3 Black Box
Time Limit:1000 ms Memory Limit:10000 KB
题目描述：
ADD和GET操作。ADD x操作表示向序列中添加一个数x，第i次GET表示获取序列中第i小的数。ADD和GET操作都不超过30000次。A（1）,A（2）…,A（M）表示依次向序列中添加的数，A的值不超过2000000000。序列u（1）,u（2）,…,u（N）是非递减序列，N≤M且对于每一个p（1≤p≤N），p≤u（p）≤M，u（p）表示分别在进行多少次ADD操作后再进行GET操作。例如，u（p）表示插入u（p）个数后输出第p小的数。
输入：
第一行输入两个整数M和N，第二行包含M个数表示A（1）,A（2）,…,A（M），第三行包含N个整数表示u（1）,u（2）,…,u（N）。
输出：
对于每一个GET输出结果，每行输出一个数。
样例输入：
7 4
3 1 -4 2 8 -1000 2
1 2 6 6
样例输出：
3
3
1
2
题目来源：POJ 1442。
解题思路：
给定一个序列包含两个操作：一个是向序列中插入一个数；另一个是查询序列中第k小的值。这两个操作都可以由Treap实现。
题目实现（节点定义和旋转操作同上，略）：
例1-4 营业额统计
Time Limit:5000 ms Memory Limit:162 MB
题目描述：
Tiger最近被公司升任为营业部经理。他上任后接受公司交给的第一项任务便是统计并分析公司成立以来的营业情况。Tiger拿出了公司的账本，账本上记录了公司成立以来每天的营业额。分析营业情况是一项相当复杂的工作。由于在节假日、大减价或者其他情况的时候，营业额会出现一定的波动，当然一定的波动是能够接受的，但是在某些时候营业额突变得很高或者很低，证明公司此时的经营状况出现了问题。经济管理学上定义了一种最小波动值来衡量这种情况：该天的最小波动值越大时，说明营业情况越不稳定。而分析整个公司从成立到现在营业情况是否稳定，只需要把每一天的最小波动值加起来就可以了。你的任务就是编写一个程序帮助Tiger来计算这一个值。第一天的最小波动值为第一天的营业额。
输入：
第一行为正整数，表示该公司从成立一直到现在的天数，在接下来的n行中的每行都有一个整数（有可能有负数），表示第i天公司的营业额。
输出：
在输出文件中仅有一个正整数，即Sigma（每天最小的波动值）。结果小于231。
样例输入：
6
5
1
2
5
4
6
样例输出：
12
提示：
结果说明：5+|1-5|+|2-1|+|5-5|+|4-5|+|6-5|=5+4+1+0+1+1=12
题目来源：HYSBZ 1588。
解题思路：
Splay入门题，考察对序列的基本操作。
题目实现：
