Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees.

Authors :: Lohrey, Markus
Maneth, Sebastian
Reh, Carl Philipp
Source :: Algorithmica. Jul2018, Vol. 80 Issue 7, p2082-2105. 24p.
Publication Year :: 2018
Abstract: A linear space data structure for grammar-compressed trees is presented which allows to carry out tree traversal operations and subtree equality checks in constant time. A traversal step consists of moving to the parent or to the <italic>i</italic>th child of a node. [ABSTRACT FROM AUTHOR]

Subjects :: *VECTOR spaces
*DATA structures
*TREE graphs
*DECISION trees
*GRAPHIC methods

Full Text Access

Tools