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

Question

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

Answer 1

Basically I am looking for a data structure where the queries should happen in O(lg n) time

使用 TreeMap .它由 Red-Black tree 支持所以它的访问时间是O(logN)(我强调下面的引述)

public class TreeMap
extends AbstractMap implements
NavigableMap, Cloneable, Serializable

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.