Java中实现红黑树或AVL树

Question

Java中实现红黑树或AVL树

10

Java集合/Guava/Apache Commons库中是否有Red Black Tree/AVL Tree数据结构的实现？如果有，您能告诉我吗？基本上，我正在寻找一个时间复杂度为O(lg n)的数据结构来进行查询。还会对数据结构进行一些更新，但不会像查询那样频繁。

- Geek

一个好的散列表有什么问题吗？ - user395760

@delnan 是的，HashTable可以是其中一种选择。我更喜欢基于哈希的映射表，比如ConcurrentHashMap，但我仍然想知道这些常用库中是否有这两个平衡二叉搜索树数据结构中的任何一个。 - Geek

1

如果你只需要一个Map（或Set），那么选择HashMap，因为它更快（具有小因子的O(1)）。忘记HashTable，因为它已经过时了。如果你需要并发性，请使用ConcurrentHashMap。如果你需要排序，请选择TreeMap，不用担心它是红黑树、AVL树还是Splay-tree。如果你需要其他东西，请详细说明你的问题。 - maaartinus

我的意思是，Guava的TreeMultiset在内部使用AVL树... - Louis Wasserman

@LouisWasserman 感谢您提到 TreeMultiset。 - Geek

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Cratylus · Accepted Answer

基本上我正在寻找一种数据结构，其中查询应在O(lg n)时间内完成。

使用TreeMap。它由Red-Black tree支持，因此其访问时间为O(logN)（以下引用是我强调的）。

public class TreeMap
extends AbstractMap implements
NavigableMap, Cloneable, Serializable

基于红黑树的NavigableMap实现。该地图按其键的自然排序或在地图创建时提供的比较器排序，具体取决于使用哪个构造函数。

此实现提供了包含containsKey，get，put和remove操作的保证log(n)时间成本。