V
 the graph vertex typeE
 the graph edge typepublic class BinaryLiftingLCAFinder<V,E> extends Object implements LowestCommonAncestorAlgorithm<V>
The method appears in Bender, Michael A., and Martın FarachColton. "The level ancestor problem simplified." Theoretical Computer Science 321.1 (2004): 512 and it is also nicely presented in the following article on Topcoder for more details about the algorithm.
Algorithm idea:
We improve on the naive approach by using jump pointers. These are pointers at a node which
reference one of the node’s ancestors. Each node stores jump pointers to ancestors at levels 1,
2, 4, . . . , 2^k.
Queries are answered by repeatedly jumping from node to node, each time jumping more than half of
the remaining levels between the current ancestor and the goal ancestor (i.e. the lca). The
worstcase number of jumps is $O(log(V))$.
Preprocessing Time complexity: $O(V log(V))$
Preprocessing Space complexity: $O(V log(V))$
Query Time complexity: $O(log(V))$
Query Space complexity: $O(1)$
For small (i.e. less than 100 vertices) trees or forests, all implementations behave similarly.
For larger trees/forests with less than 50,000 queries you can use either
BinaryLiftingLCAFinder
, HeavyPathLCAFinder
or EulerTourRMQLCAFinder
. Fo
more than that use EulerTourRMQLCAFinder
since it provides $O(1)$ per query.
Spacewise, HeavyPathLCAFinder
and TarjanLCAFinder
only use a linear amount while
BinaryLiftingLCAFinder
and EulerTourRMQLCAFinder
require linearithmic space.
For DAGs, use NaiveLCAFinder
.
Constructor and Description 

BinaryLiftingLCAFinder(Graph<V,E> graph,
Set<V> roots)
Construct a new instance of the algorithm.

BinaryLiftingLCAFinder(Graph<V,E> graph,
V root)
Construct a new instance of the algorithm.

Modifier and Type  Method and Description 

V 
getLCA(V a,
V b)
Return the LCA of a and b

Set<V> 
getLCASet(V a,
V b)
Note: This operation is not supported.
Return the computed set of LCAs of a and b 
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
getBatchLCA, getBatchLCASet
public BinaryLiftingLCAFinder(Graph<V,E> graph, V root)
Note: The constructor will NOT check if the input graph is a valid tree.
graph
 the input graphroot
 the root of the graphpublic BinaryLiftingLCAFinder(Graph<V,E> graph, Set<V> roots)
Note: If two roots appear in the same tree, an error will be thrown.
Note: The constructor will NOT check if the input graph is a valid forest.
graph
 the input graphroots
 the set of roots of the graphpublic V getLCA(V a, V b)
getLCA
in interface LowestCommonAncestorAlgorithm<V>
a
 the first element to find LCA forb
 the other element to find the LCA forpublic Set<V> getLCASet(V a, V b)
getLCASet
in interface LowestCommonAncestorAlgorithm<V>
a
 the first element to find LCA forb
 the other element to find the LCA forUnsupportedOperationException
 if the method is calledCopyright © 2018. All rights reserved.