[LeetCode] 数据结构 - TreeMap/TreeSe
2020-07-02 本文已影响0人
YoungJadeStone
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
