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

摘要

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.