創建家族樹的樹

Question

我正在尋找一個很好的算法來計算兩個人的最低共同祖先，而不是最初的整體樹。

如果我有孩子，我可以撥打電話獲取父。所以如果我有兩個孩子，我需要每個人都打電話，直到他們有一個共同的祖先。在這一點上，我應該有兩個列表，我可以將它們構建成一棵樹。

什麼樣的算法，將有利於本？

Answer 1

如果有確定是否一個特定的節點可以「原則上」是另一個特定節點的父親的一些基本信息，它會允許你確定共同祖先（如果有的話）快速/有效。這就是我關於「年齡」的問題 - 請參閱評論 - 是關於。 年齡屬性顯然會給你這種類型的信息。

假設，從你的答案，那有沒有可用的這樣的信息，有兩個明顯的方法：

A.同時掃描樹向上（的getParent，等等），構造每個初始孩子的祖先列表，同時檢查與每一個新的祖先是否發生在另一個孩子的祖先列表中。一般來說，沒有理由認爲共同的祖先與兩個孩子距離（「幾乎」）相等，所以你建立相應祖先列表的任何順序都等於給你共同的祖先在儘可能少的步驟。

這種方法的缺點是，你有運行在相互列舉了大量的時間來尋找新的候選人發生的風險。這可能很慢。

B.一種替代方法是簡單地建立所述兩個ancestorlists獨立直至力竭。這可能是相對較快的，因爲在每一步都不會因爲檢查「其他」列表的內容而中斷。

然後，當你已經完成了兩個列表，你要麼有一個共同的祖先與否，只要通過驗證彼此的頂級項目。 如果否，您就完成了（沒有結果）。如果是的話，你可以同步回到列表中，並檢查他們分開的位置，再次避免列表搜索。從一般的觀點來看，我更喜歡方法B.有時方法A會產生更快的結果，但是在不好的情況下，它可能會變得單調乏味，這對方法B來說不會發生。我假設，當然，任何祖先列表都不能是循環的，即一個節點不能成爲它自己的祖先。作爲一個最後的注意事項：畢竟，如果你確實有一個「命令」節點的屬性，那麼你應該同時構建這兩個列表，因爲你總是處理這個列表目前有一個頂層節點，它不可能是其他列表的頂級節點的父節點。這允許您僅檢查當前的頂級節點（而不是列表中的任何其他成員）。