Traversing Grammar-Compressed Trees with Constant Delay

Markus Lohrey, Sebastian Maneth, Carl Philipp Reh

Research output: Chapter in Book/Report/Conference proceedingConference contribution


A grammar-compressed ranked tree is represented with a linear space overhead so that a single traversal step, i.e., the move to the parent or the ith child, can be carried out in constant time. The data structure is extended so that equality of subtrees can be checked in constant time.
Original languageEnglish
Title of host publication2016 Data Compression Conference
Number of pages10
Publication statusPublished - 2016
Event2016 Data Compression Conference - Snowbird, United States
Duration: 29 Mar 20161 Apr 2016


Conference2016 Data Compression Conference
Abbreviated titleDCC 2016
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Traversing Grammar-Compressed Trees with Constant Delay'. Together they form a unique fingerprint.

Cite this