2019-01-11
一、继承关系
继承AbstractMap 实现了NavigableMap方法（扩展的SortedMap接口）导航方法，
内部类Entry，红黑树节点
Entryleft;
Entryright;
Entryparent;
boolean color =BLACK;
3、构造器：
无参构造器：
可以不使用比较器，但是key对象必须实现Comparable接口
public TreeMap() { comparator =null;}
指定比较器构造器：指定比较器后对key的大小比较使用这个比较器进行比较
public TreeMap(Comparator<? super K> comparator) {
this.comparator = comparator;
}
map构造器，把map转为treeMap，这里map可以为有序的，也可以是无序
public TreeMap(Map<? extends K, ? extends V> m) {
comparator = null;
putAll(m);
}
有序map构造器：
public TreeMap(SortedMap m) {
comparator = m.comparator();
try {
buildFromSorted(m.size(), m.entrySet().iterator(),null,null);
}catch (java.io.IOException cannotHappen) {
}catch (ClassNotFoundException cannotHappen) {
}}
Map转treeMap的putAll方法：
public void putAll(Map<? extends K, ? extends V> map) {
int mapSize = map.size();
if (size==0 && mapSize!=0 && map instanceof SortedMap) {
直接获取sortMap的比较器
Comparator<?> c = ((SortedMap<?,?>)map).comparator();
if (c == comparator || (c != null && c.equals(comparator))) {
++modCount;
try {
//对map进行转换为红黑树，入参为map的size和迭代器 buildFromSorted(mapSize, map.entrySet().iterator(), null, null);
} catch (java.io.IOException cannotHappen) { } catch (ClassNotFoundException cannotHappen) { } return; } }//如果不是有序的map走put方法构建红黑树 super.putAll(map); }
private void buildFromSorted(int size, Iterator<?> it,
java.io.ObjectInputStream str,
V defaultVal)
throws java.io.IOException, ClassNotFoundException {
this.size = size;
//
root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
it, str, defaultVal);
}
//转换方法
private final Entry<K,V> buildFromSorted(int level, int lo, int hi,
int redLevel, //红色节点的层数
Iterator<?> it, //迭代器
java.io.ObjectInputStream str, //null
V defaultVal //null)
throws java.io.IOException, ClassNotFoundException {
/*
* Strategy: The root is the middlemost element. To get to it, we
* have to first recursively construct the entire left subtree,
* so as to grab all of its elements. We can then proceed with right
* subtree.
*
* The lo and hi arguments are the minimum and maximum
* indices to pull out of the iterator or stream for current subtree.
* They are not actually indexed, we just proceed sequentially,
* ensuring that items are extracted in corresponding order.
*/
if (hi < lo) return null;
//取中间值作为中间节点
int mid = (lo + hi) >>> 1;
Entry<K,V> left = null;
if (lo < mid)
//迭代构建左子树。()
left = buildFromSorted(level+1, lo, mid - 1, redLevel, it, str, defaultVal);
K key;
V value;
if (it != null) {
if (defaultVal==null) {
Map.Entry<?,?> entry = (Map.Entry<?,?>)it.next();
key = (K)entry.getKey();
value = (V)entry.getValue();
} else {
key = (K)it.next();
value = defaultVal;
}
} else { // use stream
key = (K) str.readObject();
value = (defaultVal != null ? defaultVal : (V) str.readObject());
}
Entry<K,V> middle = new Entry<>(key, value, null);
// color nodes in non-full bottommost level red
//涂色
if (level == redLevel)
middle.color = RED;
if (left != null) {
middle.left = left;
left.parent = middle;
}
//构建右子树
if (mid < hi) {
Entry<K,V> right = buildFromSorted(level+1, mid+1, hi, redLevel,
it, str, defaultVal);
middle.right = right;
right.parent = middle;
}
return middle;
}
//get方法根据平衡二叉树进行搜索，比根节点小的在左子树，比根节点大的在右子树
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")
//没有比较器使用Key对象的Comparable接口
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;
}
public V put(K key, V value) {
Entry<K,V> t = root;
如果是根节点
if (t == null) {
//检查一下是否有比较器或者key对象是否实现Comparable接口，如果key没有实现Comparable接口会直接报类型转换异常
compare(key, key); // type (and possibly null) check
//设置为根节点
root = new Entry<>(key, value, null);
//mapSize++
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
//如果不是根节点。遍历红黑树。还是有比较器走比较器没有就走Comparable接口，比当前节点小放左子树。大放右子树
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;
}
//涂色和再平衡算法
private void fixAfterInsertion(Entry<K,V> x) {
//当前节点涂色为红色
x.color = RED;
//情况1：如果父节点也是红色
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;
}
