种树系列二:伸展树

作者: shad0w_walker(admin) 分类: 种树系列 发布时间: 2015-09-15 11:47 ė 6 没有评论

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

伸展树是一种基于平衡树的二叉查找树,同样是平衡二叉查找树,它比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(插入、求最大值、最小值)

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

本文出自shad0w_walker,转载时请注明出处及相应链接。

本文永久链接: https://www.sdwalker.com/archives/361.html

发表评论

电子邮件地址不会被公开。 必填项已用*标注

返回顶部