Representing Trees of Higher Degree
Representing Trees of Higher Degree
复制标题
代表更高阶的树
DOI：
10.1007/s00453-004-1146-6
复制
发表时间：
2005
期刊：
影响因子：
1.1
通讯作者：
Rao
中科院分区：
文献类型：
--
作者：
David Benoit;E. Demaine;J. Munro;R. Raman;Venkatesh Raman;S. Srinivasa;Rao
摘要本文主要研究有根树的空间高效表示
允许在恒定时间内进行基本导航。虽然大多数人
以前的工作已经集中在二叉树上，我们将注意力转向
高度较高的树木。我们考虑两个基数树(或k-ary
尝试)、
其中每个节点具有k个时隙，标记为{1，...，k}，
它们中的每一个都可能具有
引用一个子节点和序号树，其中每个节点的子节点
都是简单地订购的。我们的表示法使用了许多比特接近
中的信息论下界和支持运算
恒定时间。对于序树，我们支持以下运算
查找学位、父级、第i个子级和子树大小。为
基数树该结构还支持查找
除序号树之外的给定节点的标记为i的子节点
行动。这些表示还提供来自n的映射
将树的节点放到整数{1，...，n}上，给出唯一
将标签添加到树的节点。这个标签可以用来储存
有效地将卫星信息与节点结合。
AbstractThis paper focuses on space efficient representations of rooted trees
that permit basic navigation in constant time. While most of the
previous work has focused on binary trees, we turn our attention to
trees of higher degree. We consider both cardinal trees (or k-ary
tries),
where each node has k slots, labelled {1,...,k},
each of which may have a
reference to a child, and ordinal trees, where the children of each node
are simply ordered. Our representations use a number of bits close
to the information theoretic lower bound and support operations in
constant time. For ordinal trees we support the operations of
finding the degree, parent, ith child, and subtree size. For
cardinal trees the structure also supports finding the
child labelled i of a given node apart from the ordinal tree
operations. These representations also provide a mapping from the n
nodes of the tree onto the integers {1, ..., n}, giving unique
labels to the nodes of the tree. This labelling can be used to store
satellite information with the nodes efficiently.