Paper by Erik D. Demaine

Reference:

David Benoit, Erik D. Demaine, J. Ian Munro, and Venkatesh Raman, “Representing Trees of Higher Degree”, in Proceedings of the 6th International Workshop on Algorithms and Data Structures (WADS'99), Lecture Notes in Computer Science, volume 1663, Vancouver, British Columbia, Canada, August 11–14, 1999, pages 169–180.

Abstract:

This paper focuses on space efficient representations of 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 (rooted trees where each node has k positions each of which may have a reference to a child) and ordinal trees (the children of each node are simply ordered). Our representations use a number of bits within a lower order term of the information theoretic lower bound. For cardinal trees the structure supports finding the parent, child i or subtree size of a given node. For ordinal trees we support the operations of finding the degree, parent, ith child and subtree size. These operations provide a mapping from the n nodes of the tree onto the integers [1, n] and all are performed in constant time, except finding child i in cardinal trees. For k-ary cardinal trees, this operation takes O(lg lg k) time for the worst relationship between k and n, and constant time if k is much less than n.

Comments:

This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1663/16630169.pdf.

Copyright:

The paper is \copyright Springer-Verlag.

Length:

The paper is 12 pages.

Availability:

The paper is available in PostScript (233k).

See information on file formats.

[Google Scholar search]