7

我正在寻找一个好的数据结构来在树的节点上构建等价类。在理想的结构中，以下操作应该是快速的（O(1)/O(n)，视情况而定）并且容易（没有神秘代码段落）：

  • (A) 从根部走树；在每个节点上 --> 子转换枚举子节点的所有等效版本
  • (B) 合并两个等价类
  • (C) 从现有节点（子节点）和其他数据的列表中创建新节点
  • (D) 找到任何结构上与node 等价的节点（即它们有相同数量的子节点，对应的子节点属于同一个等价类，并且它们的“其他数据”相等），以便可以放入新的（或新修改的）节点在正确的等价类中（通过合并）

到目前为止，我已经考虑过（其中一些可以组合使用）：

  • 冻糕，其中子代是对节点集合的引用，而不是对节点的引用。(A) 速度快，(B) 需要遍历树并更新节点以指向合并的集合，(C) 需要找到包含新节点的每个子节点的集合，(D) 需要遍历树
  • 通过节点的特征维护节点的哈希。这使得 (D) 更快但 (B) 更慢（因为当等价类被合并时哈希必须被更新）
  • 将节点串在一起形成一个循环链表。(A) 很快，(B) 会很快，但是事实上，将循环列表的一部分与自身“合并”实际上会拆分列表 (C) 会很快，(D) 需要遍历树
  • 与上面类似，但在每个节点中都有一个额外的“向上”指针，可用于查找循环列表的规范成员。

我错过了一个甜蜜的选择吗？

4

3 回答 3

5

你似乎有两种形式的等价处理。普通等价（A），被跟踪为保持最新的等价类和结构等价（D），您偶尔会为此构建一个单一的等价类，然后将其丢弃。

在我看来，如果您为普通和结构等价维护等价类，那么问题在概念上会更简单。如果这为结构等价引入了过多的流失，您可以为结构等价的某些方面维护等价类。然后你可以找到一个平衡点，你可以负担得起这些等价类的维护，但在构建结构上等价的节点列表时仍然大大减少要检查的节点数量。

于 2009-04-09T00:44:26.097 回答
4

我认为任何一种结构都无法解决您的问题，但您可以看看Disjoint-set data structure。毕竟，等价类与集合的划分是一回事。它应该能够快速处理其中一些操作。

于 2009-03-23T20:40:51.920 回答
2

退后一步，我建议完全不要使用树。上次我不得不面对类似的问题时，我从一棵树开始，但后来又转向了一个数组。

原因很多，但第一个原因是性能，我的类有多达 100 个左右的孩子，实际上在将它们作为数组操作时比通过树的节点执行更好，主要是因为硬件局部性、CPU 预取逻辑和 CPU流水线。

因此，尽管从算法上讲，数组结构需要比树更多的操作 N，但执行这几十个操作可能比在内存中追逐指针更快。

于 2009-04-14T01:13:33.633 回答