Package com.jgalgo.alg.tree

Class LowestCommonAncestorStaticRmq

java.lang.Object

com.jgalgo.alg.tree.LowestCommonAncestorStaticAbstract

com.jgalgo.alg.tree.LowestCommonAncestorStaticRmq

All Implemented Interfaces:

LowestCommonAncestorStatic

public class LowestCommonAncestorStaticRmq
extends LowestCommonAncestorStaticAbstract

Static LCA implementation using RMQ.

By traversing the tree once and assigning for each vertex a number corresponding to its depth, the LCA query is equivalent to a range minimum query. This RMQ problem is a special case of RMQ, as the different between any pair of consecutive elements is always +1/-1, and RmqStaticPlusMinusOne can be used.

The algorithm require preprocessing of \(O(n)\) time and space and answer queries in \(O(1)\) time.

Based on 'Fast Algorithms for Finding Nearest Common Ancestors' by D. Harel, R. Tarjan (1984).

Author:

Barak Ugav

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.tree.LowestCommonAncestorStatic

LowestCommonAncestorStatic.IDataStructure

Constructor Summary

Constructors

Constructor	Description
LowestCommonAncestorStaticRmq()	Create a new static LCA algorithm object.

Method Summary

Methods inherited from class com.jgalgo.alg.tree.LowestCommonAncestorStaticAbstract

preProcessTree

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

LowestCommonAncestorStaticRmq

public LowestCommonAncestorStaticRmq()

Create a new static LCA algorithm object.

Please prefer using LowestCommonAncestorStatic.newInstance() to get a default implementation for the LowestCommonAncestorStatic interface.