时间戳

首页 > 解决方案 > 计算两个指定键之间键数的良好数据结构

data-structures - 计算两个指定键之间键数的良好数据结构

问题描述

在我的脑海中经历了一个假设场景，并且无法完全想到在这种情况下使用的数据结构。假设我们需要的只是添加（）和删除（）键的能力，然后计算（key1，key2）两个指定（包括）之间的键数。我们当然假设这些键重载了比较运算符，因此它们可以明确地小于、大于或等于彼此。例如，如果我们插入 1、5、3、4、7，然后运行 ​​count(1, 4)，我们将得到 3 的结果输出，因为我们可以计算键 1、3 和 4。

现在我们可以在 O(n) 时间内使用递归使用二叉搜索树来做到这一点，但是如果我们需要 count() 在 O(log(n)) 时间内运行呢？是否有数据结构可供您修改以执行此操作？

起初我想也许我们可以使用堆或 BST 并跟踪每一侧的子节点数量。但后来我真的迷失了，试图在纸上追踪它。

标签： data-structures

解决方案

顺序统计树是对 BST的修改，它允许您针对任何值查询树中有多少元素小于该值。然后，您可以通过询问有多少项目小于 a，然后减去有多少项目小于 b，来计算 (a, b) 范围内有多少项目。

订单统计树上的每个操作（添加、删除、查找和计数）都需要 O(log n) 时间，因此这也可以让您在 O(log n) 时间内解决您的特定问题。

推荐阅读