添加entry时,核心函数fixAfterInsertion源码如下:
具体图示请分别参照http://www.cnblogs.com/fornever/archive/2011/12/02/2270692.html 中的插入和删除情形。
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED;
while (x != null && x != root && x.parent.color == RED) {
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
//parent为red且parent的sibling为red,参照情形3
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//parent为red且parent的sibling为black,参照情形5
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
//parent为red且parent的sibling为black,参照情形4
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
//parent为red且parent的sibling为red,和情形3对称
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
//parent为red且parent的sibling为black,和情形5对称
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
删除entry时,
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
if (x == leftOf(parentOf(x))) {
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
//x为black且x的sibling为red,和情形1对称,x对应n
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
//sib为之前x的兄弟,当sib的两个子元素均为黑时,在上步条件满足时则和情形3对应;若不满足上面条件,则和情形2对应
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
//sib的左孩子为红,右孩子为黑,和情形5对应
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
//sib的右孩子为红,和情形4对应;且上面情况必须导致这种情形。
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
}
} else { // symmetric
//下面情形和上面是左右对称的。
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateRight(parentOf(x));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
分享到:
相关推荐
Java TreeMap源码解析 Java TreeMap源码解析 Java TreeMap源码解析
继上篇文章介绍完了HashMap,这篇文章开始介绍Map系列另一个比较重要的类TreeMap。 大家也许能感觉到,网络上介绍HashMap的文章比较多,但是介绍TreeMap反而不那么多,这里面是有原因:一方面HashMap的使用场景比较...
TreeMap源码是基于数据结构中的红黑树进行设计并开发的。
主要介绍了java TreeMap源码解析详解的相关资料,需要的朋友可以参考下
TreeMap源码解读.java
JDK源码剖析之红黑树TreeMap,偶然看见,传上来分享一下
今天小编就为大家分享一篇关于Java源码解析TreeMap简介,小编觉得内容挺不错的,现在分享给大家,具有很好的参考价值,需要的朋友一起跟随小编来看看吧
通过分析java.util.TreeMap源码来对经典问题红黑树加强理解和理清思路。
TreeMap按VALUE排序
vue 2.x echarts treemap带示例数据及效果图,及在对话框里显示的处理方法
java所有集合类底层源码解析汇总,包括ArrayList、HashMap、HashSet、LinkedList、TreeMap、HashSet、ConcurrentHashMap等集合框架的底层实现源码大白话解读。
TreeMap自己的理解
JAVA中用TREEMAP做的,可以求学生的总分,总分的平均值,最大值最小值
Treemap-4.1.2.zip tree map开发代码,可用于创建tree map
TreeMap例子GDP
在eclipse上用java实现统计一句话或一段话中单词出现的个数,并按照字母表顺序输出,并利用treemap实现
C#实现的树图和放射环算法,信息可视化领域
treemap treeset hashset hashmap 简要介绍
Map,HashMap,TreeMap的使用 很详细额,值得看看
本资源提供了List对对象中的属性和TreeMap, String>对键值排序,并针对100w条数据排序,对比List和TreeMap, String>排序的效率...个人认为排序效率对比可以相信,但也可能存在不科学之处,还请高手给与指点,多多包涵。