This crate provides traits to describe operations on EVAL-LINK-UPDATE data structures (similar to operations defined by Tarjan in "Applications of Path Compression on Balanced Trees.”).
It also provides implementations of basic EVAL-LINK-UPDATE structures such as forest with path compression on evaluation (see [CompressedForest]).
Suppose we have an associative operation ⊕. The three operations made available on forests are:
- EVAL(n): find the root of the tree that contains the node n, let say r, and compute the product of all values on the path from r to n (i.e value(r) ⊕ ... ⊕ value(n))
- LINK(n, m): find the root of the tree that contains the node m, let say r, and link it to the node n (i.e r becomes a child of n)
- UPDATE(n, v): find the root of the tree that contains the node n, let say r, and replace its value by v