种树系列二:伸展树
时隔好久又来写种树系列啦。
伸展树是一种基于平衡树的二叉查找树,同样是平衡二叉查找树,它比AVL树有不少先进的地方,代码复杂度低,可操作性好,时间复杂度更低。
伸展树的所有操作都与splay有关,在对一个节点进行访问时,先通过splay操作将其旋转至根节点,调用Splay(x,rt),可以将节点x旋转至rt处。Splay的操作是一个自底向上的过程,通过不断的旋转使节点x向上,而每一次旋转有三种情况
- Zig 或 Zag
- Zig-Zig 或 Zag-Zag
- 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(插入、求最大值、最小值)
这些裸题真的都是很裸啊。。。。。。
本文出自shad0w_walker,转载时请注明出处及相应链接。
本文永久链接: https://www.sdwalker.com/archives/361.html