Paper by Erik D. Demaine
- 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.
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.
- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/1663/16630169.pdf.
- The paper is \copyright Springer-Verlag.
- The paper is 12 pages.
- The paper is available in PostScript (233k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated September 18, 2020 by