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]
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated November 27, 2024 by
Erik Demaine.