java提高篇之treemap-编程开发技术

《java提高篇之treemap-编程开发技术》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Java提高篇ZTrccMap-编程开发技术Java提高篇之TreeMap原文出处：chenssyTreeMap的实现是红黑树算法的实现，所以要了解TreeMap就必须对红黑树冇一定的了解，其实这篇博文的名字叫做：根据红黑树的算法來分析TreeMap的实现,但是为了与Java捉高篇系列博文保持一致述是叫做TreeMap比较好。通过这篇I■専文你可以获得如下知识点：1、红黑树的基木概念。2、红黑树壇加节点、删除节点的实现过程。3、红黑树左旋转、右旋转的复杂过程。4、Java+TreeMap是如何通过put、deleteEntry两个来实现红黑树增加、删除节点的。我

2、想通过这篇博文你对TreeMap-定有了更深的认识。好了，下面先简单普及红黑树知识。一、红黑树简介红黑树乂称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。我们知道一颗基本的二叉树他们都需要满足一个基本性质-即树中的任何节点的值大于它的左了节点，且小于它的右了节点。按照这个基本性质使得树的检索效率大大捉高。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒(只有右/左子树)，这样势必会导致二叉树的检索效率大大降低(0(n)),所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，女n：AVL,SBT,

3、伸展树，TREAP?,红黑树等等。平衡二叉树必须具备如卜•特性：它是一棵空树或它的左右两个了树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：1、每个节点都只能是红色或者黑色2、根节点是黑色3、每个叶节点(NIL节点，空节点)是黑色的。4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。5、从任一节点到其每

4、个叶子的所有路径都包含相同数目的黑色节点。这些约朿强制了红黑树的关键性质：从根到叶了的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率0(log?/7)o下图为一颗典型的红黑二叉树。对于红黑二叉树而言它主要包括三大基木操作：左旋、右旋、着色。99999999999999999999999999左旋？？？？？？？？？？？？？？？？？？？？？？？？？？？

5、？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？右旋(图片来自：http:/A™v.cnblogs・com/yangccnu/p/1ntroducc-Red-Black-Trcc.html)本节参考文献：http://baike.baidu.com/view/133754.htm?fr=aladdin百度百科注：由于本文主要是讲解Java屮TreeMap,所以并没冇对红黑树进行非常深入的了解和研究，如果诸位想对其进行更加深入的研究Lz提供儿篇较好的I■専文：1、红黑树系列集锦2.红黑树数据结构剖析3>红黑树二、TreeMap数据结

6、构»»»回归主角：TreeMap<<<<«TreeMap的定义如下：publicclassTreeMapextendsAbstractMapimplementsNavigablcMap,Cloncablc,java・io.SerializableTreeMapAbstractMap,Navigab1eMap>Cloneable>SerializableH个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合,Navigab1eMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索口标返

7、回最接近匹配项的导航方法。TreeMap中同时也包含了如卜•几个重要的屈性：//比较器，因为TreeMap是有序的，通过comparator接口我们可以对TreeMap的内部排序进行精密的控制privatefinalComparatorcomparator;//TreeMap红-黑节点，为TreeMap的内部类privatctransicntEntryroot=null;//容器大小privatetransientintsize二0;//TreeMap修改次数privatetransientintmodCount=0;//红黑树的节点

8、颜色--红色privat