c# - 对数时间 C# 列表

Question

是否存在列表集合的 .NET 实现，使得插入和查找都是最坏情况下的 O(log(n)) 操作？默认 System.Collections.Generic.List ' Insert ' 方法是一个 O(n) 操作。

我所说的列表集合是指类似数组的可扩展数据结构。 “查找”是指按索引访问。

我怀疑这可以用平衡树来完成，但实现起来并不容易。

Answer 1

我不知道 .NET 实现，但可能适合您的数据结构是 Indexible Skiplist。它具有与平衡二叉树类似的 O(lg n) 性能，但在概念上更像链表。

http://en.wikipedia.org/wiki/Skip_list

我认为用 C# 编写一个不会太难。