Computing on a free tree via complexity-preserving mappings

Bernard Chazelle

doi:10.1007/BF01840366

Computing on a free tree via complexity-preserving mappings

Bernard Chazelle

Research output: Contribution to journal › Article › peer-review

87 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 language	English (US)
Pages (from-to)	337-361
Number of pages	25
Journal	Algorithmica
Volume	2
Issue number	1-4
DOIs	https://doi.org/10.1007/BF01840366
State	Published - Nov 1987
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
Computer Science Applications
Applied Mathematics

Keywords

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

Access to Document

10.1007/BF01840366

Cite this

@article{d221d60850ce4be6b8e15873ac8a8c80,

title = "Computing on a free tree via complexity-preserving mappings",

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.",

keywords = "Ackermann's function, Free tree, Interval tree, Linear list, Query-answering, Range tree",

author = "Bernard Chazelle",

year = "1987",

month = nov,

doi = "10.1007/BF01840366",

language = "English (US)",

volume = "2",

pages = "337--361",

journal = "Algorithmica",

issn = "0178-4617",

publisher = "Springer New York",

number = "1-4",

}

TY - JOUR

T1 - Computing on a free tree via complexity-preserving mappings

AU - Chazelle, Bernard

PY - 1987/11

Y1 - 1987/11

N2 - 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.

AB - 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.

KW - Ackermann's function

KW - Free tree

KW - Interval tree

KW - Linear list

KW - Query-answering

KW - Range tree

UR - http://www.scopus.com/inward/record.url?scp=52449148136&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=52449148136&partnerID=8YFLogxK

U2 - 10.1007/BF01840366

DO - 10.1007/BF01840366

M3 - Article

AN - SCOPUS:52449148136

SN - 0178-4617

VL - 2

SP - 337

EP - 361

JO - Algorithmica

JF - Algorithmica

IS - 1-4

ER -

Computing on a free tree via complexity-preserving mappings

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this