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

public class TreeMap<K,V>   Set<Map.Entry<K,V>>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable

Methods

• ceilingKey/floorKey -> include equal

• lower/highrt -> strictly

Modifier and Type	Method and Description
Map.Entry<K,V>	ceilingEntry(Kkey)Returns a key-value mapping associated with the least key greater than or equal to the given key, ornullif there is no such key.
K	ceilingKey(Kkey)Returns the least key greater than or equal to the given key, ornullif there is no such key.
void	clear()Removes all of the mappings from this map.
Object	clone()Returns a shallow copy of thisTreeMapinstance.
Comparator<? superK>	comparator()Returns the comparator used to order the keys in this map, ornullif this map uses thenatural orderingof its keys.
boolean	containsKey(Objectkey)Returnstrueif this map contains a mapping for the specified key.
boolean	containsValue(Objectvalue)Returnstrueif this map maps one or more keys to the specified value.
NavigableSet<K>	descendingKeySet()Returns a reverse orderNavigableSetview of the keys contained in this map.
NavigableMap<K,V>	descendingMap()Returns a reverse order view of the mappings contained in this map.
Set<Map.Entry<K,V>>	entrySet()Returns aSetview of the mappings contained in this map.
Map.Entry<K,V>	firstEntry()Returns a key-value mapping associated with the least key in this map, ornullif the map is empty.
K	firstKey()Returns the first (lowest) key currently in this map.
Map.Entry<K,V>	floorEntry(Kkey)Returns a key-value mapping associated with the greatest key less than or equal to the given key, ornullif there is no such key.
K	floorKey(Kkey)Returns the greatest key less than or equal to the given key, ornullif there is no such key.
void	forEach(BiConsumer<? superK,? superV> action)Performs the given action for each entry in this map until all entries have been processed or the action throws an exception.
V	get(Objectkey)Returns the value to which the specified key is mapped, ornullif this map contains no mapping for the key.
SortedMap<K,V>	headMap(KtoKey)Returns a view of the portion of this map whose keys are strictly less thantoKey.
NavigableMap<K,V>	headMap(KtoKey, boolean inclusive)Returns a view of the portion of this map whose keys are less than (or equal to, ifinclusiveis true)toKey.
Map.Entry<K,V>	higherEntry(Kkey)Returns a key-value mapping associated with the least key strictly greater than the given key, ornullif there is no such key.
K	higherKey(Kkey)Returns the least key strictly greater than the given key, ornullif there is no such key.
Set<K>	keySet()Returns aSetview of the keys contained in this map.
Map.Entry<K,V>	lastEntry()Returns a key-value mapping associated with the greatest key in this map, ornullif the map is empty.
K	lastKey()Returns the last (highest) key currently in this map.
Map.Entry<K,V>	lowerEntry(Kkey)Returns a key-value mapping associated with the greatest key strictly less than the given key, ornullif there is no such key.
K	lowerKey(Kkey)Returns the greatest key strictly less than the given key, ornullif there is no such key.
NavigableSet<K>	navigableKeySet()Returns aNavigableSetview of the keys contained in this map.
Map.Entry<K,V>	pollFirstEntry()Removes and returns a key-value mapping associated with the least key in this map, ornullif the map is empty.
Map.Entry<K,V>	pollLastEntry()Removes and returns a key-value mapping associated with the greatest key in this map, ornullif the map is empty.
V	put(Kkey,Vvalue)Associates the specified value with the specified key in this map.
void	putAll(Map<? extendsK,? extendsV> map)Copies all of the mappings from the specified map to this map.
V	remove(Objectkey)Removes the mapping for this key from this TreeMap if present.
V	replace(Kkey,Vvalue)Replaces the entry for the specified key only if it is currently mapped to some value.
boolean	replace(Kkey,VoldValue,VnewValue)Replaces the entry for the specified key only if currently mapped to the specified value.
void	replaceAll(BiFunction<? superK,? superV,? extendsV> function)Replaces each entry's value with the result of invoking the given function on that entry until all entries have been processed or the function throws an exception.
int	size()Returns the number of key-value mappings in this map.
NavigableMap<K,V>	subMap(KfromKey, boolean fromInclusive,KtoKey, boolean toInclusive)Returns a view of the portion of this map whose keys range fromfromKeytotoKey.
SortedMap<K,V>	subMap(KfromKey,KtoKey)Returns a view of the portion of this map whose keys range fromfromKey, inclusive, totoKey, exclusive.
SortedMap<K,V>	tailMap(KfromKey)Returns a view of the portion of this map whose keys are greater than or equal tofromKey.
NavigableMap<K,V>	tailMap(KfromKey, boolean inclusive)Returns a view of the portion of this map whose keys are greater than (or equal to, ifinclusiveis true)fromKey.
Collection<V>	values()Returns aCollectionview of the values contained in this map.