algorithm - 用于有效百分位查找的数据结构？

Question

假设您有大量的键/值对，其中的值是某个任意实数。您有兴趣创建支持以下操作的数据结构:

插入 ，它向集合中添加了一个新的键/值对，

删除 ，从集合中删除一个键/值对，

百分位 ，它告诉与给定键关联的值位于哪个百分位，以及

Tell-Percentile ，它接受一个百分位数并返回其值至少是给定百分位数的最小值的键。

例如，该数据结构可用于有效地确定给定学生在收到全国性测试分数流时所处的百分位数，或识别服务质量异常好或差的医院。

有没有办法让这些操作有效地运行(比如，次线性时间？)

Answer 1

实现此数据结构的一种可能方法是使用 order statistic tree 的混合。和一个 hash table .

顺序统计树是一种平衡二叉搜索树，除了正常的二叉搜索树操作外，还支持另外两种操作:

排名 (key)，返回树中小于给定元素的元素数，以及

选择 (k)，它返回树中第 k 个最小的元素。

可以通过使用在旋转期间保留的额外信息来扩充普通的平衡二叉搜索树(例如 red/black tree 或 AVL tree )来构建顺序统计树。这样，订单统计树上的所有正常 BST 操作都可以在 O(log n) 时间内运行，额外的操作也在 O(log n) 时间内运行。

现在，让我们假设您纯粹存储值分数，而不是键/百分位分数。在这种情况下，实现百分位查找将非常简单，如下所示。将所有值存储在订单统计树中。要确定给定值的百分位数，请使用 排名对订单统计树进行操作以查找该值出现在哪个索引处。这给出了一个范围从 0 到 n - 1(其中 n 是树中元素的数量)的数字，表示该分数在订单统计树中的位置。然后，您可以将该数字乘以 99/(n - 1)，以根据需要获得在 0 到 99 范围内运行的值的百分位数。

要确定大于某个百分位数的最小值，您可以使用 选择 操作如下。给定一个介于 0 和 99 之间的百分位数，将该百分位数乘以 99/(n - 1) 以获得介于 0 和 n - 1 之间的实数，包括两者。取该数字的上限会生成 0 到 n - 1(含)范围内的自然数。使用 选择 然后可以使用订单统计树上的操作来查找范围中处于或高于给定百分位数的第一个值。

然而，这些操作假设我们在数据结构中有纯粹的值，而不是键/值对。为了使这个操作适用于键/值对，我们将增加我们的数据结构如下:

我们将在每个节点中存储键/值对，而不是仅仅存储值。订单统计树将纯粹按键/值对的值对键/值对进行排序，键作为卫星数据携带。

我们将存储一个二级哈希表，将键映射到它们的关联值。

这两个更改使我们可以为我们的数据结构实现所需的功能。为了让数据结构按键进行百分位查找，我们首先使用给定的键查询哈希表以查找其关联值。然后我们像以前一样对值进行百分位查找。为了让数据结构告诉我们一个键的值是第一个或高于给定百分位数，我们如上所述对订单统计树执行正常的查找百分位数操作，然后查找与给定值关联的键。

如果我们假设哈希表使用链式哈希，那么每个操作所需的时间如下:

插入 : O(log n) 时间将值/键对插入订单统计树，加上 O(1) 分摊时间将键/值对插入哈希表。总时间为 O(log n) 摊销。

删除 : O(log n) 从订单统计树中删除值/键对的时间，加上 (1) 从哈希表中删除键/值对的分摊时间。总时间为 O(log n) 摊销。

百分位 : O(1) 期望时间来查找与键关联的值，O(log n) 时间做 排名操作，以及 O(1) 额外时间将等级映射到百分位数。预计总时间为 O(log n)。

查找百分位 :将百分位数映射到等级所需的时间为 O(1)，执行 所需的时间为 O(log n)选择 手术。总时间是 O(log n) 最坏情况。

希望这可以帮助!