rangemin-2.2.1: Linear range-min algorithms.
Data.RangeMin.LCA.Binary
Description
Functions for finding lowest common ancestors in binary trees in O(1) time, with O(n) preprocessing.
Synopsis
type Index = IntSource
The type of a vector index.
data BinTree a Source
A generic binary tree.
Constructors
quickLCABinary :: BinTree a -> (Int, BinTree (Index, a), Index -> Index -> (Index, a))Source
Takes a binary tree and indexes it inorder, returning the number of nodes, the indexed tree, and the lowest common ancestor function.
lcaBinary :: Int -> (a -> Index) -> BinTree a -> Index -> Index -> aSource
Similar to LCA.lowestCommonAncestor, but optimized for binary trees. This method can reasonably be expected to run twice as fast as lowestCommonAncestor.
LCA.lowestCommonAncestor
lowestCommonAncestor