在树的节点上构建等价类的好数据结构是什么？

Question

我正在寻找一个良好的数据结构来在树的节点上构建等价类.在理想的结构中,以下操作应该是快速的(适当的O(1)/ O(n))和容易(没有神秘代码的段落):

(A)从树上走树; 在每个节点上 - >子转换枚举子节点的所有等效版本
(B)合并两个等价类
(C)从现有节点(子节点)和其他数据的列表中创建新节点
(D)找到结构上等同于节点的任何节点(即它们具有相同数量的子节点,相应的子节点属于相同的等价类,并且它们的"其他数据"相等)以便可以放置新的(或新修改的)节点在正确的等价类中(通过合并)

到目前为止,我已经考虑过(其中一些可以组合使用):

parfait,其中子节点引用节点集合而不是节点.(A)速度快,(B)需要遍历树并更新节点以指向合并集合,(C)需要查找包含新节点的每个子节点的集合,(D)需要遍历树
按特征维护节点的哈希值.这使得(D)更快但(B)更慢(因为当合并等价类时必须更新散列)
将节点串在一起成为循环链表.(A)速度快,(B)速度快但是因为圆形列表的"合并"部分实际上拆分列表(C)会很快,(D)需要走树
如上所述,但在每个节点中有一个额外的"向上"指针,可用于查找循环列表的规范成员.

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

Answer 1

您似乎要处理两种形式的对等。简单的等价 (A)，跟踪为保持最新的等价类和结构等价 (D)，您偶尔会为此构建一个等价类，然后将其丢弃。

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