Java中的红黑树或AVL树实现

Question

Java collections/Guava/Apache Commons库中是否有Red Black Tree/AVL Tree data结构实现？如果是，你能把它们指给我吗。基本上，我正在寻找一种数据结构，其中查询应该在O（lg n）时间内发生。数据结构也会有一些更新，但不会像查询那样频繁。

Answer 1

基本上，我正在寻找一个数据结构，查询应该发生在O（lg n）时间

使用树映射。它有一个红黑树支持，所以它的访问时间是O(logN)（我强调下面的报价）

公共类树映射
扩展AbstractMap实现
NavigableMap、可克隆、可串行

基于红黑树的NavigableMap实现。地图已排序根据其键的自然顺序，或通过比较器在映射创建时提供，具体取决于使用的构造函数。

此实现为包含Key、get、put和remove操作。