Computing on a free tree via complexity-preserving mappings
Computing on a free tree via complexity-preserving mappings
复制标题
通过保留复杂性的映射在自由树上进行计算
DOI：
10.1007/bf01840366
复制
发表时间：
1984
期刊：
影响因子：
1.1
通讯作者：
B. Chazelle
中科院分区：
文献类型：
--
作者：
B. Chazelle
研究了线性表与自由树的关系。我们研究了一些著名的数据结构的线性列表上的计算功能，并表明，它们可以被转换成规范的数据结构，用于计算相同的功能定义在自由树。这是用来建立新的上限的复杂性的几个问答问题。
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.