C#或what-DS中的快速顺序统计树比提供相同功能的SortedList更高效

Question

我的C#代码中需要一个快速订单统计树。我所知道的唯一具有IndexOf（）方法并保持项目排序的数据结构是SortedList。不幸的是，它的插入复杂度是O（n），不像SortedDictionary是O（Lg n），但SortedDiction没有IndexOf（）。

我需要的方法只是Add（）和IndexOf

感谢

Answer 1

可索引跳过列表具有O（logn）插入、删除和IndexOf。不幸的是，在C#中实现跳过列表涉及到一些折衷。

我还没有建立一个可索引的跳过列表，但我在两篇不同的文章中讨论了建立一个常规跳过列表：

• 跳过列表数据结构
• 更节省内存的跳过列表

修改它们中的任何一个来进行索引应该都不太困难。

Answer 2

我使用了红黑树的一个很好的实现，并实现了我自己的订单统计树。它是一个通用DS。由于它不具备框架DS的所有通用属性，所以它在解决我的特定问题时速度快了5倍。