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