的Tarjan的脫機最小公共祖先算法

Question

我正在閱讀有關從的Tarjan如何讓兩個節點的最低共同祖先二叉樹的算法。

我從Wikipedia閱讀僞代碼，但我沒有得到它的要點。我的意思是我無法將該算法應用於任何給定的二叉樹。我也嘗試在Google上找到對每個步驟的解釋，但是我沒有得到任何有價值的東西。因此，如果有人能夠幫助我理解這種算法如何在二叉樹上工作，那麼這將非常可觀。

Answer 1

除了給定的二叉樹，應實現設置爲應用此算法不相交的另一個名爲數據結構。這個數據結構有三種主要的方法，MAKE-SET，UNION和FIND-SET。我強烈建議您閱讀第21章「數據結構不相交的集合」的「算法導論」爲了更好的理解。