Treap（树堆）

概念

• 一种弱平衡的二叉搜索树(BST)
• 同时符合堆(Heap)和二叉搜索树的性质
• 是笛卡尔树的一种

每个结点都可以用一个数对 $(\mathit{value},\mathit{fix})$ 表示，其中 $\mathit{fix}$ 是随机生成的，用于维护树的平衡性（即保证树的深度基本一致）。

旋转

插入

删除