标签：笔记 二叉 学习 Treap 搜索 权值 节点
Treap(树堆) 学习笔记(此处为带旋Treap)
Treap简介
Treap是一种二叉搜索树，其中，权值val满足二叉搜索树的性质，节点优先级priority满足堆的性质(作用后面会讲到)
Treap适用情况
因为属于二叉搜索树，所以可以维护二叉搜索树的信息，带旋Treap可以更好地控制树的深度，使得每次操作不至于被特殊数据卡成一条链使得单次操作复杂度从logn退化到n
Treap维护的信息
1. 左右儿子的编号(带修，不适用堆式存储) lc rc
2. 权值 val
3. 子树大小 siz
4. 节点个数 cnt (可能有重复权值的节点)
5. 优先级 pos （维护堆的性质）
标签：笔记,
二叉,
学习,
Treap,
搜索,
权值,
节点
From： https://www.cnblogs.com/vicem/p/18454877