Functions for finding lowest common ancestors in trees in O(1) time, with O(n) preprocessing.
Documentation
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
takes a tree whose nodes are mapped by
lowestCommonAncestor
n ix treeix
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.