Lowest Common Ancestor

As Lowest Common Ancestor (LCA ) or " last common ancestor " a determination concept in computer science and graph theory refers to the pre-processed a given rooted tree data structures efficiently, so then requests after the last common ancestor can be answered for arbitrary pairs of nodes in constant time.

Trees are among the most fundamental data structures in computer science. They are often used to represent the data in a hierarchical or nested structure. Two classic examples are the search and decision trees. Algorithmic questions for standard trees are, for example, the pre-, post - and Inordertraversierung. A less well-known in this context algorithmic problem is the search for the last common ancestor (LCA ).

Definition of the LCA

Given a tree with a root node, total nodes and a height. Lowest Common Ancestor of (LCA) of two nodes and one node. One parent node of both, and is farthest from the root, that is having the maximum depth

The objective is to efficiently process a given tree so that LCA queries can be answered as quickly as possible.

Areas of application

The LCA detection can be used to determine the LCA of gene trees (bio - computer science ).

Development ( story)

The LCA problem was first defined in 1973 by Alfred Aho, John Hopcroft and Jeffrey Ullman.

In 1984, Dov Harel and Robert Tarjan developed the first efficient data structure to solve the LCA problem. Here, the input tree (see Landau symbols) is preprocessed so that the queries can be answered in constant time. However, the data structure is considered to be very complex and difficult to implement. Tarjan later found a simpler, but less efficient algorithm based on the union-find structure and the LCA of a pre- calculated amount of node pairs determined ( Tarjan Offline Least Common Ancestor 's Algorithm ( TOLCA ) ). In 1988 Baruch simplified slider and Uzi Vishkin this data structure, so that it has been implemented, and yet has a pre-processing of the time and expense of a query.

1993 discovered Omer Berkman and Uzi Vishkin a new way, the LCA problem by means of reducing and Range Minimum Query ( RMQ) to solve. The time spent here has linear preprocessing time and constant query time. This approach was simplified in 2000 by Michael Bender and Martin Farach - Colton.