4 TreeSet/TreeMap

TreeSet / TreeMap 是底层运用了的数据结构

对比 HashSet / HashMap

HashSet / HashMap 存取的时间复杂度为O(1),而 TreeSet / TreeMap 存取的时间复杂度为O(logn)所以在存取上并不占优。
HashSet / HashMap 内元素是无序的，而TreeSet / TreeMap 内部是有序的(可以是按自然顺序排列也可以自定义排序)。
TreeSet / TreeMap 还提供了类似和这两个其他数据结构没有的方法
- 对于 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

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

void

boolean

void

boolean

void

int

PreviousNext Greater Element II NextMy Calendar I

Last updated 6 years ago