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

succinct data structuresordinal trees, time complexity

Mathematics Subject Classification ID

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

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

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

• scientific article; zbMATH DE number 140457 (Why is no real title available?)
• scientific article; zbMATH DE number 2038723 (Why is no real title available?)
• 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
• 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)

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

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)