Fhq-Treap 学习笔记
Fhq—Treap是一种好写，好用的平衡树。他主要通过 \(split\) 和 \(merge\) 这两个操作完成。基于二叉平衡树。
split
\(spilt\) 主要有两种方法实现。一种是按照权值排序，又或者是按照子树大小排序。如果是按权值来的话，就是把树通过一个 \(val_k\) 值进行分成两个子树 \(x,y\) 。\(x\) 的子树内部值全部都严格小于 \(val_k\) ，\(y\) 则反之。
inline void spilt(int now,int k,int &x,int &y){
if(!now) x=y=0;
else{
if(val[now]<=k){
x=now; spilt(child[now][1],k,child[now][1],y);
}else{
y=now; spilt(child[now][0],k,x,child[now][0]);
}
update(now);
}
return;
}
解释一下，当 \(val_{now}<=k\) 的时候，由于二叉平衡树的性质，他的左子都严格小于 \(val_{now}\) ，所以他的左子都不可能成为右子的根节点，只有可能是右子。所以这是为什么是向右边递归。 \(val_{now} \ge k\) 的时候反之。