TreeSet仅对TreeMap做了一层包装，实现相同。TreeSet里面有一个TreeMap（适配器模式）。
TreeMap和TreeSet根据对象的 compareTo 方法判断对象是否是同一个对象，若自定义了排序 Comparator，以自定义为准，顺序相同的只能存在一个。
1 TreeMap
1.1 总体介绍
TreeMap实现了SortedMap接口，有序。非同步。
底层通过红黑树实现，也就意味着containsKey(), get(), put(), remove()都有着log(n)的时间复杂度。
1.2 红黑树
红黑树是一种近似平衡的二叉查找树，它能够确保任何一个节点的左右子树的高度差不会超过二者中较低那个的一倍。满足如下条件：
- 每个节点要么是红色，要么是黑色。
- 根节点必须是黑色
- 红色节点不能连续（也即是，红色节点的孩子和父亲都不能是红色）。
- 对于每个节点，从该点至
null（树尾端）的任何路径，都含有相同个数的黑色节点。
在树的结构发生改变时（插入或者删除操作），往往会破坏上述条件3或条件4，需要通过调整使得查找树重新满足红黑树的约束条件。
//内部类Entry
static final class Entry<K,V> implements Map.Entry<K,V> {
K key;
V value;
Entry<K,V> left = null;
Entry<K,V> right = null;
Entry<K,V> parent;
boolean color = BLACK;
...
}
1）调整
调整可以分为两类：
- 颜色调整：改变某个节点的颜色
- 结构调整：改变检索树的结构关系
结构调整过程包含两个基本操作：左旋，右旋。
左旋
左旋的过程是将x的右子树绕x逆时针旋转，使得x的右子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
private void rotateLeft(Entry<K,V> p) {
if (p != null) {
Entry<K,V> r = p.right;
p.right = r.left;
if (r.left != null)
r.left.parent = p;
r.parent = p.parent;
if (p.parent == null)
root = r;
else if (p.parent.left == p)
p.parent.left = r;
else
p.parent.right = r;
r.left = p;
p.parent = r;
}
}
右旋
右旋的过程是将x的左子树绕x顺时针旋转，使得x的左子树成为x的父亲，同时修改相关节点的引用。旋转之后，二叉查找树的属性仍然满足。
private void rotateRight(Entry<K,V> p) {
if (p != null) {
Entry<K,V> l = p.left;
p.left = l.right;
if (l.right != null) l.right.parent = p;
l.parent = p.parent;
if (p.parent == null)
root = l;
else if (p.parent.right == p)
p.parent.right = l;
else p.parent.left = l;
l.right = p;
p.parent = l;
}
}
2）寻找节点后继
对于一棵二叉查找树，给定节点 t ，寻找后继节点（树中比大于t的最小的那个元素）：
- t 的右子树不空，则 t 的后继是其右子树中最小的那个元素。
- t 的右孩子为空，则 t 的后继是其第一个向左走的祖先。
后继节点在红黑树的删除操作中将会用到。
static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
if (t == null)
return null;
else if (t.right != null) {// 1. t的右子树不空，则t的后继是其右子树中最小的那个元素
Entry<K,V> p = t.right;
while (p.left != null)
p = p.left;
return p;
} else {// 2. t的右孩子为空，则t的后继是其第一个向左走的祖先
Entry<K,V> p = t.parent;
Entry<K,V> ch = t;
while (p != null && ch == p.right) {
ch = p;
p = p.parent;
}
return p;
}
}
1.2 方法剖析
1）get()
get(Object key)调用了getEntry(Object key)得到相应的entry，然后返回entry.value。
getEntry()根据key的顺序对二叉查找树进行查找，直到找到满足k.compareTo(p.key) == 0的entry。
final Entry<K,V> getEntry(Object key) {
......
if (key == null)//不允许key值为null
throw new NullPointerException();
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;
}
2）put()
put(K key, V value)首先查找map，如果已包含则直接返回；否则插入新的entry，如果插入之后破坏了红黑树的约束条件，还需要进行调整（旋转，改变某些节点的颜色）。
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;
}
//首先查找map，如果已包含则直接返回
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
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();
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
Entry<K,V> e = new Entry<>(key, value, parent);//创建并插入新的entry
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//如果插入之后破坏了红黑树的约束条件，则调整
fixAfterInsertion(e);//调整
size++;
modCount++;
return null;
}
插入调整
调整函数fixAfterInsertion()
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); // 情况1
setColor(y, BLACK); // 情况1
setColor(parentOf(parentOf(x)), RED); // 情况1
x = parentOf(parentOf(x)); // 情况1
} else {
if (x == rightOf(parentOf(x))) {
x = parentOf(x); // 情况2
rotateLeft(x); // 情况2
}
setColor(parentOf(x), BLACK); // 情况3
setColor(parentOf(parentOf(x)), RED); // 情况3
rotateRight(parentOf(parentOf(x))); // 情况3
}
} else {
Entry<K,V> y = leftOf(parentOf(parentOf(x)));
if (colorOf(y) == RED) {
setColor(parentOf(x), BLACK); // 情况4
setColor(y, BLACK); // 情况4
setColor(parentOf(parentOf(x)), RED); // 情况4
x = parentOf(parentOf(x)); // 情况4
} else {
if (x == leftOf(parentOf(x))) {
x = parentOf(x); // 情况5
rotateRight(x); // 情况5
}
setColor(parentOf(x), BLACK); // 情况6
setColor(parentOf(parentOf(x)), RED); // 情况6
rotateLeft(parentOf(parentOf(x))); // 情况6
}
}
}
root.color = BLACK;
}
3）remove()
remove(Object key)首先通过getEntry(Object key)找到对应的entry，然后调用deleteEntry(Entry<K,V> entry)删除。
deleteEntry()删除指定的entry并在红黑树的约束被破坏时进行调用fixAfterDeletion(Entry<K,V> x)调整。
普通二叉查找树的删除过程，可以简单分为两种情况：
- 删除点 p 的左右子树都为空，或者只有一棵子树非空。
直接将 p 删除（左右子树都为空时），或者用非空子树替代 p（只有一棵子树非空时） - 删除点 p 的左右子树都非空。
可以用 p 的后继 s（树中大于x的最小的那个元素）代替 p，然后使用情况 1 删除 s（此时 s 一定满足情况 1）。
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {// 2. 删除点p的左右子树都非空。
Entry<K,V> s = successor(p);// 后继
p.key = s.key;
p.value = s.value;
p = s;
}
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {// 1. 删除点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;
p.left = p.right = p.parent = null;
if (p.color == BLACK)
fixAfterDeletion(replacement);// 调整
} else if (p.parent == null) {
root = null;
} else { // 1. 删除点p的左右子树都为空
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;
}
}
}
删除调整
调整函数fixAfterDeletion()
只有删除点是BLACK的时候，才会触发调整函数，因为删除 RED 节点不会破坏红黑树的任何约束，而删除 BLACK 节点会破坏规则 4。
上述图解的总体思想是：将情况 1 首先转换成情况 2，或者转换成情况 3 和情况 4。
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); // 情况1
setColor(parentOf(x), RED); // 情况1
rotateLeft(parentOf(x)); // 情况1
sib = rightOf(parentOf(x)); // 情况1
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED); // 情况2
x = parentOf(x); // 情况2
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK); // 情况3
setColor(sib, RED); // 情况3
rotateRight(sib); // 情况3
sib = rightOf(parentOf(x)); // 情况3
}
setColor(sib, colorOf(parentOf(x))); // 情况4
setColor(parentOf(x), BLACK); // 情况4
setColor(rightOf(sib), BLACK); // 情况4
rotateLeft(parentOf(x)); // 情况4
x = root; // 情况4
}
} else { // 跟前四种情况对称
Entry<K,V> sib = leftOf(parentOf(x));
if (colorOf(sib) == RED) {
setColor(sib, BLACK); // 情况5
setColor(parentOf(x), RED); // 情况5
rotateRight(parentOf(x)); // 情况5
sib = leftOf(parentOf(x)); // 情况5
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED); // 情况6
x = parentOf(x); // 情况6
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK); // 情况7
setColor(sib, RED); // 情况7
rotateLeft(sib); // 情况7
sib = leftOf(parentOf(x)); // 情况7
}
setColor(sib, colorOf(parentOf(x))); // 情况8
setColor(parentOf(x), BLACK); // 情况8
setColor(leftOf(sib), BLACK); // 情况8
rotateRight(parentOf(x)); // 情况8
x = root; // 情况8
}
}
}
setColor(x, BLACK);
}
2 TreeSet
前面已经说过TreeSet是对TreeMap的简单包装，对TreeSet的函数调用都会转换成合适的TreeMap方法，因此TreeSet的实现非常简单。这里不再赘述。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
......
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
public TreeSet() {
this.m = new TreeMap<E,Object>();// TreeSet里面有一个TreeMap
}
......
public boolean add(E e) {
return m.put(e, PRESENT)==null;
}
......
}