Computing on a free tree via complexity-preserving mappings

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

The relationship between linear lists and free trees is studied. We examine a number of well-known data structures for computing functions on linear lists and show that they can be canonically transformed into data structures for computing the same functions defined over free trees. This is used to establish new upper bounds on the complexity of several query-answering problems.

Original languageEnglish (US)
Pages (from-to)337-361
Number of pages25
JournalAlgorithmica
Volume2
Issue number1
DOIs
StatePublished - Mar 1 1987

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Keywords

  • Ackermann's function
  • Free tree
  • Interval tree
  • Linear list
  • Query-answering
  • Range tree

Fingerprint Dive into the research topics of 'Computing on a free tree via complexity-preserving mappings'. Together they form a unique fingerprint.

Cite this