基于节点属性构建树的算法

Question

我是一名有用的助手，可以为您进行文本翻译。

我正在尝试解决一个编程问题，需要实现以下算法（大致如下）：

有几个节点，例如 A、B、C 等。

每个节点可以包含多个项，例如 a、b、c、x、y、z 等。例如：

A [a, b, c, x, y, z]

B [a, b, c]

C [x, y, z]

节点和项可以有无限数量，节点中的项可以任意多（但相同的项不会重复出现）。

我的任务是根据节点中的共同项在节点之间创建层次结构。因此，在上面的示例中，A应该比B和C具有更高的层次结构。或者换句话说，A是主节点，B和C是从属节点。

所以，我想如果我可以根据共同项从节点中创建树形结构，那么这将更容易。但我不知道要使用哪种算法。有人知道适合我情况的算法吗？建立树不是必须的，如果有其他方法可以实现相同的事情，那就好了。谢谢。

- moshfiqur

---

听起来像是拓扑排序。您能否根据它们的内容准确地定义两个节点的顺序？相对于A，[a, b, c, d, e, f]会如何排序？ - Ian Mercer

那么，如果您有（比如）255个节点，您总会从根节点到叶子节点有8个级别吗？ - Darius X.

@IanMercer 但是拓扑搜索看起来对我的问题很有帮助和前途。我会去检查一下。谢谢。 - moshfiqur

@DariusX。不，等级是动态的，可以有任意长度的等级。 - moshfiqur

当你在层次结构中说“更高”，这意味着节点之间存在某种排序（即一种排序顺序）。那么，哪个更高[a，b，c，x，y，z]还是[a，b，c，d，e，f]？或者它们是“相等”的？您能否更精确地定义您所说的“更高”是什么意思？如果X严格包含在Y中，那么X < Y吗？还是如果X与Y相交并且X具有较少的元素，则X < Y？或者...？ - Ian Mercer

Answer 1

尝试使用AVL树。

请注意，AVL树的最坏情况可能类似于this。您可以在这里阅读有关最坏情况的更多信息。

最重要的是，给定两个“节点”，是否存在比较它们并确定哪个更高的逻辑？如果没有，则需要首先构建它！

一旦您知道如何进行比较，那么AVL树就可以用于构建和维护“层次结构”。

- Ravindra HV

---

谢谢你的回答。但我已经找到了解决方案。请查看我的答案。 - moshfiqur

Answer 2

我已经根据Ming-Syan Chen、Jong Soo Park和Philip S. Yu在论文《数据挖掘用于Web环境中的路径遍历模式》中提出的算法进行了适应。该论文可以在这里找到。虽然这个算法并没有直接解决我的问题，但我对算法进行了一些调整，使其适应了我的问题情况。现在它运行良好，并且我得到了所需的结果。

我想感谢所有花时间阅读我的问题并提出解决方案的人。

- moshfiqur