跳转到内容

User:Ivyxjc/沙盒

维基百科，自由的百科全书


In a tree data structure where each node points to its parent, the lowest common ancestor can be easily determined by finding the first intersection of the paths from v and w to the root. In general, the computational time required for this algorithm is O(h) where h is the height of the tree (length of longest path from a leaf to the root). However, there exist several algorithms for processing trees so that lowest common ancestors may be found more quickly. Tarjan's off-line lowest common ancestors algorithm, for example, preprocesses a tree in linear time to provide constant-time LCA queries. In general DAGs, similar algorithms exist, but with super-linear complexity.

历史

[编辑]

最近公共祖先问题由阿尔佛雷德·艾侯,约翰·霍普克洛夫特（英语：John Hopcroft）和杰佛里·厄尔曼（英语：Jeffrey Ullman）在1973年首次定义。但是有效的最近公共祖先数据结构由多夫·哈雷尔和罗伯特·塔扬于1984年首次提出，他们的算法在线性时间内处理一个树之后每次查询都可以在常数时间内得到最近公共祖先，但是该算法过于复杂，难以实现。塔扬还发现一个基于联合查找算法的简单的但略微低效算法来解决该问题，这种方法被称为塔扬离线最近公共祖先算法（英语：Tarjan's off-line lowest common ancestors algorithm）

巴鲁克·西贝尔和乌兹·威斯金（英语：Uzi Vishkin）在1988年简化了哈雷尔和塔扬的数据结构，该算法同样可以达到线性时间内处理一个树，常数时间内得到最近公共祖先的效果。他们的算法基于这样的一个原则，在下面这两种树中，最近公共祖先是很好寻找的：1。如果树是一个路径，

Baruch Schieber and Uzi Vishkin （1988） simplified the data structure of Harel and Tarjan, leading to an implementable structure with the same asymptotic preprocessing and query time bounds. Their simplification is based on the principle that, in two special kinds of trees, lowest common ancestors are easy to determine: if the tree is a path, then the lowest common ancestor can be computed simply from the minimum of the levels of the two queried nodes, while if the tree is a complete binary tree, the nodes may be indexed in such a way that lowest common ancestors reduce to simple binary operations on the indices. The structure of Schieber and Vishkin decomposes any tree into a collection of paths, such that the connections between the paths have the structure of a binary tree, and combines both of these two simpler indexing techniques.

Omer Berkman 和乌兹·威斯金（英语：Uzi Vishkin）于1993年发现一个全新的方法来解决最近公共祖先问题，同样可以达到先前的低复杂度。他们利用深度优先搜索将一个拥有N个节点的二叉树转换为长度为2N-1的欧拉序列，并记录下每一个节点第一次在序列中出现的位置。这样就可以将最近公共祖先问题转换为范围最值查询问题。之后，他们就结合两种方法来解决范围最值查询问题。 Omer Berkman and Uzi Vishkin （1993） discovered a completely new way to answer lowest common ancestor queries, again achieving linear preprocessing time with constant query time. Their method involves forming an Euler tour of a graph formed from the input tree by doubling every edge, and using this tour to write a sequence of level numbers of the nodes in the order the tour visits them; a lowest common ancestor query can then be transformed into a query that seeks the minimum value occurring within some subinterval of this sequence of numbers. They then handle this range minimum query problem by combining two techniques, one technique based on precomputing the answers to large intervals that have sizes that are powers of two, and the other based on table lookup for small-interval queries. This method was later presented in a simplified form by Michael Bender and Martin Farach-Colton （2000）. As had been previously observed by Gabow, Bentley & Tarjan (1984), the range minimum problem can in turn be transformed back into a lowest common ancestor problem using the technique of Cartesian trees.

Further simplifications were made by Alstrup et al. (2004) and Fischer & Heun (2006).

A variant of the problem is the dynamic LCA problem in which the data structure should be prepared to handle LCA queries intermixed with operations that change the tree (that is, rearrange the tree by adding and removing edges) This variant can be solved using O(logN) time for all modifications and queries. This is done by maintaining the forest using the dynamic trees data structure with partitioning by size; this then maintains a heavy-;light decomposition of each tree, and allows LCA queries to be carried out in logarithmic time in the size of the tree.

Without preprocessing you can also improve the naïve online algorithm's computation time to O(log h) by storing the paths through the tree using skew-binary random access lists, while still permitting the tree to be extended in constant time (Edward Kmett (2012)). This allows LCA queries to be carried out in logarithmic time in the height of the tree.

Extension to directed acyclic graphs

[编辑]
A DAG with the common ancestors of x and y in light green, and their lowest common ancestors in dark green.

While originally studied in the context of trees, the notion of lowest common ancestors can be defined for directed acyclic graphs (DAGs), using either of two possible definitions. In both, the edges of the DAG are assumed to point from parents to children.

  • Given G = (V, E), Aït-Kaci et al. (1989) define a poset (V, ≤) such that x ≤ y iff x is in the reflexive transitive closure of y. The lowest common ancestors of x and y are then the maximum elements under ≤ of the common ancestor set {z ∈ V | z ≤ x and z ≤ y}.
  • Bender et al. (2005) give an equivalent definition, where the lowest common ancestors of x and y are the nodes of out-degree zero in the subgraph of G induced by the set of common ancestors of x and y.

In a tree, the lowest common ancestor is unique; in a DAG of n nodes, each pair of nodes may have as much as n-2 LCAs (Bender et al. 2005), while the existence of an LCA for a pair of nodes is not even guaranteed in arbitrary connected DAGs.

A brute-force algorithm for finding lowest common ancestors is given by Aït-Kaci et al. (1989): find all ancestors of x and y, then return the maximum element of the intersection of the two sets. Better algorithms exist that, analogous to the LCA algorithms on trees, preprocess a graph to enable constant-time LCA queries. The problem of LCA existence can be solved optimally for sparse DAGs by means of an O(|V||E|) algorithm due to Kowaluk & Lingas (2005).

Applications

[编辑]

The problem of computing lowest common ancestors of classes in an inheritance hierarchy arises in the implementation of object-oriented programming systems (Aït-Kaci et al. 1989). The LCA problem also finds applications in models of complex systems found in distributed computing (Bender et al. 2005).

See also

[编辑]

References

[编辑]
[编辑]
检索自“https://zh.wikipedia.org/w/index.php?title=User:Ivyxjc/沙盒&oldid=47188616”