1. 概述
A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest’s Introduction to Algorithms.
之前已经学习过HashMap和LinkedHashMap了,HashMap不保证数据有序,LinkedHashMap保证数据可以保持插入顺序,而如果我们希望Map可以保持key的大小顺序的时候,我们就需要利用TreeMap了。(可以用于顺序匹配,避免全量匹配)
1
2
3
4
5
6
7
8
9
10
11
12
|
TreeMap<Integer, String> tmap = new TreeMap<Integer, String>();
tmap.put( 1 , "语文" );
tmap.put( 3 , "英语" );
tmap.put( 2 , "数学" );
tmap.put( 4 , "政治" );
tmap.put( 5 , "历史" );
tmap.put( 6 , "地理" );
tmap.put( 7 , "生物" );
tmap.put( 8 , "化学" );
for (Entry<Integer, String> entry : tmap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
|
其大致的结构如下所示:
使用红黑树的好处是能够使得树具有不错的平衡性,这样操作的速度就可以达到log(n)的水平了。具体红黑树的实现不在这里赘述,可以参考数据结构之红黑树、wikipedia-红黑树等的实现。
2. put函数
Associates the specified value with the specified key in this map.If the map previously contained a mapping for the key, the old value is replaced.
如果存在的话,old value被替换;如果不存在的话,则新添一个节点,然后对做红黑树的平衡操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
public V put(K key, V value) {
Entry<K,V> t = root;
if (t == null ) {
compare(key, key);
root = new Entry<>(key, value, null );
size = 1 ;
modCount++;
return null ;
}
int cmp;
Entry<K,V> parent;
Comparator<? super K> cpr = comparator;
if (cpr != null ) {
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0 )
t = t.left;
else if (cmp > 0 )
t = t.right;
else
return t.setValue(value);
} while (t != null );
}
else {
if (key == null )
throw new NullPointerException();
@SuppressWarnings ( "unchecked" )
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 );
}
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0 )
parent.left = e;
else
parent.right = e;
fixAfterInsertion(e);
size++;
modCount++;
return null ;
}
|
3. get函数
get函数则相对来说比较简单,以log(n)的复杂度进行get
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
final Entry<K,V> getEntry(Object key) {
if (comparator != null )
return getEntryUsingComparator(key);
if (key == null )
throw new NullPointerException();
@SuppressWarnings ( "unchecked" )
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;
}
return null ;
}
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p== null ? null : p.value);
}
|
4. successor后继
TreeMap是如何保证其迭代输出是有序的呢?其实从宏观上来讲,就相当于树的中序遍历(LDR)。我们先看一下迭代输出的步骤
1
2
3
|
for (Entry<Integer, String> entry : tmap.entrySet()) {
System.out.println(entry.getKey() + ": " + entry.getValue());
}
|
根据The enhanced for statement,for语句会做如下转换为:
1
2
3
4
|
for (Iterator<Map.Entry<String, String>> it = tmap.entrySet().iterator() ; tmap.hasNext(); ) {
Entry<Integer, String> entry = it.next();
System.out.println(entry.getKey() + ": " + entry.getValue());
}
|
在it.next()的调用中会使用nextEntry调用successor
这个是过的后继的重点,具体实现如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null )
return null ;
else if (t.right != null ) {
Entry<K,V> p = t.right;
while (p.left != null )
p = p.left;
return p;
} else {
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
|
怎么理解这个successor呢?只要记住,这个是中序遍历就好了,L-D-R。具体细节如下:
a. 空节点,没有后继
b. 有右子树的节点,后继就是右子树的“最左节点”
c. 无右子树的节点,后继就是该节点所在左子树的第一个祖先节点
a.好理解,不过b, c,有点像绕口令啊,没关系,上图举个例子就懂了!
有右子树的节点,节点的下一个节点,肯定在右子树中,而右子树中“最左”的那个节点则是右子树中最小的一个,那么当然是右子树的“最左节点”,就好像下图所示:
无右子树的节点,先找到这个节点所在的左子树(右图),那么这个节点所在的左子树的父节点(绿色节点),就是下一个节点。
分享到:
相关推荐
Java高级数据结构算法知识
本文将深入探讨这两种算法的原理、实现方式以及它们在C#中的应用。 ### TreeMap算法 TreeMap是一种基于分层数据的可视化技术,它通过矩形的面积大小来表示数据的量级,矩形的层次结构则代表了数据的层级关系。这种...
总的来说,TreeMap源码的学习可以帮助我们理解红黑树的数据结构和其实现原理,这对于优化和调试涉及大量数据的操作至关重要。同时,掌握TreeMap的内部机制也能提升我们在实际开发中使用Java集合框架的能力。
TreeMap排序算法的实现原理是基于红黑树数据结构的,通过将键值对插入到红黑树中,并对树中的节点进行排序,以达到对键值对的排序目的。 在Java中,TreeMap排序算法的实现可以通过两种方式:一是使用TreeMap的自然...
Java中的`TreeMap`是一个基于红黑树(Red-Black Tree)数据结构的有序映射容器。它维护了键的自然顺序或者根据提供的比较器进行排序。...阅读"TreeMap in Java.pdf"文档将进一步深入理解其内部工作原理和高级用法。
在Java编程语言中,`TreeMap`是`java.util`包下的一种有序的键值对存储结构,它基于红黑树(Red-Black Tree)算法实现。...通过学习,你可以更好地理解`TreeMap`的工作原理,以及如何在实际项目中充分利用其优势。
TreeMap 的核心原理是分块算法,它将数据结构划分为多个矩形区域,每个区域代表一个数据节点。通过调整矩形的面积和位置,可以清晰地展示数据的层级关系和相对大小。矩形的面积越大,表示的数据量越大;矩形的嵌套...
TreeMap 排序的实现原理 TreeMap 使用红黑树数据结构来存储数据。红黑树是一种自平衡二叉树,它可以保证树的高度较小,从而提高查询和插入的效率。 在 TreeMap 中,每个节点都包含一个键值对,并且键值对是根据键...
`TreeMap`的工作原理基于红黑树数据结构,这是一种自平衡二叉查找树。这种数据结构保证了插入、删除和查找操作的时间复杂度为O(log n),使得`TreeMap`在保持有序性的同时,能够高效地处理大量数据。 1. **创建和...
这通常涉及到计数和频率统计,可以使用HashMap或TreeMap等数据结构存储特征与类别的频次信息。 4. 建立模型:将计算出的先验概率和条件概率存储在模型中,以便于后续预测使用。 5. 预测:对于新的数据点,计算其...
本文将深入探讨这三种数据结构的特点、工作原理以及适用场景。 1. **HashMap** `HashMap`是最常见的Map实现,它基于哈希表(散列表)原理,通过键(key)的哈希码来快速定位到对应的值(value)。哈希表提供平均O...
TreeSet是Set接口的实现,它内部依赖于TreeMap来实现。在TreeSet的构造函数中,我们可以看到它创建了一个内部的TreeMap实例,用于存储元素。每个添加到TreeSet的元素都会被当作键放入这个内部的TreeMap,而值则是一...
本篇文章将总结集合框架的基础知识,包括主要接口、实现类以及底层实现原理。 1. 集合框架接口 - **Collection接口**:作为所有集合类的父接口,提供了基本的操作方法,如add、remove等。 - **List接口**:继承自...
尽管我们通常不直接使用`TreeNode`,但了解它的存在可以帮助我们理解`TreeMap`和`TreeSet`的工作原理。 除了基本的实现,Java中还有`java.awt.Tree`和`javax.swing.JTree`,这两个类主要用于图形用户界面(GUI)中...
本文将深入探讨“du.js”的核心概念、工作原理以及如何在项目中应用。 TreeMap是一种数据可视化方法,特别适合展示层次结构数据,通过不同大小的矩形来代表数据的大小关系。在“du.js”中,它被用来表示磁盘上的...
3. Tree数据结构:TreeSet、TreeMap的内部实现,以及红黑树的工作原理。 三、多线程 1. 线程创建:通过Thread类和Runnable接口创建线程。 2. 同步机制:synchronized关键字的使用,以及wait()、notify()和notifyAll...
- **TreeSet**:基于TreeMap实现,元素按自然顺序排序。 #### 1.6 总结: 集合框架中常用类比较 - **ArrayList** vs. **LinkedList**:前者支持快速随机访问,后者适合频繁插入和删除。 - **HashSet** vs. **...
TreeSet 和 TreeMap 之间存在着紧密的关系,下面我们将详细讲解 TreeSet 的结构和实现。 TreeSet 的实现是基于 TreeMap 的,TreeSet 使用 NavigableMap 来保存 Set 集合的元素。TreeSet 的构造器可以指定 ...