Summary：
- public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, java.io.Serializable
- 定义了一个内部类Entry<K,V>；该节点定义了这课红黑树的存储结构；
- 存储有该树的根节点；要删除这颗树只需要将root指向null即可；GC之后便会回收该红黑树，因为不可达
- 每次插入、删除一个树中节点时；都需要对这颗红黑树进行调整，使其结构没被破坏；
Fields：
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;//根节点
private transient int size = 0;
private transient int modCount = 0;//迭代器使用
Constructor：
public TreeMap() {
comparator = null;
}
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
size():
public int size() {
return size;
}
clear():
public void clear() {
modCount++;
size = 0;
root = null;
}
get():
public boolean containsKey(Object key) {
return getEntry(key) != null;
}
public V get(Object key) {
Entry<K,V> p = getEntry(key);
return (p==null ? null : p.value);
}
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
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);
if (cmp < 0)
p = p.left;
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;
}
put():
</pre><pre name="code" class="java">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) {
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;
}
//插入后的调整
/** 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);
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);
rotateLeft(parentOf(parentOf(x)));
}
}
}
root.color = BLACK;
}
remove():
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) {
modCount++;
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 has 2 children
// Start fixup at replacement node, if it exists.
//只有一个子节点和没有子节点的情况
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
if (replacement != null) {
// Link replacement to parent
//待删节点至少有一个子节点
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.left = p.right = p.parent = null;
// Fix replacement
//待删除节点是黑色
//进行调整！
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
//带删节点没有子节点，且其父节点为null；即当前待删节点为根节点
root = null;
} else { // No children. Use self as phantom replacement and unlink.
//待删节点没有子节点，但是父节点不为null
//待删节点颜色为黑
//进行调整！
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;
}
}
}
//删除后调整
private void fixAfterDeletion(Entry<K,V> x) {
while (x != root && colorOf(x) == BLACK) {
//当前节点非根、颜色为黑
if (x == leftOf(parentOf(x))) {
//x为父节点的左节点
Entry<K,V> sib = rightOf(parentOf(x));
if (colorOf(sib) == RED) {
//兄弟节点颜色为红
//兄弟变黑、父变红、以父节点为中心左旋
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
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));
sib = leftOf(parentOf(x));
}
if (colorOf(rightOf(sib)) == BLACK &&
colorOf(leftOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
if (colorOf(leftOf(sib)) == BLACK) {
setColor(rightOf(sib), BLACK);
setColor(sib, RED);
rotateLeft(sib);
sib = leftOf(parentOf(x));
}
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(leftOf(sib), BLACK);
rotateRight(parentOf(x));
x = root;
}
}
}
setColor(x, BLACK);
}
结构调整用到的一些方法：
//红黑树修正树结构所需要的基本操作：
//fixAfterDeletion()、fixAfterInsertion()两个方法会使用下面的这些方法
private static final boolean RED = false;
private static final boolean BLACK = true;
private static <K,V> boolean colorOf(Entry<K,V> p) {
return (p == null ? BLACK : p.color);
}
private static <K,V> void setColor(Entry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
private static <K,V> Entry<K,V> parentOf(Entry<K,V> p) {
return (p == null ? null: p.parent);
}
private static <K,V> Entry<K,V> leftOf(Entry<K,V> p) {
return (p == null) ? null: p.left;
}
private static <K,V> Entry<K,V> rightOf(Entry<K,V> p) {
return (p == null) ? null: p.right;
}
/** From CLR */
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;
}
}
/** From CLR */
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;
}
}
内部类
//树的存储结构
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;
/**
* Make a new cell with given key, value, and parent, and with
* {@code null} child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
/**
* Returns the key.
*
* @return the key
*/
public K getKey() {
return key;
}
/**
* Returns the value associated with the key.
*
* @return the value associated with the key
*/
public V getValue() {
return value;
}
/**
* Replaces the value currently associated with the key with the given
* value.
*
* @return the value associated with the key before this method was
* called
*/
public V setValue(V value) {
V oldValue = this.value;
this.value = value;
return oldValue;
}
public boolean equals(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
}
public int hashCode() {
int keyHash = (key==null ? 0 : key.hashCode());
int valueHash = (value==null ? 0 : value.hashCode());
return keyHash ^ valueHash;
}
public String toString() {
return key + "=" + value;
}
}
补充知识-红黑树：
- 概念：红黑树是一种比平衡二叉树条件稍微宽松的二叉树（主要的一个限制就是最长路径长度不大于最短路径长度的两倍），之所以放宽这样的条件的好处在于，它能够在删除插入查找之间取得一种好的折中（时间基本在logn左右）；平衡二叉树在插入删除的时候耗费的时间会比较多；
- 使用场景：所以建议就是，如果一棵树查找的次数远大于插入删除的次数选择平衡二叉树，反之使用红黑树，所以现在大多数开发者选用红黑树；以下是参考资料：http://m.blog.csdn.net/article/details?id=7939671
- 定义：
- 每个节点要么红，要么黑
- 每个叶节点是黑（此处叶节点对应普通树尾端的空节点）
- 根节点是黑
- 如果一个节点是红色的，那么其两个孩子则必须为黑色的；
- 对于任意节点而言其到叶节点的每条路径都包含相同数目的黑色结点
- 插入一个结点需要进行的修正有：（注意插入的结点必然是红色的，这是规定）
- 如其父结点为空，则将该结点颜色设成黑色即可；（违反性质3）
- 如果其父结点为黑色，则直接插入；不违反任何性质
- 如果其父结点为红色（祖父必然为黑色）（思想是：将红色的节点移到根节点；然后，将根节点设为黑色）（以下假设当前结点的父结点是祖父结点的左结点，如果为右结点则左右关键字互换即可）
- 叔父结点（祖父结点的另一个结点）为红色：
- 父结点和叔父结点颜色变成黑色，祖父结点变成红色
- 同时当前结点变成祖父结点，以该祖父结点为参数进行一次修正；
- 叔父结点为黑色，且当前结点是其父结点的右孩子：
- 以当前结点的父结点为新的当前结点，以新的当前节点（原修正点的父节点）为支点左旋；
- 同时以新的当前节点（原修正点的父节点）为参数进行一次修正；
- 叔父结点为黑色，且当前结点是其父结点的左孩子：
- 当前结点的父结点变成黑色，祖父结点变成红色，以祖父节点为支点右旋；
- 同时当前结点变成祖父结点，以该祖父结点为参数进行一次修正；
- 最后将根节点设为黑色，则完成修正；
- 叔父结点（祖父结点的另一个结点）为红色：
- reference：http://www.csdn123.com/html/itweb/20130813/57700_57702_57699.htm
- 删除一个结点需要进行的修正有：
- 首先，将T当作一颗二叉树，将节点删除；然后，通过RB-DELETE-FIXUP来对节点重新着色并旋转，以此来保证删除节点后的树仍然是一颗红黑树。
- 二叉树删除：
- 第一种，被删除节点没有儿子，即为叶节点。那么，直接将该节点删除就OK了。
- 第二种，被删除节点只有一个儿子。那么，直接删除该节点，并用该节点的唯一子节点顶替它的位置。
- 第三种，被删除节点有两个儿子。那么，首先把“它的后继节点的内容”复制给“该节点的内容”；之后，删除“它的后继节点”。
- 这里有两点需要说明：第一步中复制时，仅仅复制内容，即将“它的后继节点的内容”复制给“该节点的内容”。 这相当于用“该节点的后继节点”取代“该节点”，之后就删除“该节点的后继节点”即可，而不需要删除“该节点”(因为“该节点”已经被“它的后继节点”所取代)。
- 第二步中删除“该节点的后继节点”时，需要注意：“该节点的后继节点”不可能是双子非空，这个根据二叉树的特性可知。 既然“该节点的后继节点”不可能双子都非空，就意味着“该节点的后继节点”要么没有儿子，要么只有一个儿子。若没有儿子，则按“第一种”种的办法进行处理；若只有一个儿子，则按“第二种”中的办法进行处理。
- 修正的思想是：（思想是：将x所包含的额外的黑色不断沿树上移(向根方向移动)
- 具体内容参考上面网址