Constant time retrieval of I<Nearest Common Ancestor>

This package provides constant-time retrieval of the Nearest Common Ancestor (NCA) of nodes in a tree. The implementation is based on the algorithm by Harel and which can, after linear-time preprocessing, retrieve the nearest common ancestor of two nodes in constant time. To implement the algorithm it is necessary to store some data for each node in the tree. * - A _node number_ assigned to the node in a pre-order fashion * - A number to identify the _run_ of the node ("ALGORITHM") * - The _leader_ for each run, which should be retrievable through its node number * - A _magic_ number ("ALGORITHM") * - The _parent_ node for each node * - The _maximum_ number assigned to a any node in the subtree All data above, with the exception of the node number, is stored in an array inside the 'Algorithm::Tree::NCA' object. The node number has to be stored in the actual tree node in some manner (alternative solutions would be to slow to give constant-time retrieval), which requires a _set method_ and a _get method_ for the nodes. Since the most common case is using hashes to represent nodes, there are default implementations of the set and get methods. The default set method is: sub _set_method { my($node,$value) = @_; $node->{'_nca_number'} = $value; } and the default get method is: sub _get_method { my($node) = @_; return $node->{'_nca_number'}; } If have chosen another representation of your nodes, you can provide alternative set and get methods by using the *-set* and *-get* options when creating the 'Algorithm::Tree::NCA' object.

There is no official package available for openSUSE Leap 15.3


openSUSE Tumbleweed