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

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

ID:34551048

大小:182.45 KB

页数:9页

时间:2019-03-07

treemap的实现就是红黑树数据结构_第1页
treemap的实现就是红黑树数据结构_第2页
treemap的实现就是红黑树数据结构_第3页
treemap的实现就是红黑树数据结构_第4页
treemap的实现就是红黑树数据结构_第5页
资源描述:

《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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。