种树系列二：伸展树

时隔好久又来写种树系列啦。

伸展树是一种基于平衡树的二叉查找树，同样是平衡二叉查找树，它比AVL树有不少先进的地方，代码复杂度低，可操作性好，时间复杂度更低。

伸展树的所有操作都与splay有关，在对一个节点进行访问时，先通过splay操作将其旋转至根节点，调用Splay(x,rt)，可以将节点x旋转至rt处。Splay的操作是一个自底向上的过程，通过不断的旋转使节点x向上，而每一次旋转有三种情况

1. Zig 或 Zag
2. Zig-Zig 或 Zag-Zag
3. Zig-Zag 或 Zag-Zig

具体的旋转过程在《Data Structures and Algorithmn Analysis》以及许多博客上已经讲的很详细了，可以参考【转】【伸展树Splay Tree】 – kuangbin – 博客园

接下来讲的是伸展树的性质以及具体用途

1、伸展树是一种基于平衡树的二叉查找树。我们知道，在平衡树中对一个节点的访问可以在\(O(\log{N})\)复杂度内实现，伸展树虽然不能保证每次操作都能在\(O(\log{N})\)内实现，且存在\(O(N)\)的可能，但是M次操作最多的花费是\(O(M\log{N})\)，所以伸展树的摊还时间复杂度是\(O(\log{N})\)。

以下给出伸展树的通用操作

点击此处展开代码

2、伸展树是一种基于平衡树的二叉查找树。对于查找树的一个节点来说，它的左儿子key值小于它的key值，右儿子key值大于它的key值，这种排列的有序性使得查找操作变得很简单，只要对一棵子树保存其size值。size一般是子树内节点数量，但也是随情况而变化的（例如HDU3436需要离散化的）

以下给出常见的Find_Min，Find_MAX，Find_Kth操作

点击此处展开代码

3、伸展树是一种基于平衡树的二叉查找树。平衡树的二叉属性使得它能够完成同为二叉树的线段树的所有操作，不同的是，线段树是将区间分段成已经处理好的许多小段，然后再将小段合并以对区间操作，而伸展树则是通过splay操作得到包含[l,r]区间的子树，直接对这棵子树的根节点进行操作即可。

例：区间加值（线段树经典操作）

点击此处展开代码

4、上一段说到伸展树能够解决线段树的所有操作，而且同时也能解决很多线段树不能解决的操作，因为伸展树是动态的，可以进行插入和删除点的操作

以下是插入节点和删除根节点的操作

点击此处展开代码

以上应该就是伸展树的所有操作了，基本上线段树掌握的好的话，伸展树的操作应该还是得心应手的。

下面是一些伸展树裸题，都来自[kuangbin]伸展树(splay tree)练习专题

POJ 3468（区间加值、区间求和）

POJ 3481（插入、删除、求最大值、最小值）

HDU 1754（单点修改、区间求最值）

HDU 1890（删除、区间反转）

HDU 3436（离散化、区间转移、单点查询）

HDU 3487（区间转移、区间反转）

HYSBZ 1588（插入、求最大值、最小值）

这些裸题真的都是很裸啊。。。。。。