先看看这篇文章,了解一下红黑树。
http://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91
特别注意这一段:
因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量(O(log n))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次。
==================================
看一下帮助文件:
java_zh/java/util/TreeSet.html
public class TreeSet<E>
extends AbstractSet<E>
implements SortedSet<E>, Cloneable, Serializable
此类实现 Set 接口,该接口由 TreeMap 实例支持。此类保证排序后的 set 按照升序排列元素,根据使用的构造方法不同,可能会按照元素的自然顺序 进行排序(参见 Comparable),或按照在创建 set 时所提供的比较器进行排序。
此实现为基本操作(add、remove 和 contains)提供了可保证的 log(n) 时间开销。
==================================
java_zh/java/util/TreeMap.html
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, Cloneable, Serializable
SortedMap 接口的基于红黑树的实现。此类保证了映射按照升序顺序排列关键字,根据使用的构造方法不同,可能会按照键的类的自然顺序 进行排序(参见 Comparable),或者按照创建时所提供的比较器进行排序。
此实现为 containsKey、get、put 和 remove 操作提供了保证的 log(n) 时间开销。这些算法是 Cormen、Leiserson 和 Rivest 的《Introduction to Algorithms》中的算法的改编。
==================================
嗯,然后看一段 TreeMap 的源程序。
/** From CLR **/
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) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x);
rotateLeft(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
if (parentOf(parentOf(x)) != null)
rotateRight(parentOf(parentOf(x)));
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
x = parentOf(parentOf(x));
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x);
rotateRight(x);
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
if (parentOf(parentOf(x)) != null)
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
可以看到,在进行红黑属性恢复。
还有其它的一些函数也涉及到红黑属性恢复,可以自行查看。
分享到:
相关推荐
title: TreeSet 和 TreeMap 理论基础Java 根据红黑树这种平衡的二叉搜索树实现了 TreeSet 和 TreeMap 两种数据结构,如果
主要为大家详细介绍了java中treemap和treeset实现红黑树,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
structure 跳表 vs 红黑树,对比了两种数据结构的优劣 跳表(Skip List)是一种基于并行...这使得红黑树成为一种广泛应用于高性能数据结构的选择,比如在标准库中的集合类实现中,如 Java 中的 TreeSet 和 TreeMap。
数据结构java版 pdf ,书中有霍夫曼压缩、Dijkstra最小路径算法,平衡搜索树,八皇后问题,RSA加密算法、TreeSet、TreeMap、队列、优先队列、堆栈等算法
数据结构学习记录 线性结构 动态样本:动态样本->环形动态样本 ...红黑树:TreeMap和TreeSet内部使用了红黑树 B树:切实了解了什么是B树 特里 哈夫曼树 图形结构 学习完线性结构与树形结构完成再添加
用PHP写的红黑树,带测试用例, TreeSet https://blog.csdn.net/fareast_mzh/article/details/119495318 这篇博文的完整代码
AVL树(AVLTree)、红黑树(RebBlackTree) B树(B-Tree) 集合(TreeSet)、映射(TreeMap) 哈夫曼树 Trie 线性+树形数据结构 集合(HashSet) 映射(HashMap、LinkedHashMap) 二叉堆(BinaryHeap) 优先级队列...
ava基础 基础知识 面向对象基础 Java基本数据类型 string和包装类 ...Java集合详解6:TreeMap和红黑树 Java集合详解7:HashSet,TreeSet与LinkedHashSet Java集合详解8:Java集合类细节精讲 JavaWeb
高级数据结构及其实现12.1 自顶向下伸展树12.2 红黑树12.2.1 自底向上的插入12.2.2 自顶向下红黑树12.2.3 自顶向下的删除12.3 确定性跳跃表12.4 AA树12.5 treap树12.6 kd树12.7 配对堆小结练习参考文献索引
4.5.1 一个简单的想法(不能直接使用) 4.5.2 展开 4.6 树的遍历 4.7 b树 4.8 标准库中的集合与映射 4.8.1 关于set接口 4.8.2 关于map接口 4.8.3 treeset类和treemap类的实现 4.8.4 使用多个映射...
4.5.1 一个简单的想法(不能直接使用) 4.5.2 展开 4.6 树的遍历 4.7 b树 4.8 标准库中的集合与映射 4.8.1 关于set接口 4.8.2 关于map接口 4.8.3 treeset类和treemap类的实现 4.8.4 使用多个映射...
高级数据结构及其实现12.1 自顶向下伸展树12.2 红黑树12.2.1 自底向上的插入12.2.2 自顶向下红黑树12.2.3 自顶向下的删除12.3 确定性跳跃表12.4 AA树12.5 treap树12.6 kd树12.7 配对堆小结练习参考文献索引
高级数据结构及其实现12.1 自顶向下伸展树12.2 红黑树12.2.1 自底向上的插入12.2.2 自顶向下红黑树12.2.3 自顶向下的删除12.3 确定性跳跃表12.4 AA树12.5 treap树12.6 kd树12.7 配对堆小结练习
4.8.3 TreeSet类和TreeMap类的实现 4.8.4 使用多个映射的例 小结 练习 参考文献 第5章 散列 5.1 一般想法 5.2 散列函数 5.3 分离链接法 5.4 不用链表的散列表 5.4.1 线性探测法 5.4.2 平方探测法 5.4.3 双散列 5.5 ...
(1)二叉树:二分搜索树、AVL(自平衡)、红黑树(统计性能高,自平衡,最常用)。 (2)堆(优先队列)、线段树。 (3)多叉树:Trie、并查集。 3.抽象数据结构: 有序集合TreeSet,有序映射TreeMap,底层基于平衡树实现。 ...
3.1.3 TreeMap和TreeSet 3.2 Map和List 3.2.1 Map的values()方法 3.2.2 Map和List的关系 3.3 ArrayList和LinkedList 3.3.1 Vector和ArrayList的区别 3.3.2 ArrayList和LinkedList的实现差异 3.3.3 ...
25 3:ServicorTo 和 ServicorFrom 互换................................................................................................................25 2.3.3.1. 2.4.1. 如何确定垃圾 ......................
25 3:ServicorTo 和 ServicorFrom 互换................................................................................................................25 2.3.3.1. 2.4.1. 如何确定垃圾 ......................