半层次是否有类似于树数据结构的数据结构？

Question

如果我们将树视为部分有序的集合，它将成为联接 - 隔离的特殊情况。对于联接 - 隔离，我们希望能够有效地计算两个元素（或多或少）的（唯一）上限。在树的情况下，可以将其存储在相应的节点中的每个元素的数据结构，并将其存储在相应的节点中的指针中，而距离的距离度量。 （实际上，基于拓扑排序的标记通常用于“距离距离的距离度量”，实际上所需的只是兼容的部分订单，可以有效地评估）。

每个有限的联接 - 隔离度可以表示为有限集的一组有限集的子集，以使得最小的上限由集合的联合给出。因此，通过有限数量的标签代表每个元素，并且计算相应标签的结合的最小上限将是一种可能的数据结构。 （通过查看补充，人们可以看到将最小的上限定义为相应标签的交汇处。）更常见的数据结构是简单地使用矩阵来存储所有结果“ A <= = b“甚至所有“加入（a，b）”的结果。

但是，使用这样的数据结构代表树会很奇怪。是否有更多类似树状的数据结构用于联接 - 偏层，这些数据结构仍然允许（或多或少）对两个元素的（唯一）最小上限的有效计算？ （也许是某种有向的无环图，并在节点中具有其他信息，类似于树根的距离度量？）

Answer 1

这个 Blogpost 关于晶格理论，有一个有用的参考部分，其中包含Vijay K. Garg的“晶格理论”。第2章“表示POSET”描述了一些用于表示POSET的数据结构，并讨论了如何使用这种数据结构来计算Join（X，Y）。

讨论的前两个数据结构是传递还原图的邻接列表表示（= hasse图/封面关系）和传递闭合图（= poset关系）。关于使用拓扑排序标记节点先于讨论之前标记的优势的评论。请注意，拓扑排序的标签将足以作为“距离根的距离度量”，这是问题中树的数据结构的一部分。

另一个讨论的表示是“骨骼表示”，“基质表示”和“基于维度的表示”。 “骨骼表示”很有趣且有用，但基于Poset的（任何）链分解。 “矩阵表示”似乎很容易，但它可能是大多数实际问题的最佳代表。 “基于维度的表示”表示Poset是线性订单的笛卡尔产物的子集，但是计算此类的最小表示是NP-HARD。

总之，它们最神经的表示是传递还原的邻接列表表示以及通过拓扑排列的节点标记（而不是“距离距离的距离度量”）。这实际上是Sage使用的表示之一（另一个是“矩阵表示”）。