Succinct data structure for dynamic trees with faster queries

DOI10.1016/J.TCS.2019.02.005MaRDI QIDQ2420610zbMATH OpenOpenAlexFDO

Authors Dekel Tsur

Publication date 6 June 2019

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.11255

zbMATH Keywords

ordinal trees, time complexitysuccinct data structures

Mathematics Subject Classification ID

Data structures (68P05) Analysis of algorithms and problem complexity (68Q25)

Abstract: Navarro and Sadakane [TALG 2014] gave a dynamic succinct data structure for storing an ordinal tree. The structure supports tree queries in either $O(logn/loglogn)$ or $O(logn)$ time, and insertion or deletion of a single node in $O(logn)$ 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(logn)$ to $O(logn/loglogn)$.

Review text

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.

Recommendations

• A practical succinct data structure for tree-like graphs
• Succinct and I/O Efficient Data Structures for Traversal in Trees
• Succinct and I/O efficient data structures for traversal in trees
• An Improved Succinct Representation for Dynamic k-ary Trees
• Dynamic Succinct Ordered Trees
• Succinct representation of dynamic trees
• Simple and efficient fully-functional succinct trees
• Representing dynamic binary trees succinctly
• scientific article; zbMATH DE number 2038723
• Fast searching in trees

Cites work

• A Framework for Dynamizing Succinct Data Structures
• A SIMPLE BALANCED SEARCH TREE WITH O(1) WORST-CASE UPDATE TIME
• A simple optimal representation for balanced parentheses
• A uniform paradigm to succinctly encode various families of trees
• Engineering the LOUDS Succinct Tree Representation
• Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree
• Fully functional static and dynamic succinct trees
• scientific article; zbMATH DE number 140457 (Why is no real title available?)
• scientific article; zbMATH DE number 2038723 (Why is no real title available?)
• On the Size of Succinct Indices
• Representing dynamic binary trees succinctly
• Representing trees of higher degree
• Succinct dynamic cardinal trees
• Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets
• Succinct ordinal trees based on tree covering
• Succinct ordinal trees with level-ancestor queries
• Succinct representation of balanced parentheses and static trees
• Succinct representation of dynamic trees
• Succinct representation of labeled trees
• Succinct representations of permutations and functions
• Ultra-succinct representation of ordered trees with applications

Cited in

(9)

• Succinct data structures for nearest colored node in a tree
• Tree pattern query minimization
• Representation of ordered trees with a given degree distribution
• Fast searching in trees
• Succinct Data Structures for Path Queries
• Dynamic tree shortcut with constant degree
• scientific article; zbMATH DE number 3843184 (Why is no real title available?)
• Forward node-selecting queries over trees
• scientific article; zbMATH DE number 1830754 (Why is no real title available?)

This page was built for publication: Succinct data structure for dynamic trees with faster queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2420610)