列为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))和列表.有很多树可以在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))的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！