treemap的实现就是红黑树数据结构

《treemap的实现就是红黑树数据结构》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、TreeMap的实现就是红黑树数据结构，也就说是一棵自平衡的排序二叉树，这样就可以保证当需要快速检索指定节点。TreeSet和TreeMap的关系为了让大家了解TreeMap和TreeSet之间的关系，下面先看TreeSet类的部分源代码：publicclassTreeSetextendsAbstractSetimplementsNavigableSet,Cloneable,java.io.Serializable{//使用NavigableMap的key来保存Set集合的元素priva

2、tetransientNavigableMapm;//使用一个PRESENT作为Map集合的所有value。privatestaticfinalObjectPRESENT=newObject();//包访问权限的构造器，以指定的NavigableMap对象创建Set集合TreeSet(NavigableMapm){this.m=m;}publicTreeSet()//①{//以自然排序方式创建一个新的TreeMap，//根据该TreeSet创建一个TreeSet，/

3、/使用该TreeMap的key来保存Set集合的元素this(newTreeMap());}publicTreeSet(Comparatorcomparator)//②{//以定制排序方式创建一个新的TreeMap，//根据该TreeSet创建一个TreeSet，//使用该TreeMap的key来保存Set集合的元素this(newTreeMap(comparator));}publicTreeSet(Collectionc)

4、{//调用①号构造器创建一个TreeSet，底层以TreeMap保存集合元素this();//向TreeSet中添加Collection集合c里的所有元素addAll(c);}publicTreeSet(SortedSets){//调用②号构造器创建一个TreeSet，底层以TreeMap保存集合元素this(s.comparator());//向TreeSet中添加SortedSet集合s里的所有元素addAll(s);}//TreeSet的其他方法都只是直接调用TreeMap的方法来提供实现..

5、.publicbooleanaddAll(Collectionc){if(m.size()==0&&c.size()>0&&cinstanceofSortedSet&&minstanceofTreeMap){//把c集合强制转换为SortedSet集合SortedSetset=(SortedSet)c;//把m集合强制转换为TreeMap集合TreeMapmap=(TreeMap)m;Comparat

6、orcc=(Comparator)set.comparator();Comparatormc=map.comparator();//如果cc和mc两个Comparator相等if(cc==mc

7、

8、(cc!=null&&cc.equals(mc))){//把Collection中所有元素添加成TreeMap集合的keymap.addAllForTreeSet(set,PRESENT);returntrue;}}//直接调用父类的addAll()方法来实现

9、returnsuper.addAll(c);}...}从上面代码可以看出，TreeSet的①号、②号构造器的都是新建一个TreeMap作为实际存储Set元素的容器，而另外2个构造器则分别依赖于①号和②号构造器，由此可见，TreeSet底层实际使用的存储容器就是TreeMap。与HashSet完全类似的是，TreeSet里绝大部分方法都是直接调用TreeMap的方法来实现的，这一点读者可以自行参阅TreeSet的源代码，此处就不再给出了。对于TreeMap而言，它采用一种被称为“红黑树”的排序二叉树来保存M

10、ap中每个Entry——每个Entry都被当成“红黑树”的一个节点对待。例如对于如下程序而言：publicclassTreeMapTest{publicstaticvoidmain(String[]args){TreeMapmap=newTreeMap();map.put("ccc",89.0);map.put("aaa",80.0);map.put("zzz",80