檢查2樹節點在O相關（祖先/後代）（1）用前處理

檢查2樹節點是相關的（即祖先子孫）檢查2樹節點在O相關（祖先/後代）（1）用前處理

解決它在O（1）時間，與O（N）的空間（N =節點＃）
預處理允許

就是這樣。我將在下面討論我的解決方案（方法）。如果你想先想好自己，請停止。

對於前處理，我決定做一個預購（遞歸通過根先走，然後兒童），給一個標籤到每個節點。

讓我詳細解釋標籤。每個標籤由逗號分隔的自然數組成，如「1,2,1,4,5」 - 該序列的長度等於（節點的深度+1）。例如。根的標籤是「1」，根的孩子將有標籤「1,1」，「1,2」，「1,3」等。下一級節點將有標籤，如「1,1,1」，「1,1,2」，...，「1,2,1」，「1,2,2」，...

假設節點的「訂單號」是「該節點的基於1的索引」在其父項的子項目列表中。

常用規則：節點的標籤由其父標籤後跟逗號和「訂單號」組成。因此，爲了回答O（1）中兩個節點是否相關（即祖先 - 後代），我將檢查其中一個標籤的標籤是否爲其他標籤的「」前綴「。雖然我不確定這些標籤是否可以被認爲佔用O（N）空間。

任何批評者都有修正或替代方法。

來源

2012-04-25 Alec

這是在最壞的情況下每個節點都有一個孩子（麪條）的O（N^2）空間。 – WeaselFox 2012-04-25 07:09:25

如果您存儲每個頂點的預訂號和後序號並使用此事實，則可以在O（n）預處理時間和O（n）空間中執行O（1）查詢時間：

對於樹T的兩個給定節點x和y，x是y的祖先，只有當x在前序遍歷T中出現在y之前，並且在後序遍歷中出現在y 之後時。

（在此頁：http://www.cs.arizona.edu/xiss/numbering.htm）

你在最壞的情況下所做的是西塔（d）其中d是上級節點的深度，所以是不是O（1）。空間也不是O（n）。

來源

2012-04-25 07:21:58

那麼麪條情景呢？有序的前序和後序完全一樣，所以沒有節點是另一個的祖先？ – WeaselFox 2012-04-25 07:41:34

@ WeaselFox：你的意思是像一個鏈表？這些遍歷不會互相顛倒嗎？ – 2012-04-25 07:52:13

你是絕對正確..我的壞 – WeaselFox 2012-04-25 07:57:46

有線性時間最低的共同祖先算法（至少離線）。例如看看here。你也可以看看tarjan's offline LCA algorithm。請注意，這些文章要求您事先知道您將執行LCA的配對。我認爲也有在線線性時間預計算時間算法，但它們非常複雜。例如，對於範圍最小查詢問題，存在線性預計算時間算法。據我記得這個解決方案兩次通過LCA問題。該算法的問題在於它具有如此大的常數，以至於實際上比O（n * log（n））算法更快地需要大量輸入。

有更簡單的方法需要O（n * log（n））額外的內存，並在同一時間再次回答。

希望這會有所幫助。

來源

2012-04-25 07:23:38

生命週期分析對此是過度的。 – 2012-04-25 07:23:56

如果您考慮一棵樹，樹中有一個節點有n/2個孩子（比如說），設置標籤的運行時間將會高達O（n * n）。所以這個標籤方案不會工作....

來源

2013-09-26 14:33:11 pypep278

檢查2樹節點在O相關（祖先/後代）（1）用前處理

回答

相關問題