non-rotating Treap op.1

之前只学过Treap,然后还没写完就不知道去干啥了,昨天刚好有机会,就请了机房数据结构大佬——xtr教了教我,感觉还不是很难啊。数据结构真有趣

首先假装大家都会了二叉搜索树,并且知道了为什么它会变得不平衡。

然后呢,就可以像随机化快排一样的思路,把读入ramdom shuffle一下,是不是期望上就是平衡了呀?

不过由于输入与查询是有先后次序的,所以我们只能在每个节点上动手脚。

所以我们引入一个随机的priority值,作为每个节点的属性之一,然后要求:每个节点的priority都必须严格满足比父节点的大(或小),再以此建立一棵二叉搜索树,就成了“treap”(tree+heap)了呀!

可以证明,只要priority值与每个节点的键值确定,整棵树的形态就会确定了。

一般的treap对于priority满足靠旋转操作,想必大家都知道,这里就不再赘述。但是,有旋转的treap有几点不足:

  1. 不能进行“可持久化”;
  2. 不能快速地提取出一段区间;
  3. 不能实现区间反转;
  4. 想必还有很多啊……

所以,某位大佬突发奇想,就想出了一种新型的treap,它维持平衡的方式与treap相同,但是维护堆性质采取了不同的方法——分裂与合并。

首先说分裂:

分裂分为两种:按排名分裂与按键值分裂,我们可以分别命名为split_kth与split_key,他们的作用就是将一棵子树分裂为两颗,且左边的一棵排名/键值都小于等于k,右边大于k。

那么,可以怎么实现呢?

来看图:

一张图读懂split(逃

split

可以看出,split是一个递归的过程,边界条件是该子树为空

然后呢……详情见代码,不过还是推荐大家自己思考一下

[code language = cpp]

void split_key(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (key_of(rt) > k) y = rt, split_key(rt->ch[0], x, rt->ch[0], k);
else x = rt, split_key(rt->ch[1], rt->ch[1], y, k);
update(rt);
}

void split_kth(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (size_of(rt->ch[0]) + 1 ch[1], rt->ch[1], y, k – size_of(rt->ch[0]) – 1);
else y = rt, split_kth(rt->ch[0], x, rt->ch[0], k);
update(rt);
}

[/code]
然后是merge:

这就没split那么烦了,还要分成两个段,还要传参。只要几个简简单单的if语句就能够实现(不过当然是递归的啦)。

要注意的是,merge操作只能合并两端原本就绝对有序的子树——分别满足二叉搜索树的条件且左子树的节点键值全部小于右子树的。

一张图读懂merge(逃

merge

又是代码……我好懒啊

[code language = cpp]

node* merge(node* x, node* y)
{
if (x == NULL) return y;
if (y == NULL) return x;
if (x->p > y->p)
{
y->ch[0] = merge(x, y->ch[0]), update(y);
return y;
}
x->ch[1] = merge(x->ch[1], y), update(x);
return x;
}

[/code]

以上就是treap的基本操作,然后就可以利用这两个字操作来实现其他的一切啦!

首先是最基本的插入:

可以按照键值k分裂成两颗子树,再把新增的节点当做一颗子树一一合并即可。详见代码

[code language = cpp]

inline void insert(int k)
{
node *x, *y;
split_key(root, x, y, k);
root = merge(x, newnode(k));
root = merge(root, y);
}

[/code]

还有删除:

删除也分为按键值删除与按排名删除

方法是:先找到权值或排名为k的一棵子树或一个节点,之后根据要删除单个节点或是所有节点删除一棵子树或将两个子节点合并到原来节点的位置上。

代码:

[code language = cpp]

inline void del_subtree(node* &rt)
{
if (rt->ch[0] != NULL) del_subtree(rt->ch[0]);
if (rt->ch[1] != NULL) del_subtree(rt->ch[1]);
delete rt;
}

inline void del_node(node* &rt)
{
node* o = rt;
rt = merge(rt->ch[0], rt->ch[1]);
delete o;
}

bool delete_key(int k, bool op) //op == 0 delete one, op == 1 delete all
{
int flag = 1;
node *x, *y, *o;
split_key(root, x, y, k – 1);
split_key(y, o, y, k);
if (o == NULL) flag = 0;
if (op) del_subtree(o);
else del_node(o);
y = merge(o, y);
root = merge(x, y);
return flag;
}

bool delete_kth(int k)
{
bool flag = 1;
node *x, *y, *o;
split_kth(root, x, y, k – 1);
split_kth(y, o, y, 1);
if (o == NULL) flag = 0;
del_node(o);
y = merge(x, y);
root = merge(o, y);
return flag;
}

[/code]

还有排名、前驱、后继、第k小数等等我就不多说了,直接上代码(并不能掩饰我的懒)

[code language = cpp]

namespace nrtreap
{
struct node
{
int p, v, size;
node *ch[2];
} *root;

static inline int size_of(node* o)
{
if (o == NULL) return 0;
return o->size;
}

static inline int key_of(node* o)
{
if (o == NULL) return 0;
return o->v;
}

node* newnode(int x)
{
node *o = new node;
o->p = rand() % 100000 + 1, o->v = x, o->size = 1;
o->ch[0] = o->ch[1] = NULL;
return o;
}

inline void update(node* o)
{
o->size = size_of(o->ch[0]) + size_of(o->ch[1]) + 1;
}

node* merge(node* x, node* y)
{
if (x == NULL) return y;
if (y == NULL) return x;
if (x->p > y->p)
{
y->ch[0] = merge(x, y->ch[0]), update(y);
return y;
}
x->ch[1] = merge(x->ch[1], y), update(x);
return x;
}

void split_key(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (key_of(rt) > k) y = rt, split_key(rt->ch[0], x, rt->ch[0], k);
else x = rt, split_key(rt->ch[1], rt->ch[1], y, k);
update(rt);
}

void split_kth(node* rt, node* &x, node* &y, int k)
{
if (rt == NULL)
{
x = y = NULL;
return;
}
if (size_of(rt->ch[0]) + 1 ch[1], rt->ch[1], y, k – size_of(rt->ch[0]) – 1);
else y = rt, split_kth(rt->ch[0], x, rt->ch[0], k);
update(rt);
}

inline void insert(int k)
{
node *x, *y;
split_key(root, x, y, k);
root = merge(x, newnode(k));
root = merge(root, y);
}

inline void del_subtree(node* &rt)
{
if (rt->ch[0] != NULL) del_subtree(rt->ch[0]);
if (rt->ch[1] != NULL) del_subtree(rt->ch[1]);
delete rt;
}

inline void del_node(node* &rt)
{
node* o = rt;
rt = merge(rt->ch[0], rt->ch[1]);
delete o;
}

bool delete_key(int k, bool op) //op == 0 delete one, op == 1 delete all
{
int flag = 1;
node *x, *y, *o;
split_key(root, x, y, k – 1);
split_key(y, o, y, k);
if (o == NULL) flag = 0;
if (op) del_subtree(o);
else del_node(o);
y = merge(o, y);
root = merge(x, y);
return flag;
}

bool delete_kth(int k)
{
bool flag = 1;
node *x, *y, *o;
split_kth(root, x, y, k – 1);
split_kth(y, o, y, 1);
if (o == NULL) flag = 0;
del_node(o);
y = merge(x, y);
root = merge(o, y);
return flag;
}

int rank(int k)
{
node *x, *y;
split_key(root, x, y, k – 1);
int ret = size_of(x) + 1;
root = merge(x, y);
return ret;
}

int prev(int k)
{
node *x, *y, *o;
split_key(root, x, y, k – 1);
split_kth(x, x, o, size_of(x) – 1);
int ret = key_of(o);
x = merge(x, o);
root = merge(x, y);
return ret;
}

int succ(int k)
{
node *x, *y, *o;
split_key(root, x, y, k);
split_kth(y, o, y, 1);
int ret = key_of(o);
y = merge(o, y);
root = merge(x, y);
return ret;
}

int findkth(int k)
{
node *x, *y, *o;
split_kth(root, x, y, k – 1);
split_kth(y, o, y, 1);
int ret = key_of(o);
y = merge(o, y);
root = merge(x, y);
return ret;
}
}

[/code]

至于其他操作(比如翻转,标记)就下次再说吧。
有问题可以在下面评论或者联系我