java - Java中的红黑树或AVL树实现

Question

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

Answer 1

基本上我正在寻找一个查询应该在 O(lg n) 时间内发生的数据结构

使用TreeMap。它由红黑树支持，所以它的访问时间是O(logN)（我强调下面的引用）

公共类 TreeMap
扩展 AbstractMap 实现
NavigableMap、Cloneable、Serializable

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

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n)时间成本。