4 TreeSet/TreeMap
TreeSet / TreeMap 是底层运用了红黑树的数据结构
对比 HashSet / HashMap
HashSet / HashMap 存取的时间复杂度为O(1),而 TreeSet / TreeMap 存取的时间复杂度为O(logn)所以在存取上并不占优。
HashSet / HashMap 内元素是无序的，而TreeSet / TreeMap 内部是有序的(可以是按自然顺序排列也可以自定义排序)。
TreeSet / TreeMap 还提供了类似lowerBound和upperBound这两个其他数据结构没有的方法
对于 TreeSet, 实现上述两个方法的方法为：
lowerBound
public E lower(E e) --> 返回set中严格小于给出元素的最大元素，如果没有满足条件的元素则返回null。
public E floor(E e) --> 返回set中不大于给出元素的最大元素，如果没有满足条件的元素则返回null。
upperBound
public E higher(E e) --> 返回set中严格大于给出元素的最小元素，如果没有满足条件的元素则返回null。
public E ceiling(E e) --> 返回set中不小于给出元素的最小元素，如果没有满足条件的元素则返回null。
对于 TreeMap, 实现上述两个方法的方法为：
lowerBound
public Map.Entry<K,V> lowerEntry(K key) --> 返回map中严格小于给出的key值的最大key对应的key-value对，如果没有满足条件的key则返回null。
public K lowerKey(K key) --> 返回map中严格小于给出的key值的最大key，如果没有满足条件的key则返回null。
public Map.Entry<K,V> floorEntry(K key) --> 返回map中不大于给出的key值的最大key对应的key-value对，如果没有满足条件的key则返回null。
public K floorKey(K key) --> 返回map中不大于给出的key值的最大key，如果没有满足条件的key则返回null。
upperBound
public Map.Entry<K,V> higherEntry(K key) --> 返回map中严格大于给出的key值的最小key对应的key-value对，如果没有满足条件的key则返回null。
public K higherKey(K key) --> 返回map中严格大于给出的key值的最小key，如果没有满足条件的key则返回null。
public Map.Entry<K,V> ceilingEntry(K key)--> 返回map中不小于给出的key值的最小key对应的key-value对，如果没有满足条件的key则返回null。
public K ceilingKey(K key) --> 返回map中不小于给出的key值的最小key，如果没有满足条件的key则返回null。
lowerBound 与 upperBound 均为二分查找(因此要求有序)，时间复杂度为O(logn).
对比 PriorityQueue(Heap)
PriorityQueue是基于Heap实现的，它可以保证队头元素是优先级最高的元素，但其余元素是不保证有序的。
方法时间复杂度对比：
添加元素 add() / offer()
TreeSet: O(logn)
PriorityQueue: O(logn)
删除元素 poll() / remove()
TreeSet: O(logn)
PriorityQueue: O(n)
查找 contains()
TreeSet: O(logn)
PriorityQueue: O(n)
取最小值 first() / peek()
TreeSet: O(logn)
PriorityQueue: O(1)
常见用法
比如滑动窗口需要保证有序，那么这时可以用到TreeSet,因为TreeSet是有序的，并且不需要每次移动窗口都重新排序，只需要插入和删除(O(logn))就可以了
Doc Intro
A Red-Black tree basedNavigableMapimplementation. 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,putandremoveoperations.
Note that this implementation is not synchronized
Methods
ceilingKey/floorKey -> include equal
lower/highrt -> strictly
Modifier and Type | Method and Description |
| |
| |
|
|
| |
|
|
|
|
|
|
| |
| |
| |
| |
| |
|
|
| |
| |
| |
| |
| |
| |
| |
| |
| |
|
|
|
|
|
Last updated