java - 列为 O(log(n))

Question

我必须制作一个符合特定条件的数据结构。

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

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

其次:数据结构必须实现java.util.List

我的问题是 O(log(n)) 和列表。有很多树可以做O(log(n))的操作(比如BST、Red-Black Tree、AVL Tree)，但是这些树怎么索引，怎么插入到哪里呢？

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

这些类中的大多数都有 O(1) 和 O(1) < O(log(n)) 的方法，但总有一种方法是 O(n) 的。例如，ArrayList 的删除时间为 O(n)。

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

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

Answer 1

安indexable skip list似乎符合要求:插入和删除是 O(log n)，update 的索引访问也是 O(log n)。