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

Craig Dillabaugh

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 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 + \frac{\epsilon N }{\log_B{N}} + o(N)$ bits, for an arbitrarily selected constant, $\epsilon$, where $0 < \epsilon < 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.