Succinct data structure for dynamic trees with faster queries (Q2420610): Difference between revisions

The paper improves the result of \textit{G. Navarro} and \textit{K. Sadakane} [ACM Trans. Algorithms 10, No. 3, Article No. 16, 39 p. (2014; Zbl 1333.68084)] about dynamic succinct data structures. The improvements consist of reducing the time for the queries level\(_-\)ancestor, level\(_-\)next, level\(_-\)prev, level\(_-\)lmost, level\(_-\)rmost and degree from \(O(\log n)\) to \(O(\log n/\log\log n)\); the queries child\(_-\)rank and child\(_-\)select take \(O(\log n)\) time in both structures, and the queries depth, height, num\(_-\)descendants, parent, lca, first\(_-\)child, last\(_-\)child, next\(_-\)sibling and prev\(_-\)sibling take \(O(\log n/\log\log n)\) in both structures. By reducing the complexity time, the result obtained in this paper is very important in applications implemented on a computer.