列为 O(log(n)) [英] List as O(log(n))

问题描述

我必须制作具有特定条件的数据结构.

I have to make a data structure with certain conditions.

首先这4个函数必须是O(log(n)):

First these 4 functions must be in O(log(n)):

insert(Object o)  
insert(int index, Object o)  
delete(int index)  
update(int index, Object o) 

第二:数据结构必须实现java.util.List

Second: The data structure must implement java.util.List

我的问题是 O(log(n)) 和 List.有很多树可以做O(log(n))中的操作(比如BST、Red-Black Tree、AVL Tree)，但是这些树怎么索引，怎么插入到任何地方呢?

My issue is with the O(log(n)) and the List. There are a lot of trees that can do the operation in O(log(n)) (like BST, Red-Black Tree, AVL Tree), but how can these trees be indexed and how can the insert be anywhere?

将其设置为仅列表确实会带来问题.java.util.List 有这些实现类:AbstractList、AbstractSequentialList、ArrayList、LinkedList、Stack、Vector

Setting this up as only a list does bring up issues. java.util.List has these implementing classes: AbstractList, AbstractSequentialList, ArrayList, LinkedList, Stack, Vector

这些类中的大多数都有 O(1) 和 O(1) <的方法.O(log(n))，但总有一个方法是 O(n).示例 ArrayList 删除了 O(n).

Most of these classes have methods of O(1) and O(1) < O(log(n)), but there is always a method that is O(n). Example the ArrayList has a remove of O(n).

有没有人对这个问题有任何建议或方法?

Does anyone have any advise or approaches to this problem?

基本上，我正在寻找一种能够满足这些要求的数据结构.

Basically, I am looking for a data structure that I'll fulfill those requirements.

推荐答案

可索引的跳过列表 似乎符合要求:插入和删除操作是 O(log n)，update 的索引访问也 O(log n).

An indexable skip list seems to fit the bill: inserts and deletes are O(log n), and index access for update is also O(log n).

这篇关于列为 O(log(n))的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！