首页> 外文会议>Algorithms and computation >Succinct and I/O Efficient Data Structures for Traversal in Trees
【24h】

Succinct and I/O Efficient Data Structures for Traversal in Trees

机译:树中遍历的简洁和I / O高效数据结构

获取原文
获取原文并翻译 | 示例

摘要

We present two results for path traversal in trees, where the traversal is performed in an asymptotically optimal number of I/Os and the tree structure is represented succinctly. Our first result is for bottom-up traversal that starts with a node in the tree T and traverses a path to the root. For blocks of size B, a tree on N nodes, and for a path of length K, we design data structures that permit traversal of the bottom-up path in O(K/B) I/Os using only 2N + εN/log_BN + o(N) bit,for an arbitrarily selected constant, e, where 0 < E < 1. Our second result is for top-down traversal in binary trees. We store T using (3 + q)N + o(N) bits, where q is the number of bits required to store a key, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.
机译:我们给出了树中路径遍历的两个结果,其中遍历以渐近最佳I / O数执行,并且树结构简洁地表示。我们的第一个结果是自下而上的遍历,它从树T中的一个节点开始,并遍历到根的路径。对于大小为B的块,N个节点上的树以及长度为K的路径,我们设计的数据结构允许仅使用2N +εN/ log_BN来遍历O(K / B)I / O中的自底向上路径+ o(N)位,用于任意选择的常数e,其中0

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号