Succinct data structure for dynamic trees with faster queries

摘要

Navarro and Sadakane [19] gave a dynamic succinct data structure for storing an ordinal tree. The structure supports tree queries in either O(log n/log log n) or O(log n) time, and insertion or deletion of a single node in O(log n) time. In this paper we improve the result of Navarro and Sadakane by reducing the time complexities of some queries (e.g. degree and level_ancestor) from O(log n) to O(log n/log log n). (C) 2019 Elsevier B.V. All rights reserved.