TreeMap 红黑树算法实现.docx
《TreeMap 红黑树算法实现.docx》由会员分享,可在线阅读,更多相关《TreeMap 红黑树算法实现.docx(25页珍藏版)》请在三一办公上搜索。
1、通过分析JDK源代码研究TreeMap红黑树算法实现李刚,自由撰稿人简介:TreeMap 和 TreeSet 是 Java Collection Framework 的两个重要成员, 其中TreeMap是Map接口的常用实现类,而TreeSet是Set接口的常用实现 类。虽然HashMap和HashSet实现的接口规范不同,但TreeSet底层是通过 TreeMap来实现的,因此二者的实现方式完全一样。而TreeMap的实现就是红 黑树算法。发布日期:2010年5月25日级别:初级建议:1 (查看或添加评论)土土芝X彦平均分(共16个评分)TreeMap的实现就是红黑树数据结构,也就说是一棵自
2、平衡的排序二叉树,这样 就可以保证当需要快速检索指定节点。TreeSet 和 TreeMap 的关系为了让大家了解TreeMap和TreeSet之间的关系,下面先看TreeSet类的部 分源代码:public class TreeSet extends AbstractSetimplements NavigableSet, Cloneable, java.io.Serializable(/使用NavigableMap的key来保存Set集合的元素private transient NavigableMap m;/使用一个PRESENT作为Map集合的所有value。private static
3、 final Object PRESENT = new Object();/包访问权限的构造器,以指定的NavigableMap对象创建Set集合 TreeSet(NavigableMap m)(this.m = m;public TreeSet()/ (/根据该TreeSet创建一个TreeSet,/使用该TreeMap的key来保存Set集合的元素 this(new TreeMap();public TreeSet(Comparator comparator) / (/以定制排序方式创建一个新的TreeMap,/根据该TreeSet创建一个TreeSet,/使用该TreeMap的key来保
4、存Set集合的元素this(new TreeMap(comparator);public TreeSet(Collection c)(/调用号构造器创建一个TreeSet,底层以TreeMap保存集合元素 this();/向TreeSet中添加Collection集合c里的所有元素 addAll(c);public TreeSet(SortedSet s)(/调用号构造器创建一个TreeSet,底层以TreeMap保存集合元素 this(parator();/向TreeSet中添加SortedSet集合s里的所有元素addAll(s);/TreeSet的其他方法都只是直接调用TreeMap的方
5、法来提供实现.public boolean addAll(Collection c)(if (m.size() = 0 & c.size() 0 &c instanceof SortedSet &m instanceof TreeMap)(/把c集合强制转换为SortedSet集合SortedSet set = (SortedSet) c;/把m集合强制转换为TreeMap集合TreeMap map = (TreeMap) m;Comparator cc = (Comparator) parator();Comparator mc = parator();/如果cc和mc两个Comparato
6、r相等if (cc = mc | (cc != null & cc.equals(mc)(map.addAllForTreeSet(set, PRESENT); return true;/直接调用父类的addAll()方法来实现 return super.addAll(c);.从上面代码可以看出,TreeSet的号、号构造器的都是新建一个TreeMap 作为实际存储Set元素的容器,而另外2个构造器则分别依赖于号和 号构造器,由此可见,TreeSet底层实际使用的存储容器就是TreeMap。与HashSet完全类似的是,TreeSet里绝大部分方法都是直接调用TreeMap的 方法来实现的,这
7、一点读者可以自行参阅TreeSet的源代码,此处就不再给出 了。对于TreeMap而言,它采用一种被称为“红黑树”的排序二叉树来保存Map中 每个Entry 每个Entry都被当成“红黑树”的一个节点对待。例如对于如下程序而言:public class TreeMapTest(public static void main(String args)(TreeMap map =new TreeMap();map.put(ccc , 89.0);map.put(aaa , 80.0);map.put(zzz , 80.0);map.put(bbb , 89.0);System.out.printl
8、n(map);当程序执行map.put(ccc” , 89.0);时,系统将直接把ccc-89.0这个 Entry放入Map中,这个Entry就是该“红黑树”的根节点。接着程序执行 map.put(aaa” , 80.0);时,程序会将aaa-80.0作为新节点添加到已有的 红黑树中。以后每向TreeMap中放入一个key-value对,系统都需要将该Entry当成一 个新节点,添加成已有红黑树中,通过这种方式就可保证TreeMap中所有key 总是由小到大地排列。例如我们输出上面程序,将看到如下结果(所有key由 小到大地排列):aaa=80.0, bbb=89.0, ccc=89.0, z
9、zz=80.0)回页首TreeMap的添加节点红黑树红黑树是一种自平衡排序二叉树,树中每个节点的值,都大于或等于在它的左子 树中的所有节点的值,并且小于或等于在它的右子树中的所有节点的值,这确保 红黑树运行时可以快速地在树中查找和定位的所需节点。对于TreeMap而言,由于它底层采用一棵“红黑树”来保存集合中的Entry, 这意味这TreeMap添加元素、取出元素的性能都比HashMap低:当TreeMap添 加元素时,需要通过循环找到新增Entry的插入位置,因此比较耗性能;当从 TreeMap中取出元素时,需要通过循环才能找到合适的Entry,也比较耗性能。 但 TreeMap、TreeS
10、et 比 HashMap、HashSet 的优势在于:TreeMap 中的所有 Entry总是按key根据指定排序规则保持有序状态,TreeSet中所有元素总是 根据指定排序规则保持有序状态。为了理解TreeMap的底层实现,必须先介绍排序二叉树和红黑树这两种数据结 构。其中红黑树又是一种特殊的排序二叉树。排序二叉树是一种特殊结构的二叉树,可以非常方便地对树中所有节点进行排序 和检索。排序二叉树要么是一棵空二叉树,要么是具有下列性质的二叉树:若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值; 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值; 它的左、右子树也分别为排序
11、二叉树。图1显示了一棵排序二叉树:图1.排序二叉树对排序二叉树,若按中序遍历就可以得到由小到大的有序序列。如图1所示二 叉树,中序遍历得:2,3,4,8,9,9,10,13,15,18)创建排序二叉树的步骤,也就是不断地向排序二叉树添加节点的过程,向排序二 叉树添加节点的步骤如下:1. 以根节点当前节点开始搜索。2. 拿新节点的值和当前节点的值比较。3. 如果新节点的值更大,则以当前节点的右子节点作为新的当前节点;如果 新节点的值更小,则以当前节点的左子节点作为新的当前节点。4. 重复2、3两个步骤,直到搜索到合适的叶子节点为止。5. 将新节点添加为第4步找到的叶子节点的子节点;如果新节点更大
12、,则 添加为右子节点;否则添加为左子节点。掌握上面理论之后,下面我们来分析TreeMap添加节点(TreeMap中使用Entry 内部类代表节点)的实现,TreeMap集合的put(K key, V value)方法实现了 将Entry放入排序二叉树中,下面是该方法的源代码:public V put(K key, V value)(/先以t保存链表的root节点Entry t = root;/如果t=null,表明是一个空链表,即该TreeMap里没有任何Entryif (t = null)(/将新的key-value创建一个Entry,并将该Entry作为rootroot = new Ent
13、ry(key, value, null);/设置该Map集合的size为1,代表包含一个Entrysize = 1;/记录修改次数为1modCount+;return null;int cmp;Entry parent;Comparator cpr = comparator;/如果比较器cpr不为null,即表明采用定制排序if (cpr != null)(do (/使用parent上次循环后的t所引用的Entryparent = t;/拿新插入key和t的key进行比较cmp = pare(key, t.key);/如果新插入的key小于t的key,t等于t的左边节点if (cmp 0)t
14、= t.right;/如果两个key相等,新的value覆盖原有的value,/并返回原有的valueelsereturn t.setValue(value); while (t != null);else(if (key = null)throw new NullPointerException();Comparable k = (Comparable) key;do (/使用parent上次循环后的t所引用的Entry parent = t;/拿新插入key和t的key进行比较cmp = pareTo(t.key);/如果新插入的key小于t的key, t等于t的左边节点if (cmp 0
15、)t = t.right;/如果两个key相等,新的value覆盖原有的value,/并返回原有的valueelsereturn t.setValue(value); while (t != null);/将新插入的节点作为parent节点的子节点Entry e = new Entry(key, value, parent);/如果新插入key小于parent的key,则e作为parent的左子节点if (cmp 0)parent.left = e;/如果新插入key小于parent的key,则e作为parent的右子节点 elseparent.right = e;/修复红黑树fixAfter
16、Insertion(e);/ size+;modCount+;return null;上面程序中粗体字代码就是实现“排序二叉树”的关键算法,每当程序希望添加 新节点时:系统总是从树的根节点开始比较一一即将根节点当成当前节点,如 果新增节点大于当前节点、并且当前节点的右子节点存在,则以右子节点作为当 前节点;如果新增节点小于当前节点、并且当前节点的左子节点存在,则以左子 节点作为当前节点;如果新增节点等于当前节点,则用新增节点覆盖当前节点, 并结束循环一一直到找到某个节点的左、右子节点不存在,将新节点添加该节 点的子节点 如果新节点比该节点大,则添加为右子节点;如果新节点比该 节点小,则添加为左
17、子节点。回页首TreeMap的删除节点当程序从排序二叉树中删除一个节点之后,为了让它依然保持为排序二叉树,程 序必须对该排序二叉树进行维护。维护可分为如下几种情况:(1)被删除的节点是叶子节点,则只需将它从其父节点中删除即可。(2)被删除节点p只有左子树,将p的左子树pL添加成p的父节点的左子 树即可;被删除节点p只有右子树,将p的右子树pR添加成p的父节点的 右子树即可。(3)若被删除节点p的左、右子树均非空,有两种做法:将pL设为p的父节点q的左或右子节点(取决于p是其父节点q的 左、右子节点),将pR设为p节点的中序前趋节点s的右子节点(s是 pL最右下的节点,也就是pL子树中最大的节点
18、)。以p节点的中序前趋或后继替代p所指节点,然后再从原排序二叉树中 删去中序前趋或后继节点即可。(也就是用大于p的最小节点或小于p 的最大节点代替p节点即可)。图2显示了被删除节点只有左子树的示意图:图2.被删除节点只有左子树图3显示了被删除节点只有右子树的示意图:图3.被删除节点只有右子树图4显示了被删除节点既有左子节点,又有右子节点的情形,此时我们米用到 是第一种方式进行维护:图4.被删除节点既有左子树,又有右子树图5显示了被删除节点既有左子树,又有右子树的情形,此时我们采用到是第 二种方式进行维护:图5.被删除节点既有左子树,又有右子树TreeMap删除节点采用图5所示右边的情形进行维护
19、一一也就是用被删除节点 的右子树中最小节点与被删节点交换的方式进行维护。TreeMap删除节点的方法由如下方法实现:private void deleteEntry(Entry p)(modCount+;size-;/如果被删除节点的左子树、右子树都不为空if (p.left != null & p.right != null)(/用p节点的中序后继节点代替p节点Entry s = successor (p);p.key = s.key;p.value = s.value;p = s;/如果p节点的左节点存在,replacement代表左节点;否则代表右节点。Entry replacement
20、 = (p.left != null ? p.left : p.right);if (replacement != null)(replacement.parent = p.parent;/如果p没有父节点,则replacemment变成父节点if (p.parent = null)root = replacement;/如果p节点是其父节点的左子节点else if (p = p.parent.left)p.parent.left = replacement;/如果p节点是其父节点的右子节点 elsep.parent.right = replacement;p.left = p.right =
21、 p.parent = null;/修复红黑树if (p.color = BLACK)fixAfterDeletion(replacement); / /如果p节点没有父节点else if (p.parent = null)(root = null;else(if (p.color = BLACK)/修复红黑树fixAfterDeletion(p);/ if (p.parent != null) (/如果p是其父节点的左子节点if (p = p.parent.left)p.parent.left = null;/如果p是其父节点的右子节点else if (p = p.parent.right)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- TreeMap 红黑树算法实现 红黑树 算法 实现
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-4925497.html