高度由习惯堆积

分类 数据结构:Splay 下的文章

March 26, 2019

HDU1890 Robotic Sort

题目题目大意是让你找在一个区间内找一个最小权值的点,让它通过旋转的方式换到最前面。思路注意Splay的性质:中序遍历不变。所以这里就可以把Splay看作一个超级数组,而不是通常定义的二叉查找树(左边的子树权值都小于它,右边的子树权值都大于它)。然后它就可以通过打标记的方式实现区间的翻转操作。具体方法是:如果要对一段区间进行操作的话,只要:int L=find(l-1),R=find(r+1)...
March 21, 2019

Splay初步

这里主要讲一讲Splay的基础操作(插入,删除)。前言Splay本质上是一棵二叉查找树。这种树有许多美妙的性质:若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值; 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值; 它的左、右子树也分别为二叉查找树。但是它也有缺点:可能退化成一条链。所以Splay就是通过不断地对树中的点进行旋转和变换,让树的高度保持在logn。旋转y...