algorithm - 排序列表的高效数据结构

Question

我想根据对象属性中的键以排序方式保存对象。稍后我将从最大键到最小键顺序访问这些对象。我也会做一些搜索任务。

我考虑使用 AVL 树或 RB 树。据我所知，它们在理论上几乎是等价的(两者都有 O(logn))。但在实践中，在我的情况下哪一个可能表现更好。考虑到我将主要执行插入和顺序访问 ds，是否有比这些更好的选择。

编辑:我要用java

Answer 1

对于它的值(value)，在 C# 中，SortedDictionary<K, V>被实现为红黑树，并且在 C++ 中的 STL 的许多实现中，std::map<K, T>被实现为红黑树。

此外，来自 Wikipedia在 AVL 与红黑树上:

The AVL tree is another structure supporting O(log n) search, insertion, and removal. It is more rigidly balanced than red-black trees, leading to slower insertion and removal but faster retrieval. This makes it attractive for data structures that may be built once and loaded without reconstruction, such as language dictionaries (or program dictionaries, such as the order codes of an assembler or interpreter).