All Publications

Succinct Euler-Tour Trees

Jun 2021 (Written: Jun 2021)

Travis Gagie and Sebastian Wild:

Canadian Conference on Computational Geometry
in M. He, D. Sheehy (Eds.)

| read herePDFarXiv |

We show how to maintain unrooted ordered trees in succinct space under the operations of linking trees (by adding an edge) and cutting trees (by deleting an edge), while supporting various queries.

The trees are represented by their Euler tour stored in a macro tree of micro trees. A collection of Euler-tour trees for a forest on $n$ vertices can be stored in $2n + o(n)$ bits such that simple queries take constant time, more complex queries take logarithmic time and updates take polylogarithmic amortized time.