|
Title |
Simple and Efficient Fully-Functional Succinct Trees |
|
Authors |
Joshimar Cordova, Gonzalo Navarro |
|
Publication date |
2016 |
|
Abstract |
The fully-functional succinct tree representation of Navarro and Sadakane (ACM Transactions on Algorithms, 2014) supports a large number of operations in constant time using 2n+o(n) bits. However, the full idea is hard to implement. Only a simplified version with O(log n) operation time has been implemented and shown to be practical and competitive. We describe a new variant of the original idea that is much simpler to implement and has worst-case time O(log log n) for the operations. An implementation based on this version is experimentally shown to be superior to existing implementations. |
|
Pages |
135-145 |
|
Volume |
656PB |
|
Journal name |
Theoretical Computer Science |
|
Publisher |
Elsevier Science (Amsterdam, The Netherlands) |
|
Reference URL |
|
