定义

当我们提到 “Treap” 的时候,我们实际上说的是 “Tree” + “Heap”。Treap 的每个节点拥有两个值:”Key” 和 “Val”。其中 “Key” 满足堆的性质,而 “Val” 满足二叉搜索树的性质。

朴素的 Treap 在插入的时候给每个点一个随机的 Key,通过旋转来满足堆的性质。对于 FHQTreap,我们不再使用旋转维护,转而使用拆分和合并。

核心操作

拆分

我们将一个 Treap 按特定的值 Val 拆分成两个 Treap – 左树和右树,使得左树的所有值小于等于 Val,而右树的所有值大于 Val。

合并

我们可以按照堆的性质,将两个 Treap a, b ,其中 a 包含的所有值小于 b 中所有元素,合并到一个 Treap 上。

实际运用

当我们想要修改 / 获取某个点的权值时,我们希望操作的影响范围尽可能地小。比如,当我们期望删除一个点的时候,如果它恰好在根节点,我们可以通过合并它的左右子树来达成这一目的。上文提到的拆分和合并恰好可以完成这个操作。

同样的思路适用于以下所有问题:

  • 插入一个数值;
  • 删除一个数值;
  • 查询给定数值的排名;
  • 查询给定排名的数值;
  • 查询给定数值的前驱 / 后继。

代码

  1. kal0rona
    Jan 03, 2019

    %%%神仙

    Reply