2012-08-10 75 views
2

在Python中實現最低共同祖先最簡單的方法是什麼?我有一棵樹,每個節點都有一個指向父節點的指針,我希望能夠找到給定兩個節點的第一個共同祖先。我想出了一些想法,但沒有特別吸引python最低共同祖先

  1. 讓每個節點包含其基地的名單,並進行聯接,發現最長的公共前綴,然後把最後一個元素。不幸的是,我不知道任何內置的方法來做最長的通用前綴,所以這需要手動循環。

  2. 讓每個節點都包含一組基,並執行一組交集,並取最大元素。但是這需要定義自定義比較運算符,我甚至不確定它是否可行。

我該怎麼辦?我正在尋找一些有利於簡化性能的解決方案,因此需要複雜處理的解決方案已經無法使用。

編輯:我發現,雖然沒有內置的方式,你可以使用zip在一行中做最長的通用前綴,所以它仍然相當簡單。

common = [x for x in zip(*baselists) if len(set(x)) == 1][-1] 

回答

5

下,你不能修改你的樹,包括深度的假設,你可以做到以下幾點:

對於每個節點,遞歸向上遍歷樹,直到你打根。在每個父節點處,將節點插入list。這應該給你list_alist_b。迭代最短列表,比較每個列表中的元素。當你找到一個不匹配的地方時,先前的條目就是你最大的父元素。

+0

如果您可以在不修改樹本身的情況下計算深度不得不。只需使用遞歸函數或迭代節點的祖先即可。 – 2012-08-10 17:34:51

5

取每個節點的深度(距離根的距離)。如果其中一個低於另一個,則從較低節點向上到樹的深度相等。然後檢查身份,每次檢查失敗時在每一邊移動每個身份。

你可以用一個while循環做到這一點。一旦你選擇了以同樣深度的祖先:

while (ancestorA !== ancestorB) { 
    ancestorA = ancestorA.parent(); 
    ancestorB = ancestorB.parent(); 
} 

當while循環結束,ancestorAancestorB將分別成爲你的共同祖先。

這應該不僅很簡單,而且相當快。

+0

有什麼辦法修改此所以它不需要兩個循環? – Antimony 2012-08-10 17:40:23

+0

如果你不能得到深度?上面的算法根本沒有幫助。然而,即使深度沒有存儲在樹中,在每一步中保存父母列表並與其他祖先進行比較也會得出結果。雖然,這需要反覆循環遍歷可能會減慢速度的祖先列表。 – aneroid 2012-08-11 07:44:19

+1

您可以編寫一個簡單的函數,通過遞歸或遍歷祖先節點來獲取深度。在節點/樹上定義方法只是OO設計的一個很好的方便/功能。 – 2012-08-12 13:51:51

0

我想它取決於你的樹,它將包含多少個對象。如果這個數字在記憶方面是合理的(可能少於幾百萬個節點,但這只是我的猜測),我會用你的建議#2。在該集合中,只需保留每個基的字符串表示形式,因此內置的比較就可以工作。應該非常快,我想你可以用幾行代碼來實現它。如果字符串表示形式不實際,或者如果您需要對象本身並且無法實現所有對象的主字典,只需在您的節點對象中定義比較方法(如果我記得,則爲eqneq)。

0

想法它保持父母收集,最好使用散列映射=,因爲在這種情況下,你不會花費在家長列表搜索。因此,在每次迭代時檢查這張地圖,如果當前節點的父親已經存在於地圖中,那麼這個父母就是你的結果。在最壞的情況下,它會給出O(n),但是如果您在某些情況下將開始分析兩個節點,您將能夠更快地找到它。

0

既然你已經有一個指針,在兩種情況下的父節點爲什麼不這樣做: (類似於weirdcanada說,但...)

創建每個節點的父母的列表,在列表建設順序每個階段。所以list_alist_b隨着你走高而增長。比較每個列表中添加的最後一個項目與另一個項目的項目。只要list_a中的項目與list_b中的項目匹配,您就擁有最低的共同祖先。

while (parent_a not in list_b) or (parent_b not in list_a): 
    ... 

您不需要一直重建鏈,直到root。無論如何,你將不得不依次檢查每個父母(向前或向後)。

+0

這是一個O(n^2)算法。我知道原始的海報說他想要簡單性以上的表現,但如果樹足夠高,這個算法將表現得非常糟糕。 – 2012-08-12 13:54:50

+0

好吧,夠公平的。然後......(繼續你的回答)...... – aneroid 2012-08-12 16:32:05

2

Python有內置集合。爲什麼不使用沿(僞代碼)線的東西:

a_ancestors = set() 
while a: 
    a_ancestors.add(a) 
    a = a.parent 

while b: 
    if b in a_ancestors: 
    return b 
    b = b.parent 

return None # <- can't reach that for a *tree* !!! 

這將生成節點一個的所有祖先的(無序)集(包括一個本身)。

然後,在第二次,我們循環所有的祖先b。根據定義,b的第一個祖先是a的祖先將是第一個共同的祖先。這部作品在爲O(n)(在空間和時間)


你有可能加快這一進程(最終在空間佔用爲代價)通過同時收集兩個組的祖先一個b - 一找到一個公共節點就停下來。該代碼是有點做作,你必須處理的一個分支,已達到之前其他根:

visited = set() 
while a or b: 
    if a: 
    if a in visited: 
     return a 
    visited.add(a) 
    a = a.parent 

    if b: 
    if b in visited: 
     return b 
    visited.add(b) 
    b = b.parent 

return None # <- can't reach that for a *tree* !!! 
相關問題