ToB企服应用市场:ToB评测及商务社交产业平台

标题: FHQ-Treap [打印本页]
作者: 盛世宏图    时间: 2023-6-4 12:04
标题: FHQ-Treap
模板传送
FHQ-Treap顾名思义就是范浩强大佬设计的一种二叉平衡树
下面我们来讲一下它的原理和代码
结构体

对于一个节点，我们需要记录的是
  1. struct str{
  2.         int val,size,l,r,key;
  3. }fhq[100005];
复制代码
看到这里有人疑惑了，这个对应的随机值是怎么回事啊？
这里就涉及到了一个FHQ-Treap里优化的一个小技巧
我们知道，树在最坏的情况下，会退化成一条链
但很显然，出于时间复杂度上来讲，我们并不希望它成为一条链，因为我们的遍历是按照一层一层来遍历的，如果退化成一条链就会从最优O（log n）的复杂度直接降到O( n )，所以我们就用这个随机的值去让这个二叉树变得平衡，具体怎么去使用这个随机值的请看函数merge
函数

首先，先给大家把主要使用的函数列出来，然后我们再一个一个讲
  1. void update(int x)
  2. void split(int now,int dat,int &x,int &y)
  3. int merge(int x,int y)
  4. int add(int dat)
  5. void ins(int dat)
  6. void del(int dat)
  7. int get_rk(int dat)
  8. int get_num(int dat)
  9. void get_pre(int dat)
  10. void get_next(int dat)
复制代码
看起来是不是很让人头晕眼花？
我们把函数要具体实现什么注释一下：
  1. void update(int x)//更新数据
  2. void split(int now,int dat,int &x,int &y)//分裂
  3. int merge(int x,int y)//合并
  4. int add(int dat)//在树里添加节点（实际的操作）
  5. void ins(int dat)//节点进树（与上一个要区分开，这个只是一个输入的对接）
  6. void del(int dat)//节点出树
  7. int get_rk(int dat)//求dat数的排名
  8. int get_num(int dat)//求排dat名的数
  9. void get_pre(int dat)//求前驱
  10. void get_next(int dat)//求后继
复制代码
铺垫的差不多了，是时候开始讲了
update

update函数十分简单，主要要求实现的是更新该节点的子树长度，因为我们会在树上进行其他的修改操作，长度很可能会随之变化，所以这个函数一定是要放在第一位写的
  1. void update(int x){//要更新x节点
  2.         fhq[x].size=fhq[fhq[x].l].size+fhq[fhq[x].r].size+1;
  3.         //子树节点数=左子树节点数+右子树节点数+本身；
  4.         return ;
  5. }
复制代码
split

这个函数是FHQ-Treap的重点之一，主要实现的是把一棵树拆成两棵树方便后续操作，我们先解释一下这里的参数都是什么意思
  1. void split(int now,int dat,int &x,int &y)
  2. //now表示现在遍历到了哪个节点，dat是要从哪里拆开这棵树，x和y是拆后两颗树的根节点
复制代码
因为x和y的值在函数里会被不停地更新，所以我们这里的&x，&y就尤为重要
第一步，根据二叉搜索树，找到从哪里分成两半
[code]if(dat



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4