FHQ-Treap
我勒个范浩强啊
FHQ-Treap定义
- 是无旋Treap
- 用split 和 merge 维护
Treap的简介
- 随机化数据结构
- 二叉搜索树 + 二叉堆（小根大根皆可）
- 用键值维护 给每个键值一个随机附加的优先级，让键值满足二叉查找树的结构，让优先级满足二叉堆的结构。
Treap的原理
- 以随机顺序插入数据构造的二叉搜索树
- 节点插入的顺序是随机的，所以构造的二叉搜索树在概率上趋近平衡。
- 但不能提前知道构造树的数据，所以用于动态算法。
Treap维护
用左旋和右旋维护 小口诀 枢纽拎起来，父兄挂下面，右孩给父亲。
插入
- 插入的过程中通过旋转来维护优先级的堆性质
FHQ-Treap的实现
split
- 将一个FHQ-Treap 按某个值分裂成2个