rangemin-2.0: 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

Index is used as a node identifier, so that the user can refer to tree nodes in a random-access fashion.

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.