Dekel Tsur

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).