TreeMap源代码
1：TreeMap是java中排序的Map,实现的原理是基于红黑树。
红黑树原理介绍的blog：
http://www.cnblogs.com/fanzhidongyzby/p/3187912.html
红黑树最难的其实就是：
1：插入的时候, 怎么修正树结构
2：删除的时候，怎么修正树结构
因为出现的类型比较多，判断的也比较多；但是原理都一样，保证高度不超过1，一般都是用旋转达到平衡
测试例子：
public void treeMapTest() {
Map<Object, Object> treeMap=new TreeMap<Object, Object>();
treeMap.put(10, 10);
treeMap.put(11, 11);
treeMap.put(9, 9);
treeMap.put(8, 8);
Iterator<Object> it=treeMap.keySet().iterator();
while(it.hasNext()) {
Object key=it.next();
System.out.println(treeMap.get(key));
}
}
TreeMap中保存树结构的类Entry<K,V>
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
* <tt>null</tt> child links, and BLACK color.
*/
Entry(K key, V value, Entry<K,V> parent) {
this.key = key;
this.value = value;
this.parent = parent;
}
}是链表的形式保存所有的节点，在来看看TreeMap的中的属性
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, java.io.Serializable
{
/**
*比较器，实现这个可以比较大小
*/
private final Comparator<? super K> comparator;
private transient Entry<K,V> root = null;
/**
* 树的节点数量
*/
private transient int size = 0;
}
TreeMap的插入过程，就是红黑树的插入过程，即是：
1：当然key，如果比root节点小，走左孩子，大走右孩子
public V put(K key, V value) {
Entry<K,V> t = root; //根节点
if (t == null) { //根节点为空，第一次put
root = new Entry<K,V>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
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 { //默认的KEY自然排序
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<K,V> e = new Entry<K,V>(key, value, parent); //生成一个节点
if (cmp < 0)
parent.left = e;
else
parent.right = e; //指向最新节点
fixAfterInsertion(e); //修正 树结构
size++;
modCount++;
return null;
}
2：插入后修正树的结构，TreeMap默认插入的都是红色的节点，因为插入黑色会破坏，路径上黑色的节点数
/** From CLR */
private void fixAfterInsertion(Entry<K,V> x) {
x.color = RED; //默认红色
// 插入的节点不为null和不是根节点，其父亲节点是红色，那么就会两个红节点想连，
//需要调整
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); // x的父节点设置为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 { // 叔节点是黑色或者为null
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; // 把根节点变黑
}
1：考虑llr，就是插入节点是左孩子，的父亲是左孩子，红色，插入点的叔叔不存在火为黑，就必须右旋
/** From CLR */
private void rotateRight(Entry<K,V> p) { //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) // p的父亲为null，p其实就是跟节点
root = l; // l变成根节点
else if (p.parent.right == p) //
p.parent.right = l;
else p.parent.left = l;
l.right = p; // p作为l的右孩子
p.parent = l; // p的父亲指向l
}
}2：lrR，插入节点是右孩子，父亲是左孩子， 先左旋转换成llr型，然后按照上面的右旋即可
/** From CLR */
private void rotateLeft(Entry<K,V> p) { // 插入节点父亲
if (p != null) {
Entry<K,V> r = p.right; // 插入节点
p.right = r.left; // 插入节点的做孩子付给父亲的右孩子 如图p.letf = x
if (r.left != null) // x为null
r.left.parent = p; //
r.parent = p.parent; // 插入节点的父亲指向g 即使图中的p的父亲
if (p.parent == null) // 根节点
root = r;
else if (p.parent.left == p) //
p.parent.left = r;
else
p.parent.right = r;
r.left = p; // r的左孩子为p 就是图中n-》p
p.parent = r; //指定p的父亲节点为插入节点
}
}上面都是父亲节点是左孩子的情况，下面来看修正父亲节点是右孩子的情况
} 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 { // 叔节点是黑色或者为null
if (x == leftOf(parentOf(x))) { // 插入节点是左孩子
x = parentOf(x);
rotateRight(x);
}
// 父亲和孩子都在右边
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateLeft(parentOf(parentOf(x)));
}
}
}图示：