最近公共祖先 (图论)

在图论和计算机科学中，树或有向无环图 (DAG) T 中两个节点 v 和 w 的最低公共祖先 (LCA)（也称为最小公共祖先）是同时具有 v 的最低（即最深）节点 和 w 作为后代，我们将每个节点定义为其自身的后代（因此如果 v 与 w 有直接联系，则 w 是最低的共同祖先）。

T 中 v 和 w 的 LCA 是距离根最远的 v 和 w 的共享祖先。 计算最低共同祖先可能是有用的，例如，作为确定树中节点对之间距离的过程的一部分：从 v 到 w 的距离可以计算为从根到 v 的距离加上距离 从根到 w，减去从根到它们最低共同祖先的距离的两倍 (Djidjev, Pantziou & Zaroliagis 1991)。 在本体中，最低共同祖先也称为最不共同祖先。

在每个节点都指向其父节点的树数据结构中，可以通过找到从 v 和 w 到根的路径的xxx个交点来轻松确定最低公共祖先。 通常，此算法所需的计算时间为 O(h)，其中 h 是树的高度（从叶子到根的最长路径的长度）。 然而，存在几种处理树的算法，以便可以更快地找到最低共同祖先。 例如，Tarjan 的离线最低共同祖先算法以线性时间对树进行预处理，以提供恒定时间的 LCA 查询。 在一般 DAG 中，存在类似的算法，但具有超线性复杂度。

最低公共祖先问题由 Alfred Aho、John Hopcroft 和 Jeffrey Ullman (1973) 定义，但 Dov Harel 和 Robert Tarjan (1984) 是xxx个开发出最高效的最低公共祖先数据结构的人。 他们的算法使用重路径分解在线性时间内处理任何树，因此后续的最低公共祖先查询可以在每个查询的恒定时间内得到回答。 但是，它们的数据结构复杂，难以实现。 Tarjan 还发现了一种更简单但效率较低的算法，该算法基于联合查找数据结构，用于计算离线批次节点对的最低共同祖先。

Baruch Schieber 和 Uzi Vishkin (1988) 简化了 Harel 和 Tarjan 的数据结构，导致了具有相同渐近预处理和查询时间界限的可实现结构。 它们的简化是基于这样的原则，即在两种特殊的树中，最低共同祖先很容易确定：如果树是一条路径，那么最低共同祖先可以简单地从两个查询的层次中的最小值计算出来 节点，而如果树是一棵完整的二叉树，则可以以最低共同祖先减少到索引上的简单二元运算的方式对节点进行索引。 Schieber 和 Vishkin 的结构将任何树分解为路径的集合，使得路径之间的连接具有二叉树的结构，并将这两种更简单的索引技术结合起来。

Omer Berkman 和 Uzi Vishkin（1993 年）发现了一种全新的方法来回答最低公共祖先查询，再次实现线性预处理时间和恒定查询时间。 他们的方法涉及通过将每条边加倍来形成从输入树形成的图的欧拉巡回，并使用该巡回按照巡回访问它们的顺序写入节点的级别编号序列； 然后可以将最低公共祖先查询转换为寻找出现在该数字序列的某个子区间内的最小值的查询。 然后，他们通过结合两种技术来处理这个范围最小查询问题 (RMQ)，一种技术基于预先计算大小为 2 的幂的大区间的答案，另一种基于小区间查询的表查找。 这种方法后来由 Michael Bender 和 Martin Farach-Colton (2000) 以简化形式提出。

正如 Gabow、Bentley & Tarjan (1984)，可以使用笛卡尔树技术将范围最小值问题反过来转换回最低公共祖先问题。

Alstrup 等人进行了进一步的简化。 (2004) 和 Fischer & 亨（2006 年）。

Sleator 和 Tarjan (1983) 提出了该问题的动态 LCA 变体，其中数据结构应准备好处理与更改树的操作（即通过添加和删除边重新排列树）混合的 LCA 查询。 这个变体可以在 O ( log ⁡ N ) {displaystyle O(log N)} 时间内解决所有修改和查询树的总大小。 这是通过使用按大小分区的动态树数据结构维护森林来完成的； 然后维护每棵树的重分解，并允许在对数时间内执行 LCA 查询。