Storage Representations for Tree-Like Data Structures

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.

Authors

• Arnold L. Rosenberg
• Derick Wood
• Zvi Galil

Keywords

No keywords are indexed for this paper.