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
| //小于给定的Key
public Map.Entry<K,V> lowerEntry(K key) {
return exportEntry(getLowerEntry(key));
}
final Entry<K,V> getLowerEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
//1. 如果节点 p 小于 key
if (cmp > 0) {
//1.1 节点 p 有右子树，则在右子树中搜索
if (p.right != null)
p = p.right;
//1.2 节点 p 没有右子树，找到目标
else
return p;
//2. 节点 p 大于等于 key
} else {
//2.1 节点 p 有左子树，则在左子树中继续搜索
if (p.left != null) {
p = p.left;
//2.2 节点 p 无左子树，找出 p 的前驱节点，并返回
//前驱节点要么不存在，要么就是小于 key 的最大节点
//因为从根节点一直遍历到 p，那么之前经过的所有节点都是大于等于 key 的
//且 p 没有左子树，即 p 是大于等于 key 的所有节点中最小的
//则 p 的前驱一定是查找的目标
} else {
//查找前驱节点
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
}
}
return null;
}
public K lowerKey(K key) {
return keyOrNull(getLowerEntry(key));
}
//小于等于
public Map.Entry<K,V> floorEntry(K key) {
return exportEntry(getFloorEntry(key));
}
//和 getLowerEntry 类似，相等时的处理不同
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
} |
