University of Leicester
Browse
paper.pdf (294.06 kB)
Download file

Succinct Representations of Binary Trees for Range Minimum Queries

Download (294.06 kB)
conference contribution
posted on 2013-10-28, 13:05 authored by Pooya Davoodi, Rajeev Raman, Satti Srinivasa Satti
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.

History

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

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science

Source

18th Annual International Computing and Combinatorics Conference (COCOON 2012), Sydney, Australia

Version

  • AM (Accepted Manuscript)

Published in

Davoodi

Publisher

Springer Berlin Heidelberg

issn

0302-9743

eissn

1611-3349

isbn

978-3-642-32240-2;978-3-642-32241-9

Copyright date

2012

Available date

2013-10-28

Publisher version

http://link.springer.com/chapter/10.1007/978-3-642-32241-9_34

Book series

Lecture Notes in Computer Science;7434

Temporal coverage: start date

2012-08-20

Temporal coverage: end date

2012-08-22

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Keywords

    Exports