Please use this identifier to cite or link to this item:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDavoodi, Pooya-
dc.contributor.authorRaman, Rajeev-
dc.contributor.authorSrinivasa Rao Satti-
dc.identifier.citationMathematics in Computer Science, 2017, 13en
dc.descriptionThe file associated with this record is under embargo until 12 months after publication, in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.en
dc.description.abstractWe observe that a standard transformation between ordinal trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree representations. There are four symmetric versions of these transformations. Via these transformations we get four succinct representations of n-node binary trees that use 2n + n/(log n) ^Θ(1) bits and support (among other operations) navigation, inorder numbering, one of preorder or postorder numbering, subtree size and lowest common ancestor (LCA) queries. While this functionality, and more, is also supported in O(1) time using 2n + o(n) bits by Davoodi et al.’s (Phil. Trans. Royal Soc. A 372 (2014)) extension of a representation by Farzan and Munro (Algorithmica 6 (2014)), their redundancy, or the o(n) term, is much larger, and their approach may not be suitable for practical implementations. One of these transformations is related to the Zaks’ sequence (S. Zaks, Theor. Comput. Sci. 10 (1980)) for encoding binary trees, and we thus provide the first succinct binary tree representation based on Zaks’ sequence. The ability to support inorder numbering is crucial for the well-known range-minimum query (RMQ) problem on an array A of n ordered values. Another of these transformations is equivalent to Fischer and Heun’s (SIAM J. Comput. 40 (2011)) 2d-MinHeap structure for this problem. Yet another variant allows an encoding of the Cartesian tree of A to be constructed from A using only O(√n log n) bits of working space.en
dc.description.sponsorshipS. R. Satti’s research was partly supported by Basic Science Research Program through the National Research Foundation of Korea funded by the Ministry of Education, Science and Technology (Grant number 2012-0008241). P. Davoodi’s research was supported by NSF grant CCF-1018370 and BSF grant 2010437 (this work was partially done while P.Davoodi was with MADALGO, Center for Massive Data Algorithmics, a Center of the Danish National Research Foundation, grant DNRF84, Aarhus University, Denmark).en
dc.publisherSpringer Verlag (Germany) for Birkhäuser Baselen
dc.rightsCopyright © 2017, Springer Verlag (Germany). Deposited with reference to the publisher’s open access archiving policy.en
dc.titleOn Succinct Representations of Binary Treesen
dc.typeJournal Articleen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERINGen
pubs.organisational-group/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Scienceen
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
paper-full.pdfPost-review (final submitted author manuscript)361.69 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.