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

摘要

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 i th child of a node.