Traversing Grammar-Compressed Trees with Constant Delay
| Autor: | Carl Philipp Reh, Sebastian Maneth, Markus Lohrey |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2015 |
| Předmět: |
FOS: Computer and information sciences
Binary tree Linear space ComputerApplications_COMPUTERSINOTHERSYSTEMS 0102 computer and information sciences 02 engineering and technology Data structure 01 natural sciences Tree (data structure) Tree traversal 010201 computation theory & mathematics 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Overhead (computing) Data Structures and Algorithms (cs.DS) Pattern matching Constant (mathematics) Algorithm Mathematics |
| Zdroj: | DCC Lohrey, M, Maneth, S & Reh, C P 2016, Traversing Grammar-Compressed Trees with Constant Delay . in 2016 Data Compression Conference . 2016 Data Compression Conference, Snowbird, United States, 29/03/16 . < http://arxiv.org/abs/1511.02141 > |
| Popis: | 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 i-th child, can be carried out in constant time. Moreover, we extend our data structure such that equality of subtrees can be checked in constant time. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|