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 a tree on N nodes and traverses a path to the root. We show how a tree T on N nodes with q-bit keys, where q=O(lg?N), can be blocked in a succinct fashion such that a bottom-up traversal requires O(K/B+1) I/Os using only $(2+q)N + q cdot[ frac{2 tau N (q + 2 lg B)}{w} + o(N)] + frac{8tau N lg B}{w}$ bits to store T for any constant 0<τ<1, where K is the path length and w is the word size. This data structure is succinct because the above space cost is at most (2+q)N+q?(ηN+o(N)) bits for any arbitrarily selected constant, η, such that 0<η<1. When storing keys with tree nodes is not required, we can represent T in $2N + frac{epsilon Nlg B}{w} + o(N)$ bits, where ? is an arbitrarily selected constant such that 0<?<1, while providing the same support for queries. Our second result is for top-down traversal in binary trees. We store the tree in (3+q)N+o(N) bits, while top-down traversal can still be performed in an asymptotically optimal number of I/Os.