Computing on a free tree via complexity-preserving mappings
B Chazelle - Algorithmica, 1987 - Springer
Algorithmica, 1987•Springer
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.
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.
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.
Springer