Succinct data structure for dynamic trees with faster queries

Autor:	Dekel Tsur
Rok vydání:	2019
Předmět:	FOS: Computer and information sciences General Computer Science Degree (graph theory) Structure (category theory) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics Succinct data structure Single node Tree (data structure) 010201 computation theory & mathematics TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Data Structures and Algorithms (cs.DS) 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS Mathematics
Zdroj:	Theoretical Computer Science. 780:12-19
ISSN:	0304-3975
DOI:	10.1016/j.tcs.2019.02.005
Popis:	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 ) .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::50ba7eef063e3797d5fd3e323e90e690 https://doi.org/10.1016/j.tcs.2019.02.005 Zobrazit plný text záznamu Full Text from ScienceDirect