rangemin-2.2.2: Linear range-min algorithms.

Data.RangeMin.LCA

Description

Functions for finding lowest common ancestors in trees in O(1) time, with O(n) preprocessing.

Synopsis

Documentation

type Index = IntSource

The type of a vector index.

lowestCommonAncestor :: Int -> (a -> Index) -> Tree a -> Index -> Index -> aSource

lowestCommonAncestor n ix tree takes a tree whose nodes are mapped by ix to a unique index in the range 0..n-1, and returns a function which takes two indices (corresponding to two nodes in the tree) and returns the label of their lowest common ancestor.

This takes O(n) preprocessing and answers queries in O(1), as it is an application of Data.RangeMin.

For binary trees, consider using Data.RangeMin.LCA.Binary.

quickLCA :: Tree a -> (Int, Tree (Index, a), Index -> Index -> (Index, a))Source

Takes a tree and indexes it in depth-first order, returning the number of nodes, the indexed tree, and the lowest common ancestor function.