通过分析 JDK 源代码研究 TreeMap 红黑树算法实现

核心提示：TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，通过分析 JDK 源代码研究 TreeMap 红黑树算法实现，这样就可以保证当需要快速检索指定节点，TreeSet 和 TreeMap 的关系为了让大家了解 TreeMap 和 TreeSet 之间的关系，//根据该TreeSet创建一个Tree

TreeMap 的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。

TreeSet 和 TreeMap 的关系

为了让大家了解 TreeMap 和 TreeSet 之间的关系，下面先看 TreeSet 类的部分源代码：

　public　class　TreeSet<E>　extends　AbstractSet<E>　
　　implements　NavigableSet<E>,　Cloneable,　java.io.Serializable　
　{　
　　//　使用　NavigableMap　的　key　来保存　Set　集合的元素　
　　private　transient　NavigableMap<E,Object>　m;　
　　//　使用一个　PRESENT　作为　Map　集合的所有　value。　
　　private　static　final　Object　PRESENT　=　new　Object();　
　　//　包访问权限的构造器，以指定的　NavigableMap　对象创建　Set　集合　
　　TreeSet(NavigableMap<E,Object>　m)　
　　{　
　　　　this.m　=　m;　
　　}　
　　public　TreeSet()　　　　　　　　　　　　　　　　　　　//　①　
　　{　
　　　　//　以自然排序方式创建一个新的　TreeMap，　
　　　　//　根据该　TreeSet　创建一个　TreeSet，　
　　　　//　使用该　TreeMap　的　key　来保存　Set　集合的元素　
　　　　this(new　TreeMap<E,Object>());　
　　}　
　　public　TreeSet(Comparator<?　super　E>　comparator)　　　//　②　
　　{　
　　　　//　以定制排序方式创建一个新的　TreeMap，　
　　　　//　根据该　TreeSet　创建一个　TreeSet，　
　　　　//　使用该　TreeMap　的　key　来保存　Set　集合的元素　
　　　　this(new　TreeMap<E,Object>(comparator));　
　　}　
　　public　TreeSet(Collection<?　extends　E>　c)　
　　{　
　　　　//　调用①号构造器创建一个　TreeSet，底层以　TreeMap　保存集合元素　
　　　　this();　
　　　　//　向　TreeSet　中添加　Collection　集合　c　里的所有元素　
　　　　addAll(c);　
　　}　
　　public　TreeSet(SortedSet<E>　s)　
　　{　
　　　　//　调用②号构造器创建一个　TreeSet，底层以　TreeMap　保存集合元素　
　　　　this(s.comparator());　
　　　　//　向　TreeSet　中添加　SortedSet　集合　s　里的所有元素　
　　　　addAll(s);　
　　}　
　　//TreeSet　的其他方法都只是直接调用　TreeMap　的方法来提供实现　
　　...　
　　public　boolean　addAll(Collection<?　extends　E>　c)　
　　{　
　　　　if　(m.size()　==　0　&&　c.size()　>　0　&&　
　　　　　　c　instanceof　SortedSet　&&　
　　　　　　m　instanceof　TreeMap)　
　　　　{　
　　　　　　//　把　c　集合强制转换为　SortedSet　集合　
　　　　　　SortedSet<?　extends　E>　set　=　(SortedSet<?　extends　E>)　c;　
　　　　　　//　把　m　集合强制转换为　TreeMap　集合　
　　　　　　TreeMap<E,Object>　map　=　(TreeMap<E,　Object>)　m;　
　　　　　　Comparator<?　super　E>　cc　=　(Comparator<?　super　E>)　set.comparator();　
　　　　　　Comparator<?　super　E>　mc　=　map.comparator();　
　　　　　　//　如果　cc　和　mc　两个　Comparator　相等　
　　　　　　if　(cc　==　mc　||　(cc　!=　null　&&　cc.equals(mc)))　
　　　　　　{　
　　　　　　　　//　把　Collection　中所有元素添加成　TreeMap　集合的　key　
　　　　　　　　map.addAllForTreeSet(set,　PRESENT);　
　　　　　　　　return　true;　
　　　　　　}　
　　　　}　
　　　　//　直接调用父类的　addAll()　方法来实现　
　　　　return　super.addAll(c);　
　　}　
　　...　
　}