分析大纲：
- treemap中的实现原理
- treemap中的remove()(红黑树的删除实践)
- treemap中的put()
- treemap中的get()
treemap中的实现原理
1.treemap存储K-V键值使用红黑树的存储方式
- 红黑树结构天然支持排序，默认情况下通过key值自然顺序进行排序。
1. treemap的remove方法解释
public V remove(Object key) {
//获取当前的key值。
Entry<K,V> p = getEntry(key);
//如果p为空的话，之间返回空
if (p == null)
return null;
//保存要删除的值，后面做返回
V oldValue = p.value;
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
修改操作加一
modCount++;
集合的长度减一
size--;
如果当前节点的有右子树，又有左子树
if (p.left != null && p.right != null) {
//获取后置节点
Entry<K,V> s = successor(p);
//使用后置节点代替当前要删除的点，
p.key = s.key;
p.value = s.value;
//使删除点指向代替点s
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) {
//当前情况为删除点有右子树的情况，没有左子树，因为是找后继节点，不理解可以看我的红黑树原理，
//使用替换节点顶替当前的删除节点。
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;
// 如果被删除节点是黑色，替代节点为红黑，在fixAfterDeletion中把替代节点置为黑色，
//如果被删除节点为黑色，替代节点为黑色，进入fxAfterDeltetion中的循环，开始循环判断
if (p.color == BLACK)
//删除平衡方法
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
//如果仅有一个节点，直接结束
root = null;
} else { // No children. Use self as phantom replacement and unlink
// 当前情况删除节点没有子节点的情况，并且当前节点为黑色
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;
}
}
}
当前的remove方法有这样几种情况，如果删除节点有一个子节点的情况，如果当前节点为黑色，子节点为红黑，子节点直接替换当前节点，变色黑色，如果当前节点为黑色，子节点也为黑色，删除了p节点后，当前支树，少一个黑节点，进入平衡判断方法，进行平衡转换
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);
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);
}
代码逐句详解
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));
}
当前情况旋转后的情况
image.png
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
当sib的没有左节点，或者两个都为黑的情况，直接变换sib为红色，以p节点为当前节点继续循环，因为P的左子树本身缺少一个节点，现在右子树也缺少一个节点，刚好平衡，这样p节点就缺少了一个节点，以p为当前节点继续进行循环判断。如果p为红色，直接不进入循环，设置为黑色平衡，如果p为黑色继续进入循环平衡。
image.png
} else {
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
当进入当前else的话，说明sib最少有一个节点，如果有两个节点，则是一红，一黑的情况。如果右节点为黑色或者没有的话，右旋，变成以下情况
image.png
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK);
rotateLeft(parentOf(x));
x = root;
以上图的情况进行转换，sib与父类进行交换颜色，父类设置为黑色，sib的右节点设置为黑色，进行左旋，得到以下图，左边比右边多一个节点，刚好进来的时候x少一个节点平衡，推出循环。右边情况与左边刚好相反
image.png
2. treemap的put方法解析
public V put(K key, V value) {
Entry<K,V> t = root;
//如果t等于null，把当前节点作为红黑树的根节点。
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
//当根不等于空，判断是否自己定义排序规则
int cmp;
Entry<K,V> parent;
// cpr表示有无自己定义的排序规则，分两种情况遍历执行
Comparator<? super K> cpr = comparator;
if (cpr != null) {
//从root根开始使用自己的排序规则对找到插入点。
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();
@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);
}
//获取父类比较cmp的值，插入到父类的位置。
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
//使用红黑树的变化规则，可以参考我的上一篇文章红黑树的原理，或者hashmap的put方法。
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
3. treemap的get方法
public class TreeMap<K, V> extends AbstractMap<K, V>
implements NavigableMap<K, V>, Cloneable, java.io.Serializable {
...
/**
* 根据 key 进行查操作
*
* @param key 键
* @return 返回查找后的元素值，如若不存在返回 null
*/
public V get(Object key) {
TreeMapEntry<K, V> p = getEntry(key);
return (p == null ? null : p.value);
}
/**
* 根据 key 获取对应的节点
*
* @param key 键
* @return 返回节点
*/
final TreeMapEntry<K, V> getEntry(Object key) {
// 如果比较器为空，只是用 key 作为比较器查询
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
Comparable<? super K> k = (Comparable<? super K>) key;
// 取得 root 节点
TreeMapEntry<K, V> p = root;
// 核心来了：从 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;
}
...
}
网友评论