STL 的 set 和 map 就是 Treap 的变种, 实质就是 Birnary Search Tree(BST) + Heap。
一个树是 BST 需要满足这些条件：
- 当前节点的左子树中任何一个点的权值都小于当前权值
- 当前节点的右子树中任何一个点的权值都大于当前权值
- 一般不会有两个节点值相同, 若插入了一个重复值, 则直接在对应节点将计数 cnt++
BST 的性质：中序遍历（左跟右）后得到的就是从小到大正序序列。
而 Treap 是在节点中既存储 BST 的值, 又存储用于堆处理的值。有以下几种操作：
- 插入 x
- 若为已存在值, 从根节点开始： 搜左子树 当前 搜右子树
- 删除, 因为子节点比较好删, 需要用“旋转”操作等价让某个非叶节点跑到叶子节点, 然后删除
- 找前驱和后驱
- 若左子树存在, 就找左子树的最大值
往右走到底
- 若无左子树, 就一直往上找父节点, 直到存在当前点是其父节点的右儿子, 那么该父节点就是前驱。
- 若左子树存在, 就找左子树的最大值
往右走到底
- 求最大最小值, 找最左下角和右下角点即可。
- 求某个值的排名
- 求排名是 k 的数是什么
- 比给定数 x 小的最大值
- 比给定数 x 大的最小值 其中前四个操作是用 STL 的 set 就能实现。
原理
核心思想, 让二叉树变得随机, 一个随机的 BST 期望高度只有 。
定义节点数据结构：
struct Node{
int l, r;
int key, value;
}tr;key 是权值, value 是大根堆。通过 key 和 value 可以唯一确定一个二叉树的随机形式。每个节点都需要满足两个条件：
在建立 Treap 时, 要先建立两个哨兵, 确保不会出现边界问题。
两种旋转操作：
- 左旋, 让 y 的右子树 x 作为根, x 的左子树代替 y 的右子树
- 右旋, 让 x 的左子树作为根, 用 y 的右子树代替 x 的左子树
可以发现的性质是, 旋转后不影响中序遍历的顺序, 最左侧点和最右侧点 zig/zag 后还在原地。而对于 z 点, 左旋和右旋后的中序遍历结果也是不变, 都是先输出 y, 然后 z, 最后 x。
因此这样可以实现父-子节点的交换, 若 y > x 进行一个右旋后就满足 y > 左子树, 右子树, 且不会改变中序遍历结果。
用旋转实现删除：
因为叶子结点可以直接删去, 而旋转操作对树无影响, 故先用旋转旋到叶子结点, 再进行删除。旋转时需要判断一下进行左旋还是右旋, 确保删去后满足堆的性质（u > l.val, u > r.val)
例如, 删除 u 点：
- 若 a > b, 则用右旋
- 若 a < b, 则用左旋