确实 FHQ-Treap 不知道比隔壁 Splay 好多少,码量少,常数小。
前置知识
C++
BST
Head
原理&代码实现
FHQ Treap
不是通过旋转来保持平衡的,而是通过分裂和合并。 FHQ Treap
会按二叉搜索树一样根据键值排序结点,并且随机赋给每个结点一个优先级,按照二叉堆的顺序排序结点(这里用大根堆)。Treap
通过旋转,使平衡树同时满足这两个性质,从而达到平衡。而 FHQ Treap
通过调用合并函数时使平衡树满足堆序,实现原理与 Treap
不同。
新建一个节点也就是赋值与初始化各项信息,当然需要返回节点编号作为描述这个节点的信息
int new(int val){
tr[++ind].val=val;
tr[ind].rnd=rand();
tr[ind].siz=1;
return ind;
}