Dynamizing Succinct Tree Representations
Dynamizing Succinct Tree Representations
复制标题
动态化简洁树表示
DOI：
10.1007/978-3-642-30850-5_20
复制
发表时间：
2012
影响因子：
4
通讯作者：
R. Raman
中科院分区：
文献类型：
--
作者：
S. Joannou;R. Raman
我们考虑有序树的简洁或节省空间的表示。存在用2n+o(n)位表示静态节点有序树的表示——接近信息论最小值——并支持在RAM模型上o(1)时间内进行导航操作的表示；部分实现具有良好的实用性能。
We consider succinct, or space-efficient, representations of ordinal trees. Representations exist that take 2n+o(n) bits to represent a staticn-node ordinal tree --- close to the information-theoretic minimum --- and support navigational operations in O(1) time on a RAM model; and some implementations have good practical performance.
The situation is different for dynamic ordinal trees. Although there is theoretical work on succinct dynamic ordinal trees, there is little work on the practical performance of these data structures. Motivated by applications to representing XML documents, in this paper, we report on a preliminary study on dynamic succinct data structures. Our implementation is based on representing the tree structure as a sequence of balanced parentheses, with navigation done using the min-max tree of Sadakane and Navarro (SODA '10). Our implementation shows promising performance for update and navigation, and our findings highlight two issues that we believe will be important to future implementations: the difference between the finger model of (say) Farzan and Munro (ICALP '09) and the parenthesis model of Sadakane and Navarro, and the choice of the balanced tree used to represent the min-max tree.