Paper by Erik D. Demaine

Reference:

David Benoit, Erik D. Demaine, J. Ian Munro, Rajeev Raman, Venkatesh Raman, and S. Srinivasa Rao, “Representing Trees of Higher Degree”, Algorithmica, volume 43, number 4, December 2005, pages 275–292.

Abstract:

This paper focuses on space efficient representations of rooted trees that permit basic navigation in constant time. While most of the previous work has focused on binary trees, we turn our attention to trees of higher degree. We consider both cardinal trees (or k-ary tries), where each node has k slots, labelled {1, …, k}, each of which may have a reference to a child, and ordinal trees, where the children of each node are simply ordered. Our representations use a number of bits close to the information theoretic lower bound and support operations in constant time. For ordinal trees we support the operations of finding the degree, parent, ith child and subtree size. For cardinal trees the structure also supports finding the child labeled i of a given node apart from the ordinal tree operations. These representations also provide a mapping from the n nodes of the tree onto the integers {1, …, n}, giving unique labels to the nodes of the tree. This labelling can be used to store satellite information with the nodes efficiently.

Comments:

This paper is also available from SpringerLink.

Length:

The paper is 24 pages.

Availability:

The paper is available in PostScript (467k), gzipped PostScript (187k), and PDF (210k).

See information on file formats.

[Google Scholar search]