C＃中的快速订单统计树或哪种DS更有效，SortedList提供相同的function？

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

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

谢谢

Answer 1

可索引的跳过列表具有O（log n）插入，删除和IndexOf 。 不幸的是，在C＃中实现跳过列表涉及一些权衡。

我没有构建可索引的跳过列表，但我确实讨论过在两篇不同文章中构建常规跳过列表：

• 跳过列表数据结构
• 更高内存效率的跳过列表

修改其中任何一个来进行索引都不应该非常困难。

Answer 2

我使用了一个很好的红黑树实现并实现了我自己的Order Statistic Tree 。 这是一个通用的DS。 因为它没有框架DS的所有通用属性，所以它对我的特定问题的工作速度提高了5倍。