TreeMap红黑树源码详解

尊重原创，转载请标明出处 http://blog.csdn.net/abcdef314159

Redis源码学习之字典:https://cloud.tencent.com/developer/article/1353754

在分析源代码之前，最好要标注出处，因为在Java中和Android中同一个类可能代码就会不一样，甚至在Android中不同版本之间代码也可能会有很大的差别，下面分析的是红黑树TreeMap，在sourcesandroid-25中。

红黑树的几个性质要先说一下，

1. 每个节点是红色或者黑色的。
2. 根节点是黑色的。
3. 每个叶节点的子节点是黑色的（叶子节点的子节点可以认为是null的）。
4. 如果一个节点是红色的，则它的左右子节点都必须是黑色的。
5. 对任意一个节点来说，从它到叶节点的所有路径必须包含相同数目的黑色节点。

TreeMap还有一个性质，就是他的左子树比他小，右子树比他大，这里的比较是按照key排序的。存放的时候如果key一样就把他替换了。

乍一看代码TreeMap有3000多行，其实他里面有很多内部类，有Values,EntrySet,KeySet,PrivateEntryIterator,EntryIterator,ValueIterator,KeyIterator,DescendingKeyIterator,

NavigableSubMap,AscendingSubMap,DescendingSubMap,SubMap,TreeMapEntry,TreeMapSpliterator,KeySpliterator,DescendingKeySpliterator,ValueSpliterator,

EntrySpliterator多达十几个内部类。其实很多都不需要了解，下面主要来看一下TreeMapEntry这个类，它主要是红黑树的节点

/**
* Node in the Tree. Doubles as a means to pass key-value pairs back to
* user (see Map.Entry).
*/
static final class TreeMapEntry<K,V> implements Map.Entry<K,V> {
K key;
V value;
TreeMapEntry<K,V> left = null;//左子树
TreeMapEntry<K,V> right = null;//右子树
TreeMapEntry<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.
*/
TreeMapEntry(K key, V value, TreeMapEntry<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;
}
}

既然是棵树，那么肯定就会有put方法以及remove方法，那么这里就从最简单的着手，先看一下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.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
*
* @return the previous value associated with {@code key}, or
* {@code null} if there was no mapping for {@code key}.
* (A {@code null} return can also indicate that the map
* previously associated {@code null} with {@code key}.)
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
//注释说的很明白，如果有相同的key，那么之前老的就会被代替，
public V put(K key, V value) {
TreeMapEntry<K,V> t = root;
if (t == null) {
// We could just call compare(key, key) for its side effect of checking the type and
// nullness of the input key. However, several applications seem to have written comparators
// that only expect to be called on elements that aren't equal to each other (after
// making assumptions about the domain of the map). Clearly, such comparators are bogus
// because get() would never work, but TreeSets are frequently used for sorting a set
// of distinct elements.
//
// As a temporary work around, we perform the null & instanceof checks by hand so that
// we can guarantee that elements are never compared against themselves.
//
// compare(key, key);
//
// **** THIS CHANGE WILL BE REVERTED IN A FUTURE ANDROID RELEASE ****
// key检查，如果comparator为null，那么key是不能为null的，并且key是实现Comparable接口的，因为TreeMaori是有序的，需要比较.
//如果comparator不为null，则需要验证，comparator是自己传进来的，根据key == null，comparator.compare(key, key)是否可执行，
//还是抛异常，这个是由你自己写的compare方法决定的。
if (comparator != null) {
if (key == null) {
comparator.compare(key, key);
}
} else {//如果没有传入comparator，则key不能为null，且必须实现Comparable接口
if (key == null) {
throw new NullPointerException("key == null");
} else if (!(key instanceof Comparable)) {
throw new ClassCastException(
"Cannot cast" + key.getClass().getName() + " to Comparable.");
}
}
//创建root，这个是在上面root为null的时候才走到这一步
root = new TreeMapEntry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
TreeMapEntry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
//comparator无论是等于null还是不等于null，原理都是基本差不多
if (cpr != null) {
do {//添加的时候如果原来有就替换，如果没有就不断的循环，这里注意TreeMap的左子树比他小，右子树比他大，这里比较的是key
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);
}
TreeMapEntry<K,V> e = new TreeMapEntry<>(key, value, parent);//创建一个节点
if (cmp < 0)//节点比他父节点小，放到左子树
parent.left = e;
else
parent.right = e;//节点比他父节点大，放到右子树
fixAfterInsertion(e);
//这里是关键，树的调整，因为上面创建节点的时候默认的是一棵黑色的数，而树原来是平衡的，加入节点之后导致数的不平衡，所以需要调节
size++;
modCount++;
return null;
}

put方法存放的时候，首先是会存放到叶子节点，然后在进行调整。上面有一个重量级的方法fixAfterInsertion还没有分析，在分析fixAfterInsertion方法之前来看一下其他的几个方法，

private static <K,V> boolean colorOf(TreeMapEntry<K,V> p) {
//获取树的颜色，如果为null，则为黑色，这一点要记住，待会下面分析的时候会用到
return (p == null ? BLACK : p.color);
}
//找父节点
private static <K,V> TreeMapEntry<K,V> parentOf(TreeMapEntry<K,V> p) {
return (p == null ? null: p.parent);
}
//设置节点颜色
private static <K,V> void setColor(TreeMapEntry<K,V> p, boolean c) {
if (p != null)
p.color = c;
}
//获取左子树
private static <K,V> TreeMapEntry<K,V> leftOf(TreeMapEntry<K,V> p) {
return (p == null) ? null: p.left;
}
//获取右子树
private static <K,V> TreeMapEntry<K,V> rightOf(TreeMapEntry<K,V> p) {
return (p == null) ? null: p.right;
}

下面再来看一下fixAfterInsertion方法

/** From CLR */
private void fixAfterInsertion(TreeMapEntry<K,V> x) {
//在红黑树里面，如果加入一个黑色节点，则导致所有经过这个节点的路径黑色节点数量增加1，
//这样就肯定破坏了红黑树中到所有叶节点经过的黑色节点数量一样的约定。所以，
//我们最简单的办法是先设置加入的节点是红色的。
x.color = RED;
//当前节点变为红色，如果他的父节点是红色则需要调整，因为父节点和子节点不能同时为红色，但可以同时为黑色，
//所以这里的循环条件是父节点必须为红色才需要调整。
while (x != null && x != root && x.parent.color == RED) {
//这里会分多钟情况讨论，
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {//如果父节点是爷爷节点的左节点
TreeMapEntry<K,V> y = rightOf(parentOf(parentOf(x)));//当前节点的叔叔节点，也就是他父节点的兄弟节点，这个也可能为null
if (colorOf(y) == RED) {
//因为添加的是红色，而父与子不能同时为红色，所以打破了平衡，需要先让父为黑色，然后再让爷爷为红色，因为爷爷节点为红色，所以
//子节点必须为黑色，所以把叔叔节点也调为黑色，继续往上调整，
//(1)如果当前节点的叔叔节点是红色，也就是说他的叔叔节点一定是存在的，因为如果为null,则colorOf会返回黑色。既然叔叔节点
//是红色，那么他的爷爷节点一定是黑色，否则就打破了红黑平衡，那么他的父节点也一定是红色，因为只有父节点为红色才执行while
//循环，这种情况下，无论x是父节点的左节点还是右节点都不需要在旋转，
setColor(parentOf(x), BLACK);//让x的父节点为黑色
setColor(y, BLACK);//叔叔节点也设为黑色
setColor(parentOf(parentOf(x)), RED);//当前节点的爷爷节点为红色
//把爷爷节点设置为红色之后，继续往上循环，即使执行到最上端也不用担心，因为在最后会把根节点设置为黑色的。
x = parentOf(parentOf(x));
} else {
//如果他的叔叔节点是黑色的，并且他的父节点是红色的，那么说明他的叔叔节点是null，因为如果叔叔节点是黑色的且不为空,
//那么违反了他的第5条性质所以这里叔叔节点是空。因为叔叔节点
//为空，出现了不平衡,所以这里当前节点无论是父节点的左节点还是右节点，都需要旋转
if (x == rightOf(parentOf(x))) {
//(2)当前节点是父节点的右节点，
x = parentOf(x);//让当前节点的父节点为当前节点
rotateLeft(x);//对父节点进行左旋
}
//(3)当前节点是父节点的左节点，这个左节点有可能是添加的时候添加到左节点的，也有可能是上面旋转的时候旋转到左节点的
setColor(parentOf(x), BLACK);//让父节点为黑色
setColor(parentOf(parentOf(x)), RED);//爷爷节点变为红色
rotateRight(parentOf(parentOf(x)));//对爷爷节点右旋
}
} else {//父节点为爷爷节点的右节点
TreeMapEntry<K,V> y = leftOf(parentOf(parentOf(x)));//找出叔叔节点
//如果叔叔节点是红色，那么说明他一定是存在的，所以不需要旋转，这里要铭记，无论是左旋还是右旋的前提条件是他的叔叔节点不存在，
//如果存在就不需要旋转，只需要遍历改变颜色值即可
if (colorOf(y) == RED) {
//(4)修改颜色
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);//(5)右旋操作
}
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));//(6)左旋操作
}
}
}
root.color = BLACK;//根节点必须是黑色
}