2010 Proceedings of the Twelfth Workshop on Algorithm Engineering and Experiments (ALENEX), p. 84-97
DOI: 10.1137/1.9781611972900.9
Full text: Download
We implement and compare the major current techniques for representing general trees in succinct form. This is impor- tant because a general tree of n nodes is usually represented in pointer form, requiring O(nlog n) bits, whereas the suc- cinct representations we study require just 2n + o(n) bits and carry out many sophisticated operations in constant time. Yet, there is no exhaustive study in the literature comparing the practical magnitudes of the o(n)-space and the O(1)-time terms. The techniques can be classified into three broad trends: those based on BP (balanced parenthe- ses in preorder), those based on DFUDS (depth-first unary degree sequence), and those based on LOUDS (level-ordered unary degree sequence). BP and DFUDS require a balanced parentheses representation that supports the core operations findopen, findclose, and enclose, for which we implement and compare three major algorithmic proposals. All the tree rep- resentations require also core operations rank and select on bitmaps, which are already well studied in the literature. We show how to predict the time and space performance of most variants via combining these core operations, and also study some tree operations for which specialized im- plementations exist. This is especially relevant for a recent proposal (K. Sadakane and G. Navarro, SODA'10) which, although belonging to class BP, deviates from the main tech- niques in some cases in order to achieve constant time for the widest range of operations. We experiment over vari- ous types of real-life trees and of traversals, and conclude that the latter technique stands out as an excellent practi- cal combination of space occupancy, time performance, and functionality, whereas others, particularly LOUDS, are still interesting in some limited-functionality niches.