Scholarlink

This paper presents a novel data structure designed to strike a balance between reading and changing. It can achieve a square root of n time complexity for both insertions, deletions and reading with the input order by splitting a list into multiple increasingly long lists. Compared to order statistic tree or other data structure that can reach O(log n) of time, it is more simple and easy to understand and debug, which provides an instructional data structure that can be used when the data size is small.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Novel Simple Data Structure for Selecting, Inserting, and Deleting in Square Root Time

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Liu Hongyi,
  • Andre Mello Fortes

摘要

This paper presents a novel data structure designed to strike a balance between reading and changing. It can achieve a square root of n time complexity for both insertions, deletions and reading with the input order by splitting a list into multiple increasingly long lists. Compared to order statistic tree or other data structure that can reach O(log n) of time, it is more simple and easy to understand and debug, which provides an instructional data structure that can be used when the data size is small.