[LeetCode] 数据结构 - TreeMap/TreeSe

TreeSet和TreeMap都是ordered存储结构。而TreeSet又基于TreeMap来实现。

TreeSet

A NavigableSet implementation based on a TreeMap. The elements are ordered using their natural ordering, or by a Comparator provided at set creation time, depending on which constructor is used. This implementation provides guaranteed log(n) time cost for the basic operations (add, remove, and contains).

TreeSet和TreeMap的关系类似于HashSet和HashMap之间的关系。HashSet底层依赖于HashMap实现，TreeSet底层则采用一个NavigableMap来保存TreeSet集合的元素。因为NavigableMap只是一个interface，因此底层依然是用TreeMap来包含Set集合中所有的元素。

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable {
  ...
}

时间复杂度

TreeMap和TreeSet在big O方面的时间复杂度是一样的：
新增 - O(logn)
查询 - O(logn)
删除 - O(logn)

reference

• https://www.cnblogs.com/aspirant/p/8902285.html
• https://yikun.github.io/2015/04/10/Java-TreeSet%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/