ENCODING DATA-STRUCTURES IN TREES

The notion of a data encoding is meant to be a formal counterpart of the informal notion of the translauon of a logical data structure into a physical storage structure Both kinds of structures are represented here 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 m the host graph via the encoding, the average is weighted by a probability distribution (called a “usage pattern”) on the edges of the guest graph, that is intended to represent the anticipated pattern of traversing that graph This paper studms encodmgs of data structures in trees, with an eye toward developing techniques for analyzing such encodlngs. Two guest structures are studied here, namely, lines and arrays Upper and lower bounds on the costs of encodmgs of these structures in trees are derived, in several cases these bounds are asymptotically coincident, or at least very close The main results concerning line-guests exhibit certain (best possible) sufficient conditions for the costs of encodmgs of lines in trees to be independent of the lengths of the lines The mare results concerning array-guests are exemplified by the foUowmg The costs of encodlngs of d-dimensional arrays m 2a-ary trees are shown to have colnodent upper and lower bounds of 4 + o(1), and the costs of encodlngs of such arrays in binary trees are shown to have upper and lower bounds of 3d + 1 + o(I) and 2 885d + I + 0 116/d + o(1), respectively, for the case d = 2, the derived bounds are even closer than this general result would suggest the upper and lower bounds for encodmgs of 2-dimensional arrays in binary trees are 7 + o(i) and 6 98 + o(I), respectively. © 1979, ACM. All rights reserved.