Artículo de revista
Simple and efficient fully-functional succinct trees
Fecha
2016-12-20Registro en:
Theoretical Computer Science 656 (2016) 135–145
10.1016/j.tcs.2016.04.031
Autor
Córdova Monroy, Joshimar
Navarro, Gonzalo
Institución
Resumen
The fully-functional succinct tree representation of Navarro and Sadakane (2014) [10] 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(lgn) 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(lglgn) for the operations. An implementation based on this version is experimentally shown to be superior to existing implementations.