65.9K
CodeProject 正在变化。 阅读更多。
Home

双色冒险 - 在 C# 中实现类似 std::map 的结构

Ury Jamshy
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.44/5 (5投票s)

2012年6月21日

CPOL

6分钟阅读

viewsIcon

15877

downloadIcon

225

实现一个类似于 C++ std::map 的数据结构，该结构基于红黑树数据结构。

Sample Image - maximum width is 600 pixels

引言

作为一名最初的 C++ 程序员，我怀念 STL 容器的一些特性，这些特性并未在标准的 .NET 集合中实现。特别是，能够搜索一个不一定存在于集合中的项，并获得最接近的匹配。这就是 std::map 的 lower_bound 和 upper_bound。当尝试在时间轴上显示标签时，出现了对这种功能（lower_bound 和 upper_bound）的需求。当视图被放大时，需要获取缩放范围内内的标签子集。如果标签集是静态的，那么一次排序然后使用通用的 List<> 就可以达到目的，因为它提供了 BinarySearch 方法。然而，集合是动态的，所以需要另一种方法。这里提出了 SortedMap<TKey, TValue>：一个基于红黑树数据结构的通用集合。除了标准的集合接口外，它还提供了 lower_bound 和 upper_bound。

如果您需要最接近匹配功能，欢迎继续阅读并使用代码。即使您不关心 lower/upper bound，您也可能会发现关于测试的讨论很有用，因为它介绍了一些基本的测试原则，在我看来，这些原则对于创建健壮且（相对）无 bug 的软件很重要。

红黑树

红黑树在很多地方都有描述，所以我们在这里只做简要介绍。它是一棵二叉树，每个节点都涂有黑色或红色（也许灵感来自轮盘赌的颜色）。红黑树满足以下性质：

  1. 每个叶子节点都是黑色的。
  2. 如果一个节点是红色的，那么它的子节点必须是黑色的。
  3. 从叶子节点到根节点的每条路径都包含相同数量的黑色节点。

使用上述性质证明红黑树的高度为 O(log n) 并不困难。因此，查找一个元素的时间复杂度为 O(log n)。查找最接近的匹配项，而不是精确匹配，也足够简单：只需搜索该元素，如果未找到，则返回搜索停止的节点。将一个元素插入红黑树包含两个步骤：

  • 首先执行标准的二叉树插入。然后修复树以保持其性质。
  • 删除一个元素也类似：标准删除后执行步骤以保持红黑性质。

因此，插入和删除操作的时间复杂度也为 O(log n)。

使用代码

SortedMap 由 2 层组成：

  • RedBlackTree<T> (在 RedBlackTree.cs 中) - 红黑数据结构的实现。
  • SortedMap<TKey, TValue> (在 SortedMap.cs 中) - 作为标准集合的红黑树包装器，实现了 IDictionary<>、ICollection<> 和 IEnumerable<>。

项目中的其他类

  • GenericEnumerator<T> (在 GenericEnumerator.cs 中) - SortedMap 的辅助类。
  • PermutationGenerator (在 PermutationGenerator.cs 中) - 生成指定大小的所有排列：用于测试。
  • TreeVisualizer<T> (在 TreeVisualizer.cs 中) - 以图形方式显示树：用于测试。
  • RedBlackTreeTester (在 RedBlackTreeTester.cs 中) - 测试 RedBlackTree。
  • SortedMapTester (在 SortedMapTester.cs 中) - 测试 SortedMap。

如果您需要一个标准的集合，请使用 SortedMap 类，您将需要 SortedMap.cs、RedBlackTree.cs 和 GenericEnumerator.cs。如果您不关心标准接口，请直接使用 RedBlackTree 类 - 只需要 RedBlackTree.cs。

RedBlackTree<T> 提供了以下方法（请注意，它只有一个类型参数）：

  • Clear() - 清空树。
  • void Add(T item) - 向树中添加一个新项。
  • void Remove(T item) - 删除现有项。
  • TreeNode Find(T item) - 查找精确匹配项。
  • TreeNode FindGreaterEqual(T item) - 查找精确匹配项或下一个项。
  • TreeNode First() - 返回树中的第一个节点。
  • TreeNode Next(T item) - 返回下一个节点。
  • bool IsValid() - 检查树是否为有效的红黑树（用于测试）。
  • bool TravelTree(TreeVisitor visitor) - 遍历树并将访问者应用于每个节点（用于测试）。

SortedMap<TKey, TValue> 除了标准的集合方法外，还提供了最接近匹配功能：

  • TValue LowerBound(TKey key) - 返回第一个键不小于给定键的元素。
  • TValue UpperBound(TKey key) - 返回第一个键大于给定键的元素。
  • IEnumerable<KeyValuePair<TKey, TValue>> LowerBoundItems(TKey key) - 返回一个从 lower bound 项开始的枚举器。
  • IEnumerable<KeyValuePair<TKey, TValue>> UpperBoundItems(TKey key) - 返回一个从 upper bound 项开始的枚举器。

令人惊讶的是，创建标准集合需要大量的代码。SortedMap 接近 1000 行，尽管它不包含任何逻辑 - 只是实现了标准接口。以下代码片段演示了如何检索键大于特定键的所有项。

SortedMap map = new SortedMap<int, double>();
...
int key = someValue;
foreach (KeyValuePair<int, double> pair in map.UpperBoundItems(key))
{
    // Do something
}

复杂性

如上所述，插入、删除和查找键（精确匹配或最接近匹配）的操作成本为 O(log n)。移动到下一个元素是 O(log n)（最坏情况），O(1)（摊销）。这意味着单个 next 操作可能需要 O(log n) 的成本，但沿着整个树移动需要 O(n) 次操作，因此单个操作的平均成本为 O(1)。下表总结了各种操作的复杂度：

操作 (Operation) 复杂性
插入 O(log n)
卸载 O(log n)
搜索 O(log n)
下一个元素 O(log n)（摊销 O(1)）

测试树

创建此类数据结构时首先会想到一个问题：为什么选择红黑这两种颜色？第二个问题是如何确保结构满足其要求。一个答案是进行有效性检查。我在 RedBlackTree 类中添加了一个 IsValid 方法，该方法检查结构的有效性，并特别确保从每个叶子节点到根节点的黑色节点数量相同。在测试期间，每次操作后都会调用此方法，以便精确地定位树变得无效的时刻。但这还不够，因为树可能有效，但包含错误的数据。为此，我使用了“与更简单的数据结构进行比较”的技术。树上的每个操作也应用于 List<>。在每次修改后，将树的内容与列表的内容进行比较，以验证树的内容是否正确。使用了 2 个自动测试来测试树：

第一个是向树中添加数字 1 到 9 的所有排列。第二个是随机地向树中添加和删除值，同时检查其有效性。我经常使用这种随机测试，因为它在大多数情况下会在意想不到的情况下暴露 bug。然而，这还不够：IsValid 失败了，树太复杂，无法理解问题。这时 TreeVisualizer 派上了用场。这是一个简单的类，可以在文本窗口中显示树（您可以在文章顶部看到快照）。在树实现中使用它极大地帮助了我定位问题。所以，总结一下：

  • 验证 - 编写一个测试要求的方法，并在测试期间调用它。
  • 与更简单结构进行比较 - 如果可能，将新数据结构与更简单的结构（最好是标准结构）进行比较。
  • 自动随机测试 - 这将暴露您未预料到的情况。
  • 可视化 - 这有助于可视化数据结构。有时只是一个简单的转储，有时是一个图形图像。
© . All rights reserved.