Storage representations for tree-like data structures

Abstract

We review the motivation underlying the study of data encodings and the formal framework of the study. We then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. In response to these results, we propose a new data structure, called a dree, which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.