我必须制作具有一定条件的数据结构.
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))和列表.有很多树可以在O(log(n))中执行操作(例如BST,红黑树,AVL树),但是如何索引这些树,以及如何在任何位置插入?
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))
发布评论