Storage representations for tree-like data structures

Abstract

A data encoding is a formal counterpart of the "translation of a logical data structure into a physical storage structure". In this paper, both kinds of structures are represented by graphs; and an encoding is a type of embedding of the guest (logical structure) graph in the host (physical structure) graph. The cost of an encoding is the average amount that the edges of the guest graph are stretched as they are replaced by paths in the host graph via the encoding; this "average" is weighted by an assignment of probabilities to the edges of the guest graph (called a usage pattern) that weights the edges according to their anticipated frequencies of traversals. This paper continues the study begun in [13] of encodings of data structures in the leaves of complete trees. The major thrust of the paper is to show that tree-hosts do not accommodate tree-like guests as congenially as they do array-like guests. Specifically, we study two encodings of tree-guests in tree-hosts, and three usage patterns for the guests. One of these usage patterns can be accommodated with cost independent of the size of the guest by one of the encodings but not by the other; the second usage pattern engenders the complementary situation; and the third usage pattern resists size-independent cost not only on the part of the two encodings studied here but also on the part of any encoding of trees into trees. We do, however, find a third encoding of trees in trees whose cost relative to this intransigent usage pattern is exponentially smaller than the costs of our two encodings and is, in fact, optimal in rate of growth. Motivated by the demonstrated weaknesses of trees as hosts in data encodings, we introduce a new tree-like storage structure called a dree; and we show that drees are quite congenial hosts for array-like and tree-like (and dree-like) guests. Throughout the paper, demonstrations of size-independence in the costs of encodings are accompanied by proofs of the (asympotic) near-optimality of the attained costs. © 1979 Springer-Verlag New York Inc.