Lowest Common Ancestor

The lowest common ancestor (LCA) is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).

The LCA of v and w in T is the shared ancestor of v and w that is located farthest from the root. Computation of lowest common ancestors may be useful, for instance, as part of a procedure for determining the distance between pairs of nodes in a tree: the distance from v to w can be computed as the distance from the root to v, plus the distance from the root to w, minus twice the distance from the root to their lowest common ancestor.

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, in constant time per query after a linear time preprocessing stage.

Other articles related to "lowest common ancestor, lowest common ancestors, common, common ancestors, lowest, ancestor":

Cartesian Tree - Range Searching and Lowest Common Ancestors
... In a Cartesian tree, this minimum value may be found at the lowest common ancestor of the leftmost and rightmost values in the subsequence ... the first illustration, the minimum value of the subsequence (10) forms the lowest common ancestor of the leftmost and rightmost values (12 and 15) ... Because lowest common ancestors may be found in constant time per query, using a data structure that takes linear space to store and that may be constructed in linear ...
Lowest Common Ancestor - History
... The lowest common ancestor problem was defined by Alfred Aho, John Hopcroft, and Jeffrey Ullman (1973), but Dov Harel and Robert Tarjan (1984) were the first to develop an ... processes any tree in linear time, so that subsequent lowest common ancestor queries may be answered in constant time per query ... algorithm, based on the union-find data structure, for computing lowest common ancestors of an offline batch of pairs of nodes ...
Common-mode Signal
... Common-mode signal is the component of an analog signal which is present with one sign on all considered conductors ... In telecommunication, common-mode signal on a transmission line is known as longitudinal voltage ... where the signal is transferred with differential voltage use, the common-mode signal is called a half-sum of voltages When referenced to the local common or ground, a common-mode signal ...
Tarjan's Off-line Least Common Ancestors Algorithm
... In computer science, Tarjan's off-line least common ancestors algorithm (more precisely, least should actually be lowest) is an algorithm for computing lowest common ancestors for pairs of nodes in a tree, based ... The lowest common ancestor of two nodes d and e in a rooted tree T is the node g that is an ancestor of both d and e and that has the greatest depth in T ... Tarjan's algorithm is offline that is, unlike other lowest common ancestor algorithms, it requires that all pairs of nodes for which the lowest common ancestor is desired ...
Common Chimpanzee
... The common chimpanzee (Pan troglodytes), also known as the robust chimpanzee, is a species of great ape ... Colloquially, the common chimpanzee is often called the chimpanzee (or "chimp"), though technically this term refers to both species in the genus Pan the common chimpanzee ... The common chimpanzee is covered in coarse black hair, but has a bare face, fingers, toes, palms of the hands and soles of the feet ...

Famous quotes containing the words ancestor, lowest and/or common:

I cannot yet begin to understand
Why we are proud that an ancestor knew
The crazy Poe, who was not of our kind
Bats in the belfry that round and round flew
In vapors not quite wholesome for the mind.
Allen Tate (1899–1979)

All womankind, from the highest to the lowest ... love jokes; the difficulty is to know how they choose to have them cut; and there is no knowing that, but by trying, as we do with our artillery in the field, by raising or letting down their breeches, till we hit the mark.
Laurence Sterne (1713–1768)

Unpretending mediocrity is good, and genius is glorious; but a weak flavor of genius in an essentially common person is detestable. It spoils the grand neutrality of a commonplace character, as the rinsings of an unwashed wine-glass spoil a draught of fair water.
Oliver Wendell Holmes, Sr. (1809–1894)