TreeMap
简介
TreeMap 底层的数据结构就是红黑树，和 HashMap 的红黑树结构一样。
不同的是，TreeMap 利用了红黑树左节点小，右节点大的性质，根据 key 进行排序，使每个元素能够插入到红黑树大小适当的位置，维护了 key 的大小关系，适用于 key 需要排序的场景。
数据结构
特性
- 每个节点都有颜色（红或黑）；
- 根节点必须是黑色的；
- 叶子节点（null节点）是黑的，即每个节点都有两个子节点（其中一个或者两个可能是null节点）；
- 相连节点不能都是红色（红色节点的父节点和子节点必须为黑色）；
- 任意节点到它所有的叶子节点的路径都含有相同的黑色节点的数量。
类图
源码
SortedMap<K,V>
SortedMap规定了元素可以按key的大小来遍历，它定义了一些返回部分map的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public interface SortedMap<K,V> extends Map<K,V> {
//比较器
Comparator<? super K> comparator();
//返回fromKey（包含）到toKey（不包含）之间的元素组成的子map
SortedMap<K,V> subMap(K fromKey, K toKey);
//返回小于toKey（不包含）的子map
SortedMap<K,V> headMap(K toKey);
//返回大于等于fromKey（包含）的子map
SortedMap<K,V> tailMap(K fromKey);
//最小的key
K firstKey();
//最大的key
K lastKey();
//key的集合
Set<K> keySet();
//value的集合
Collection<V> values();
//节点集合
Set<Map.Entry<K, V>> entrySet();
}
NavigableMap<K,V>
NavigableMap是对SortedMap的增强，定义了一些返回离目标key最近的元素的方法。
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
public interface NavigableMap<K,V> extends SortedMap<K,V> {
//小于给定key的最大节点
Map.Entry<K,V> lowerEntry(K key);
//小于给定key的最大key
K lowerKey(K key);
//小于等于给定key的最大节点
Map.Entry<K,V> floorEntry(K key);
//小于等于给定key的最达key
K floorKey(K key);
//大于等于给定key的最小节点
Map.Entry<K,V> ceilingEntry(K key);
//大于等于给定key的最小key
K ceilingKey(K key);
//大于给定key的最小节点
Map.Entry<K,V> higherEntry(K key);
//大于给定key的最小key
K higherKey(K key);
//最小节点
Map.Entry<K,V> firstEntry();
//最大节点
Map.Entry<K,V> lastEntry();
//弹出最小节点
Map.Entry<K,V> pollFirstEntry();
//弹出最大节点
Map.Entry<K,V> pollLastEntry();
//返回倒序的map
NavigableMap<K,V> descendingMap();
//返回有序key集合
NavigableSet<K> navigableKeySet();
//返回倒序key集合
NavigableSet<K> descendingKeySet();
//返回从fromKey到toKey的子map，是否包含起止元素可以自己决定
NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive);
//返回小于toKey的子map，是否包含toKey自己决定
NavigableMap<K,V> headMap(K toKey, boolean inclusive);
//返回大于fromKey的子map，是否包含fromKey自己决定
NavigableMap<K,V> tailMap(K fromKey, boolean inclusive);
//等价于subMap(fromKey, true, toKey, false)
SortedMap<K,V> subMap(K fromKey, K toKey);
//等价于headMap(toKey, false)
SortedMap<K,V> headMap(K toKey);
//等价于tailMap(fromKey, true)
SortedMap<K,V> tailMap(K fromKey);
}
属性
1
2
3
4
5
6
7
8
//比较器
private final Comparator<? super K> comparator;
//根节点
private transient Entry<K,V> root;
//元素个数
private transient int size = 0;
//修改次数
private transient int modCount = 0;
内部类
Entry<K,V>
1
2
3
4
5
6
7
8
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;
boolean color = BLACK;
}
构造方法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//无参构造方法，比较器为null
public TreeMap() {
comparator = null;
}
//指定比较器构造方法
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
//指定Map，构造方法，比较器为null
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
//指定SortedMap构造，使用SortedMap的比较器
public TreeMap(SortedMap<K, ? extends V> m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) {
} catch (ClassNotFoundException cannotHappen) {
}
}
获取
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
//根据key获取value
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
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);
//如果k比根节点小，左子树查找
if (cmp < 0)
p = p.left;
//如果k比根节点大，右子树查找
else if (cmp > 0)
p = p.right;
else//相等，找到节点
return p;
}
return null;
}
//使用指定的比较器寻找
final Entry<K,V> getEntryUsingComparator(Object key) {
@SuppressWarnings("unchecked")
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;
}
- 从root（根节点）遍历整个树；
- 如果待查找的key比当前遍历的key小，则在其左子树中查找；
- 如果待查找的key比当前遍历的key大，则在其右子树中查找；
- 如果待查找的key与当前遍历的key相等，则找到了该元素，直接返回；
红黑树左旋
过程：
- 将 y的左节点 设为 x的右节点，即将 β 设为 x的右节点；
- 将 x 设为 y的左节点的父节点，即将 β的父节点 设为 x；
- 将 x的父节点 设为 y的父节点；
- 如果 x的父节点为空节点，则将y设置为根节点；如果x是它父节点的左（右）节点，则将y设置为x父节点的左（右）节点；
- 将 x 设为 y的左节点；
- 将 x的父节点 设为 y；
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
//p节点即图中X节点 private void rotateLeft(Entry<K,V> p) { if (p != null) { //r节点即Y节点 Entry<K,V> r = p.right; //Y的左子节点(B节点)设置为X的右子节点 p.right = r.left; if (r.left != null) //将X作为Y的左子节点(B节点)的父节点 r.left.parent = p; //X的父节点设为Y的父节点 r.parent = p.parent; //如果X的父节点为null，X为根节点，左旋后Y为根节点 if (p.parent == null) root = r; //如果X是它的父节点的左子节点 else if (p.parent.left == p) //Y设置为X的父节点的左子节点 p.parent.left = r; else//Y设置为X的父节点的右子节点 p.parent.right = r; //X设为Y的左子节点 r.left = p; //Y设为X的父节点 p.parent = r; } }
红黑树右旋
过程：
- 将 x的右节点 设为 y的左节点，即 将 β 设为 y的左节点；
- 将 y 设为 x的右节点的父节点，即 将 β的父节点 设为 y；
- 将 y的父节点 设为 x的父节点；
- 如果 y的父节点是空节点，则将x设为根节点；如果y是它父节点的左（右）节点，则将x设为y的父节点的左（右）节点；
- 将 y 设为 x的右节点；
- 将 y的父节点 设为 x；
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
private void rotateRight(Entry<K,V> p) {
//p节点即为Y节点
if (p != null) {
//l节点即是X节点
Entry<K,V> l = p.left;
//X的右子节点（B节点）设置为Y的左子节点
p.left = l.right;
//X的右子节点(B节点)的父节点设置为Y
if (l.right != null) l.right.parent = p;
//Y的父节点设置为X的父节点
l.parent = p.parent;
//Y的父节点的为null，说明Y是根节点
if (p.parent == null)
//X根节点设为根节点
root = l;
//Y是右子节点，设置X为右子节点
else if (p.parent.right == p)
p.parent.right = l;
//设置X为左子节点
else p.parent.left = l;
//Y设为X的右子节点
l.right = p;
//X设为Y的父节点
p.parent = l;
}
}
添加
put(K key, V 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
56
57
58
59
60
61
62
63
64
65
66
public V put(K key, V value) {
Entry<K,V> t = root;
//根节点为空
if (t == null) {
//非空校验
compare(key, key); // type (and possibly null) check
//插入到根节点
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//比较器不为空
if (cpr != null) {
//使用的是comparator方式，key值可以为null，只要在comparator.compare()中允许即可
do {
parent = t;
//key与根节点比较
cmp = cpr.compare(key, t.key);
//小于根节点，左子树查找
if (cmp < 0)
t = t.left;
//大于根节点，右子树查找
else if (cmp > 0)
t = t.right;
else//如果等于0，说明插入的节点已经存在了，直接更换其value值并返回旧值
return t.setValue(value);
} while (t != null);
}
else {
//Comparable方式，key不能为null
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//如果等于0，说明插入的节点已经存在了，直接更换其value值并返回旧值
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;
}
插入平衡
红黑树插入节点都是红色，有下面几种处理方式：
- 插入的元素如果是根节点，则直接涂成黑色即可，不用平衡；
- 插入的元素的父节点如果为黑色，不需要平衡；
- 插入的元素的父节点如果为红色，则违背了特性4，需要平衡，平衡时又分成下面三种情况：
如果父节点是祖父节点的左节点 情况 | 策略 —|— 父节点为红色，叔叔节点也为红色 | 将父节点设为黑色；将叔叔节点设为黑色；将祖父节点设为红色；将祖父节点设为新的当前节点，进入下一次循环判断； 父节点为红色，叔叔节点为黑色，且当前节点是其父节点的右节点|将父节点作为新的当前节点；以新当节点为支点进行左旋，进入情况3）； 父节点为红色，叔叔节点为黑色，且当前节点是其父节点的左节点|将父节点设为黑色；将祖父节点设为红色；以祖父节点为支点进行右旋，进入下一次循环判断；
如果父节点是祖父节点的右节点，则正好与上面反过来 情况 | 策略 —|— 父节点为红色，叔叔节点也为红色|将父节点设为黑色；将叔叔节点设为黑色；将祖父节点设为红色；将祖父节点设为新的当前节点，进入下一次循环判断； 父节点为红色，叔叔节点为黑色，且当前节点是其父节点的左节点|将父节点作为新的当前节点；以新当节点为支点进行右旋； 父节点为红色，叔叔节点为黑色，且当前节点是其父节点的右节点|将父节点设为黑色；将祖父节点设为红色；以祖父节点为支点进行左旋，进入下一次循环判断；
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
* 插入再平衡
*（1）每个节点或者是黑色，或者是红色。
*（2）根节点是黑色。
*（3）每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！）
*（4）如果一个节点是红色的，则它的子节点必须是黑色的。
*（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
*/
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)))) {
//y是祖父节点的右节点，即叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
//情况1、如果叔叔节点为红色
//如果叔节点是红色
if (colorOf(y) == RED) {
//设置父节点为黑色
setColor(parentOf(x), BLACK);
//设置叔节点为黑色
setColor(y, BLACK);
//设置祖父节点为红色
setColor(parentOf(parentOf(x)), RED);
//设置祖父节点设为新的当前节点
x = parentOf(parentOf(x));
} else {
//叔节点为黑色
//情况2、如果当前节点是父节点的右节点
if (x == rightOf(parentOf(x))) {
//将父节点设为当前节点
x = parentOf(x);
//以新当前节点左旋
rotateLeft(x);
}
//情况3、如果当前节点为其父节点的左节点
//设置父节点黑色
setColor(parentOf(x), BLACK);
//设置祖父节点红色
setColor(parentOf(parentOf(x)), RED);
//祖父节点右旋
rotateRight(parentOf(parentOf(x)));
}
//如果父节点是祖父节点的右节点
} else {
//y是叔节点
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
//情况1、如果叔叔节点为红色
if (colorOf(y) == RED) {
//设置父节点黑色
setColor(parentOf(x), BLACK);
//设置叔节点黑色
setColor(y, BLACK);
//设置祖父节点红色
setColor(parentOf(parentOf(x)), RED);
//设置祖父节点为当前节点
x = parentOf(parentOf(x));
//如果叔节点是黑色
} else {
//情况2、如果当前节点为其父节点的左节点
if (x == leftOf(parentOf(x))) {
//父节点设为当前节点
x = parentOf(x);
//新节点右旋
rotateRight(x);
}
//情况3、如果当前节点为其父节点的右节点
//设置父节点黑色
setColor(parentOf(x), BLACK);
//设置祖父节点红色
setColor(parentOf(parentOf(x)), RED);
//祖父节点左旋
rotateLeft(parentOf(parentOf(x)));
}
}
}
//平衡完成后根节点为黑色
root.color = BLACK;
}
删除
删除规则：
- 如果删除的位置有两个叶子节点，则从其右子树中取最小的元素放到删除的位置，然后把删除位置移到替代元素的位置，进入下一步；
- 如果删除的位置只有一个叶子节点（有可能是经过第一步转换后的删除位置），则把那个叶子节点作为替代元素，放到删除的位置，然后把这个叶子节点删除；
- 如果删除的位置没有叶子节点，则直接把这个删除位置的元素删除即可；
- 针对红黑树，如果删除位置是黑色节点，还需要做再平衡;
- 如果有替代元素，则以替代元素作为当前节点进入再平衡;
- 如果没有替代元素，则以删除的位置的元素作为当前节点进入再平衡，平衡之后再删除这个节点;
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public V remove(Object 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) {
//修改次数加1
modCount++;
//元素个数减1
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
//如果当前节点既有左子节点，又有右子节点
if (p.left != null && p.right != null) {
//右子树中最小的节点
Entry<K,V> s = successor(p);
//用右子树中最小节点的值替换当前节点的值
p.key = s.key;
p.value = s.value;
//把右子树中最小节点设为当前节点
p = s;
//这种情况实际上并没有删除p节点，而是把p节点的值改了，实际删除的是p的后继节点
} // p has 2 children
// Start fixup at replacement node, if it exists.
// 如果原来的当前节点（p）有2个子节点，则当前节点已经变成原来p的右子树中的最小节点了，也就是说其没有左子节点了
// 到这一步，p肯定只有一个子节点了,如果当前节点有子节点，则用子节点替换当前节点
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
//把替换节点直接放到当前节点的位置上（相当于删除了p，并把替换节点移动过来了）
replacement.parent = p.parent;
if (p.parent == null)
root = replacement;
else if (p == p.parent.left)
p.parent.left = replacement;
else
p.parent.right = replacement;
// Null out links so they are OK to use by fixAfterDeletion.
//将p的各项属性都设为空
p.left = p.right = p.parent = null;
// Fix replacement
//如果p是黑节点，则需要再平衡
if (p.color == BLACK)
fixAfterDeletion(replacement);
} 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) {
if (p == p.parent.left)
p.parent.left = null;
else if (p == p.parent.right)
p.parent.right = null;
p.parent = null;
}
}
}
删除平衡
- 如果当前节点是根节点，则直接涂黑即可，不需要再平衡；
- 如果当前节点是红+黑节点，则直接涂黑即可，不需要平衡；
- 如果当前节点是黑+黑节点，则我们只要通过旋转把这个多出来的黑色不断的向上传递到一个红色节点即可，这又可能会出现以下四种情况：
假设当前节点为父节点的左子节点
| 情况 | 策略 |
|---|---|
| x是黑+黑节点，x的兄弟是红节点 | 将兄弟节点设为黑色；将父节点设为红色；以父节点为支点进行左旋；重新设置x的兄弟节点，进入下一步； |
| x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的两个子节点都是黑色 | 将兄弟节点设置为红色；将x的父节点作为新的当前节点，进入下一次循环； |
| x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的右子节点为黑色，左子节点为红色 | 将兄弟节点的左子节点设为黑色；将兄弟节点设为红色；以兄弟节点为支点进行右旋；重新设置x的兄弟节点，进入下一步； |
| x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的右子节点为红色，左子节点任意颜色 | 将兄弟节点的颜色设为父节点的颜色；将父节点设为黑色；将兄弟节点的右子节点设为黑色；以父节点为支点进行左旋；将root作为新的当前节点（退出循环）； |
假设当前节点为父节点的右子节点
| 情况 | 策略 |
|---|---|
| x是黑+黑节点，x的兄弟是红节点 | 将兄弟节点设为黑色；将父节点设为红色；以父节点为支点进行右旋；重新设置x的兄弟节点，进入下一步； |
| x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的两个子节点都是黑色 | 将兄弟节点设置为红色；将x的父节点作为新的当前节点，进入下一次循环； |
| x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的左子节点为黑色，右子节点为红色 | 将兄弟节点的右子节点设为黑色；将兄弟节点设为红色；以兄弟节点为支点进行左旋；重新设置x的兄弟节点，进入下一步； |
| x是黑+黑节点，x的兄弟是黑节点，且兄弟节点的左子节点为红色，右子节点任意颜色 | 将兄弟节点的颜色设为父节点的颜色；将父节点设为黑色；将兄弟节点的左子节点设为黑色；以父节点为支点进行右旋；将root作为新的当前节点（退出循环）； |
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/**
* 删除再平衡
*（1）每个节点或者是黑色，或者是红色。
*（2）根节点是黑色。
*（3）每个叶子节点（NIL）是黑色。（注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！）
*（4）如果一个节点是红色的，则它的子节点必须是黑色的。
*（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
*/
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) {
//设置树节点为黑色
setColor(sib, BLACK);
//设置父节点为红色
setColor(parentOf(x), RED);
//父节点左旋
rotateLeft(parentOf(x));
//重新设置x的兄弟节点
sib = rightOf(parentOf(x));
}
//如果兄弟节点的两个子节点都是黑色
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
//设置兄弟节点为红色
setColor(sib, RED);
//将x的父节点作为新的当前节点，进入下一次循环
x = parentOf(x);
} else {
//如果兄弟节点的右子节点为黑色
if (colorOf(rightOf(sib)) == BLACK) {
//设置兄弟节点的左子节点为黑色
setColor(leftOf(sib), BLACK);
//设置兄弟节点为红色
setColor(sib, RED);
//已兄弟节点右旋
rotateRight(sib);
//重新设置x的兄弟节点
sib = rightOf(parentOf(x));
}
//将兄弟节点的颜色设为父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//设置父节点黑色
setColor(parentOf(x), BLACK);
//设置兄弟节点的右子节点黑色
setColor(rightOf(sib), BLACK);
//父节点为支点进行左旋
rotateLeft(parentOf(x));
//将root作为新的当前节点
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));
//重新设置x的兄弟节点
sib = leftOf(parentOf(x));
}
//如果兄弟节点的两个子节点都是黑色
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
//设置兄弟节点红色
setColor(sib, RED);
//将x的父节点作为新的当前节点
x = parentOf(x);
} else {
//兄弟节点的左子节点是黑色
if (colorOf(leftOf(sib)) == BLACK) {
//设置兄弟节点的右子节点黑色
setColor(rightOf(sib), BLACK);
//设置兄弟节点红色
setColor(sib, RED);
//兄弟节点左旋
rotateLeft(sib);
//重新设置x的兄弟节点
sib = leftOf(parentOf(x));
}
//将兄弟节点的颜色设为父节点的颜色
setColor(sib, colorOf(parentOf(x)));
//设置父节点黑色
setColor(parentOf(x), BLACK);
//设置兄弟节点的左子节点黑色
setColor(leftOf(sib), BLACK);
//父节点右旋
rotateRight(parentOf(x));
//x设置根节点
x = root;
}
}
}
//设置x设置为黑色
setColor(x, BLACK);
}
总结
TreeMap的存储结构只有一颗红黑树；TreeMap中的元素是有序的，按key的顺序排列；TreeMap比HashMap要慢一些，因为HashMap前面还做了一层桶，寻找元素要快很多；TreeMap没有扩容的概念；TreeMap的遍历不是采用传统的递归式遍历；TreeMap可以按范围查找元素，查找最近的元素；
