- 浏览: 654958 次
- 性别:
- 来自: 深圳
博客专栏
-
Hadoop学习
浏览量:250057
文章分类
最新评论
-
leibnitz:
请问,你知道在FSEdigLog#loadFSEdits()时 ...
Hadoop学习二十三:Hadoop-Hdfs FSDirectory 源码 -
jiaqing_blog:
七.等待队列(本是Object里的方法,但影响了线程)noti ...
多线程总结二:线程的状态转换 -
haaarySun:
虽然是三年前的帖子,但还是想回复博主,logger是继承了ca ...
Java日志学习三:Apache Log4j源码浅析 -
annmi_cai:
好好学习,天天向上!
Hadoop学习四:Hadoop-Hdfs NameNode -
emotionText:
楼主你好!我运行报错SLF4J: Class path con ...
Hadoop学习三十:Win7 Eclipse调试Centos Hadoop2.2-Mapreduce
一.TreeMap成员变量
//Comparator比较器接口,接口里面只有两个方法int compare(T o1, T o2);boolean equals(Object obj); private final Comparator<? super K> comparator; //根节点 private transient Entry<K,V> root = null; private transient int size = 0; private transient int modCount = 0;
二.TreeMap的Entry对象
static final class Entry<K,V> implements Map.Entry<K,V> { //构成树的三个属性left,left,parent K key; V value; Entry<K,V> left = null; Entry<K,V> right = null; Entry<K,V> parent; boolean color = BLACK; //该节点红色还是黑色 }
三.构造函数
//默认构造函数时comparator为空,则插入到TreeMap里面的key必须实现Comparator接口 public TreeMap() { comparator = null; } //用户指定Comparator public TreeMap(Comparator<? super K> comparator) { this.comparator = comparator; }
四.取数据
public V get(Object key) { Entry<K,V> p = getEntry(key); return (p==null ? null : p.value); } final Entry<K,V> getEntry(Object key) { //如果用户指定了Comparable,用指定的 if (comparator != null) return getEntryUsingComparator(key); //get操作key不能为空 if (key == null) throw new NullPointerException(); //如果用户没指定Comparable,用key作为Comparable Comparable<? super K> k = (Comparable<? super K>) key; Entry<K,V> p = root; //以根节点当前节点开始遍历搜索 while (p != null) { //拿被检索的节点的值和当前节点的值比较 int cmp = k.compareTo(p.key); //如果被检索的节点的值更小,则以当前节点的左子节点作为新的当前节点。 if (cmp < 0) p = p.left; //如果被检索的节点的值更大,则以当前节点的右子节点作为新的当前节点。 else if (cmp > 0) p = p.right; //被检索的节点的值和当前节点的值相等,则是我们需要的节点 else return p; } //找不到返回null return null; } //和上面逻辑一样 final Entry<K,V> getEntryUsingComparator(Object key) { K k = (K) key; Comparator<? super K> cpr = comparator; if (cpr != null) { Entry<K,V> p = root; while (p != null) { int cmp = cpr.compare(k, p.key); if (cmp < 0) p = p.left; else if (cmp > 0) p = p.right; else return p; } } return null; }
五.存数据
//返回被新节点覆盖的节点的值,不存在被覆盖的节点返回null public V put(K key, V value) { Entry<K,V> t = root; if (t == null) { // TBD: // 5045147: (coll) Adding null to an empty TreeSet should // throw NullPointerException // // compare(key, key); // type check //第一次插入节点 root = new Entry<K,V>(key, value, null); size = 1; modCount++; return null; } int cmp; Entry<K,V> parent; // split comparator and comparable paths Comparator<? super K> cpr = comparator; //用指定的Comparator if (cpr != null) { //以根节点当前节点t开始搜索,拿被添加的节点的值和当前节点的值比较。 do { //刚开始parent=t parent = t; cmp = cpr.compare(key, t.key); //如果被添加的节点的值更小,则以当前节点的左子节点作为新的当前节点,此时t=pL if (cmp < 0) t = t.left; //如果被添加的节点的值更大,则以当前节点的右子节点作为新的当前节点,此时t=pR else if (cmp > 0) t = t.right; //如果相等,直接覆盖 else return t.setValue(value); } while (t != null); //直到新的当前节点为空 } else { //put操作key不能为空 if (key == null) throw new NullPointerException(); //用key作为Comparator,下同 Comparable<? super K> k = (Comparable<? super K>) key; do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left; else if (cmp > 0) t = t.right; else return t.setValue(value); } while (t != null); } //生成一个新节点,父亲为parent Entry<K,V> e = new Entry<K,V>(key, value, parent); //根据最后一次比较的cmp确定pL位置存放e还是pR存放e if (cmp < 0) parent.left = e; else parent.right = e; //修复红黑树 fixAfterInsertion(e); size++; modCount++; //插入一个新节点时返回null return null; }
六.删数据
public V remove(Object key) { //先找到节点,getEntry(key)key不能为空,所以remove方法key不能为空 Entry<K,V> p = getEntry(key); if (p == null) return null; //保留一个节点的值 V oldValue = p.value; //删除节点 deleteEntry(p); return oldValue; } private void deleteEntry(Entry<K,V> p) { modCount++; size--; //若被删除节点 p 的左、右子树均非空 if (p.left != null && p.right != null) { //得到p节点的中序后继s Entry<K,V> s = successor (p); //用s替代p p.key = s.key; p.value = s.value; p = s; } //如果p节点的左节点存在,replacement代表左节点,否则代表右节点 Entry<K,V> replacement = (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 节点是其父节点的右子节点 else p.parent.right = replacement; p.left = p.right = p.parent = null; // Fix replacement if (p.color == BLACK) // 修复红黑树 fixAfterDeletion(replacement); // 如果 p 节点没有父节点 } else if (p.parent == null) { // return if we are the only node. root = null; } else { // No children. Use self as phantom replacement and unlink. 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) p.parent.right = null; p.parent = null; } } }
七.containsKey containsValue方法
public boolean containsKey(Object key) { return getEntry(key) != null; } //按中序遍历节点的顺序,把节点和指定value比较 public boolean containsValue(Object value) { for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e)) if (valEquals(value, e.value)) return true; return false; } static final class Entry<K,V> implements Map.Entry<K,V> { //找到最小的节点 final Entry<K,V> getFirstEntry() { Entry<K,V> p = root; if (p != null) while (p.left != null) p = p.left; return p; } //找到最大的节点 final Entry<K,V> getLastEntry() { Entry<K,V> p = root; if (p != null) while (p.right != null) p = p.right; return p; } } //找到指定节点的后继节点 static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; //如果t有右子数 else if (t.right != null) { Entry<K,V> p = t.right; //tRL不为空,tRL就是t的直接后继;tRLL不为空,tRLL就是t的直接后继...... while (p.left != null) p = p.left; return p; //如果t只有左子数 } else { //如果t=pL,直接返回p //如果t=pR,返回p.parent Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } //找到指定节点的前驱节点 static <K,V> Entry<K,V> predecessor(Entry<K,V> t) { if (t == null) return null; //如果t有左子数 else if (t.left != null) { Entry<K,V> p = t.left; //tLR不为空,tLR就是t的直接后继;tLRR不为空,tLRR就是t的直接后继...... while (p.right != null) p = p.right; return p; } else { //如果t=pR,直接返回p //如果t=pL,返回p.parent Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.left) { ch = p; p = p.parent; } return p; } }
八.fixAfterInsertion方法
// 插入节点后修复红黑树 private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; // 直到 x 节点的父节点不是根,且 x 的父节点不是红色 while (x != null && x != root && x.parent.color == RED) { // 如果 x 的父节点是其父节点的左子节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 获取 x 的父节点的兄弟节点 Entry<K,V> y = rightOf(parentOf(parentOf(x))); // 如果 x 的父节点的兄弟节点是红色 if (colorOf(y) == RED) { // 将 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 将 x 的父节点的兄弟节点设为黑色 setColor(y, BLACK); // 将 x 的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } // 如果 x 的父节点的兄弟节点是黑色 else { // 如果 x 是其父节点的右子节点 if (x == rightOf(parentOf(x))) { // 将 x 的父节点设为 x x = parentOf(x); rotateLeft(x); } // 把 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 把 x 的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } // 如果 x 的父节点是其父节点的右子节点 else { // 获取 x 的父节点的兄弟节点 Entry<K,V> y = leftOf(parentOf(parentOf(x))); // 如果 x 的父节点的兄弟节点是红色 if (colorOf(y) == RED) { // 将 x 的父节点设为黑色。 setColor(parentOf(x), BLACK); // 将 x 的父节点的兄弟节点设为黑色 setColor(y, BLACK); // 将 x 的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); // 将 x 设为 x 的父节点的节点 x = parentOf(parentOf(x)); } // 如果 x 的父节点的兄弟节点是黑色 else { // 如果 x 是其父节点的左子节点 if (x == leftOf(parentOf(x))) { // 将 x 的父节点设为 x x = parentOf(x); rotateRight(x); } // 把 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 把 x 的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } // 将根节点设为黑色 root.color = BLACK; }
九.fixAfterDeletion方法
// 删除节点后修复红黑树 private void fixAfterDeletion(Entry<K,V> x) { // 直到 x 不是根节点,且 x 的颜色是黑色 while (x != root && colorOf(x) == BLACK) { // 如果 x 是其父节点的左子节点 if (x == leftOf(parentOf(x))) { // 获取 x 节点的兄弟节点 Entry<K,V> sib = rightOf(parentOf(x)); // 如果 sib 节点是红色 if (colorOf(sib) == RED) { // 将 sib 节点设为黑色 setColor(sib, BLACK); // 将 x 的父节点设为红色 setColor(parentOf(x), RED); rotateLeft(parentOf(x)); // 再次将 sib 设为 x 的父节点的右子节点 sib = rightOf(parentOf(x)); } // 如果 sib 的两个子节点都是黑色 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 将 sib 设为红色 setColor(sib, RED); // 让 x 等于 x 的父节点 x = parentOf(x); } else { // 如果 sib 的只有右子节点是黑色 if (colorOf(rightOf(sib)) == BLACK) { // 将 sib 的左子节点也设为黑色 setColor(leftOf(sib), BLACK); // 将 sib 设为红色 setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } // 设置 sib 的颜色与 x 的父节点的颜色相同 setColor(sib, colorOf(parentOf(x))); // 将 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 将 sib 的右子节点设为黑色 setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } // 如果 x 是其父节点的右子节点 else { // 获取 x 节点的兄弟节点 Entry<K,V> sib = leftOf(parentOf(x)); // 如果 sib 的颜色是红色 if (colorOf(sib) == RED) { // 将 sib 的颜色设为黑色 setColor(sib, BLACK); // 将 sib 的父节点设为红色 setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } // 如果 sib 的两个子节点都是黑色 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { // 将 sib 设为红色 setColor(sib, RED); // 让 x 等于 x 的父节点 x = parentOf(x); } else { // 如果 sib 只有左子节点是黑色 if (colorOf(leftOf(sib)) == BLACK) { // 将 sib 的右子节点也设为黑色 setColor(rightOf(sib), BLACK); // 将 sib 设为红色 setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } // 将 sib 的颜色设为与 x 的父节点颜色相同 setColor(sib, colorOf(parentOf(x))); // 将 x 的父节点设为黑色 setColor(parentOf(x), BLACK); // 将 sib 的左子节点设为黑色 setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); }
十.迭代
/** * Base class for TreeMap Iterators */ abstract class PrivateEntryIterator<T> implements Iterator<T> { Entry<K,V> next; Entry<K,V> lastReturned; int expectedModCount; PrivateEntryIterator(Entry<K,V> first) { expectedModCount = modCount; lastReturned = null; next = first; } //后继迭代 final Entry<K,V> nextEntry() { Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = successor(e); lastReturned = e; return e; } //前驱迭代 final Entry<K,V> prevEntry() { Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); next = predecessor(e); lastReturned = e; return e; } }
发表评论
-
容器学习十一:Queue & Stack
2012-10-19 13:31 1100一.Queue类图 整个Queue结构 ... -
容器学习十:Vector & ArrayList & LinkedList
2012-10-15 14:57 1188一.前言 以前对Vector这对象很陌生,用的少,对象 ... -
容器学习九:Comparable & Comparator
2012-10-15 11:26 1612一.前言 本系 ... -
容器学习八:LinkedList源码分析
2012-09-01 12:22 1195一.概述 LinkedList继 ... -
容器学习七:ArrayList源码分析
2012-08-31 17:00 1619一.成员变量 // 在Ab ... -
容器学习六:HashSet & LinkedHashSet & TreeSet源码分析
2012-08-30 22:38 1836一.概述 Set是通过Map来支持的,Set ... -
容器学习四:TreeMap源码分析-排序二叉树和红黑树
2012-08-30 14:55 1589一.排序二叉树 排序二叉树是一种特殊结构的二叉树, ... -
容器学习三:LinkedHashMap源码分析
2012-08-26 21:50 5891一.LinkedHashMap的存储结构 Link ... -
容器学习二:Hashtable源码分析
2012-08-25 13:43 1707一.前言 HashMap和Hashtable大部分算 ... -
容器学习一:HashMap源码分析
2012-08-24 16:09 2949一.HashMap的存储结构 二.HashMap ... -
容器学习
2012-08-24 15:17 1720一.博客传送门 容器学习一:HashMap源码 ...
相关推荐
Java TreeMap源码解析 Java TreeMap源码解析 Java TreeMap源码解析
TreeMap源码是基于数据结构中的红黑树进行设计并开发的。
TreeMap源码解读.java
var treemap = require ( 'treemap' ) ; treemap . hello ( "biojs" ) ; // "hello biojs" 文档 如何使用不同的 .json 文件创建新的树状图? 在 simple.js 中,用一个新的替换flare.json。 var app = require ( ...
继上篇文章介绍完了HashMap,这篇文章开始介绍Map系列另一个比较重要的类TreeMap。 大家也许能感觉到,网络上介绍HashMap的文章比较多,但是介绍TreeMap反而不那么多,这里面是有原因:一方面HashMap的使用场景比较...
matlab初步回归代码TreeMap-eQTL变体的精细映射的结构化方法 TreeMap在cis-eQTL中优先考虑推定的因果变异,从而说明了一个位点的多位点效应和遗传连锁。 它采用3层嵌套设计来删除无信息的变体,并逐步减少信息性变体...
资源来自pypi官网。 资源全名:treemap-1.01.tar.gz
Python TreeMap可视化方案数据源(因为不能粘贴链接额,具体实现实现代码,请看我博客专栏《机器学习》:))
主要介绍了java TreeMap源码解析详解的相关资料,需要的朋友可以参考下
通过分析java.util.TreeMap源码来对经典问题红黑树加强理解和理清思路。
JDK源码剖析之红黑树TreeMap,偶然看见,传上来分享一下
TreeMap按VALUE排序
###React 树状图基于 d3.js 的 Treemap 组件。 目前这只是一个想法,展示了如何基于 treemap(d3.js) 创建 react 组件(可以在客户端和服务器端使用)。
vue 2.x echarts treemap带示例数据及效果图,及在对话框里显示的处理方法
TreeMap自己的理解
JAVA中用TREEMAP做的,可以求学生的总分,总分的平均值,最大值最小值
视觉地图VIM-TREEMAP 是一个 vim 脚本,用于从字符分隔的输入文件创建树图。 输出可以是文本文件或带有嵌入 SVG 的 html 文件。 (切片和骰子) 有关更多详细信息,请阅读 vim 帮助文件:../doc/treemap.txt 版本 ...
ava基础 基础知识 面向对象基础 Java基本数据类型 string和包装类 ...Java集合详解6:TreeMap和红黑树 Java集合详解7:HashSet,TreeSet与LinkedHashSet Java集合详解8:Java集合类细节精讲 JavaWeb
(Treemap Squared确实支持深度的任意级别,但是可能需要在更高的深度级别上覆盖默认样式,以确保可读性) 作为第二个目标,它还提供了Squarified Treemap算法的干净的开源实现。 过去还有其他开放源代码实现,...
树状图 用于渲染 treeMap 的 Javascript