Please use this identifier to cite or link to this item:
Title: Succinct Representations of Binary Trees for Range Minimum Queries
Authors: Davoodi, Pooya
Raman, Rajeev
Satti, Satti Srinivasa
First Published: 2012
Presented at: 18th Annual International Computing and Combinatorics Conference (COCOON 2012), Sydney, Australia
Start Date: 20-Aug-2012
End Date: 22-Aug-2012
Publisher: Springer Berlin Heidelberg
Citation: Davoodi, P.; Raman, R.; Rao, S.S. ‘Succinct Representations of Binary Trees for Range Minimum Queries’ in Gudmundsson, J.; Mestre, J.; Viglas, T. (Eds.) Computing and Combinatorics - Proceedings of the 18th Annual International Computing and Combinatorics Conference (COCOON 2012) (2012 Springer-Verlag Berlin Heidelberg), pp. 396-407
Abstract: We provide two succinct representations of binary trees that can be used to represent the Cartesian tree of an array A of size n. Both the representations take the optimal 2n + o(n) bits of space in the worst case and support range minimum queries (RMQs) in O(1) time. The first one is a modification of the representation of Farzan and Munro (SWAT 2008); a consequence of this result is that we can represent the Cartesian tree of a random permutation in 1.92n + o(n) bits in expectation. The second one uses a well-known transformation between binary trees and ordinal trees, and ordinal tree operations to effect operations on the Cartesian tree. This provides an alternative, and more natural, way to view the 2D-Min-Heap of Fischer and Huen (SICOMP 2011). Furthermore, we show that the pre-processing needed to output the data structure can be performed in linear time using o(n) bits of extra working space, improving the result of Fischer and Heun who use n + o(n) bits working space.
Series/Report no.: Lecture Notes in Computer Science;7434
DOI Link: 10.1007/978-3-642-32241-9_34
ISSN: 0302-9743
ISBN: 978-3-642-32240-2
eISSN: 1611-3349
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2012 Springer-Verlag Berlin Heidelberg. Deposited with reference to the publisher’s open access archiving policy. The final publication is available at
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

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

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