algorithm - 用于创建家谱的树

Question

我正在寻找一种好的算法来计算两个人的最低共同祖先，而无需初始整体树。

如果我有孩子，我可以打电话找家长。所以如果我有两个孩子，我需要打电话给每个孩子，直到他们有一个共同的祖先。至此，我应该有两个列表，我可以将它们构建成一棵树。

什么样的算法对此有好处？

Answer 1

如果有一些基本信息可以确定特定节点是否可以“原则上”成为另一个特定节点的父节点，那么它将允许您快速/有效地确定共同祖先（如果有的话）。这就是我关于“年龄”的问题——见评论——是关于的。年龄属性显然会给你那种类型的信息。

假设从您的回答中没有此类信息可用，则有两种明显的方法：

A. 向上扫描两棵树（getParent 等），为每个初始孩子构建祖先列表，同时检查每个新祖先是否出现在另一个孩子的祖先列表中。一般而言，没有理由假设共同祖先与两个孩子的距离（“几乎”）相等，因此您构建各自祖先列表的任何顺序都同样会给您在尽可能少的步骤。

这种方法的一个缺点是，您冒着不得不在相互列表中搜索大量新候选者的风险。这可能很慢。

B. 另一种方法是简单地独立构建两个祖先列表中的每一个，直到用尽。这可能相对较快，因为您不会在每一步都因必须检查“另一个”列表的内容而被打断。

然后，当你完成这两个列表时，你要么有一个共同的祖先，要么没有，只需通过相互验证顶部项目。如果没有，你就完成了（没有结果）。如果是的话，你同步地走回列表并检查它们分开的位置，再次避免列表搜索。

从一般的角度来看，我更喜欢方法 B。有时方法 A 当然会更快地产生结果，但在糟糕的情况下，它可能会变得乏味/缓慢，而方法 B 不会发生这种情况。我当然假设任何祖先列表都不能是循环的，即一个节点不能是它自己的祖先。

As a final note: IF, after all, you do have a property that "orders" nodes in the sense of "age", then you should build the two lists simultaneously, in the sense that you always process the list that has currently a top node which cannot possibly be the parent of the other list's topnode. This allows you to check only the current topnodes against each other (and not any other members of the lists).