data-structures - Tarjan 的离线最小公祖先算法

Question

我目前正在阅读来自 Tarjan 的关于如何获取二叉树中两个节点的最小公共祖先的算法。

我已经阅读了来自Wikipedia的伪代码，但我没有得到它的要点。我的意思是我无法在任何给定的二叉树上应用该算法。我还试图在谷歌上找到每个步骤的一些解释，但我没有得到任何有价值的东西。所以，如果有人能帮助我理解这个算法是如何在二叉树上工作的，那将是非常可观的。

Answer 1

除了给定的二叉树，你应该实现另一个名为 disjoint set 的数据结构来应用这个算法。这种数据结构主要有三种方法，MAKE-SET、UNION、FIND-SET。我强烈建议你阅读《算法导论》的第 21 章“不相交集的数据结构”以更好地理解。