快速设置操作的数据结构

问题描述 投票：0回答：1

我正在研究 Hanson 和 Chaabouni 的 Interval Binary Search Tree 的 C# 实现。简而言之，它是一种dynamic区间集合的数据结构，可让您快速找到与点重叠的区间。数据结构是使用 AVL 平衡方案的增强二叉搜索树 (BST)。

树中的每个节点包含三组区间。在进行旋转时，我们需要进行大量的集合操作以保持不变性。我们需要支持集合中的迭代间隔、集合的加法和减法以及集合交集。如果集合包含重复的间隔（具有相同端点但不是同一对象的间隔），它们将包含在相同的集合中。

我们需要能够尽快完成这些集合操作 - 这是我们的限制因素 atm。是否有任何数据结构可以有效地支持这些操作？

奖金信息：

  • 区间由低端点和高端点组成。这就是我们对他们的全部了解。
  • 我们可以对这些端点进行哈希处理，但是具有相同端点的重复间隔自然会具有相同的哈希码。
  • 间隔在参考相等性上有所区别。
  • 我们可以对端点进行排序，但是具有相同端点的重复区间自然会具有相同的排序顺序。
  • 我们没有任何其他可用于散列或排序的信息。
c# algorithm data-structures intervals set-operations
1个回答
0
投票

我使用类似的方法来实现 IntervalSet 集合，存储generic间隔。这是我的 GitHub 存储库。以下是部分文档，描述了有关 IntervalSet 的详细信息：

对间隔集的操作是通过 IntervalSet 集合完成的。它是增广区间树抽象数据结构的实现，使用自平衡二叉搜索树（BST）-AA树。 IntervalSet 提供基本操作 - Add、Remove、Union、UnionWith、Intersect、Except、Merge。它的初始化和联合算法受到 System.Collections.Generic 中的 Sorted Set 的影响。

IntervalSet 实现了 ISet，因此也支持 IEnumerable 和 iteration。间隔按开始顺序存储，然后按结束顺序存储。迭代也按该顺序完成。区间集的加法和减法可以使用Union、UnionWith和ExceptWith来完成。

区别在于，为了简单起见，我使用 AA Tree 而不是 AVL 树，每个间隔存储一个值及其开始和结束限制，并且没有重复 - IntervalSet 仅存储唯一的间隔（按限制） 。检查文档以获取更多信息。

增强间隔树的主要焦点是通过其增强属性支持更广泛的基于间隔的查询和计算（在我的例子中是最大结束限制，如Wiki中所示）。然而，它必须完全能够有效地找到与特定点重叠的区间。这可以通过使用 IntervalSet 的 Intersect 方法重载来完成，仅接受单个限制。这是一个例子：

var intervalSet = new IntervalSet<int, int?>
{
    (3, 7), // [3, 7]
    (5, 10), // [5, 10]
    (8, 12), // [8, 12]
    (1, 5), // [1, 5]
    (15, 20) // [15, 20]
};

var intersectedIntervals = intervalSet.Intersect(6); // returns an interval set with [[3, 7], [5, 10]]

我还发布了一个名为 NeatIntervals 的 NuGet 包。您可以从那里获取 IntervalSet 集合。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.