JDK 源码分析：TreeMap（二）
前文「 JDK源码分析-TreeMap(1) 」分析了 TreeMap 的一些方法，本文分析其中的增删方法。这也是红黑树插入和删除节点的操作，由于相对复杂，因此单独进行分析。
插入操作
该操作其实就是红黑树的插入节点操作。 前面分析过， 红黑树是一种平衡二叉树，新增 节点后 可能导致其失去平衡，因此需要对其进行修复操作以维持其平衡性。插入操作的 代码如下：
<span><span>public</span> V put(K key, V value) {</span>
<span> Entry<K,V> t = root;</span>
<span> <span>// 若 root 节点为空，则直接插入（为根节点）</span></span>
<span> <span>if</span> (t == <span>null</span>) {</span>
<span> compare(key, key); <span>// type (and possibly null) check</span></span>
<span> root = <span>new</span> Entry<>(key, value, <span>null</span>);</span>
<span> size = <span>1</span>;</span>
<span> modCount++;</span>
<span> <span>return</span> <span>null</span>;</span>
<span> }</span>
<span> int cmp;</span>
<span> Entry<K,V> <span>parent</span>;</span>
<span> <span>// split comparator and comparable paths</span></span>
<span> <span>// 拆分 Comparator 接口和 Comparable 接口（上文 getEntry 方法也是如此）</span></span>
<span> Comparator<span><?</span> super K> cpr = comparator;</span>
<span> <span>if</span> (cpr != <span>null</span>) {</span>
<span> <span>do</span> {</span>
<span> <span>parent</span> = t;</span>
<span> cmp = cpr.compare(key, t.key);</span>
<span> <span>if</span> (cmp < <span>0</span>)</span>
<span> t = t.left;</span>
<span> <span>else</span> <span>if</span> (cmp > <span>0</span>)</span>
<span> t = t.right;</span>
<span> <span>else</span></span>
<span> <span>// 若key已存在，则替换其对应的value</span></span>
<span> <span>return</span> t.setValue(value);</span>
<span> } <span>while</span> (t != <span>null</span>);</span>
<span> }</span>
<span> <span>else</span> {</span>
<span> <span>if</span> (key == <span>null</span>)</span>
<span> <span>throw</span> <span>new</span> NullPointerException();</span>
<span> @SuppressWarnings(<span>"unchecked"</span>)</span>
<span> Comparable<span><?</span> super K> k = (Comparable<span><?</span> super K>) key;</span>
<span> <span>do</span> {</span>
<span> <span>parent</span> = t;</span>
<span> cmp = k.compareTo(t.key);</span>
<span> <span>if</span> (cmp < <span>0</span>)</span>
<span> t = t.left;</span>
<span> <span>else</span> <span>if</span> (cmp > <span>0</span>)</span>
<span> t = t.right;</span>
<span> <span>else</span></span>
<span> <span>return</span> t.setValue(value);</span>
<span> } <span>while</span> (t != <span>null</span>);</span>
<span> }</span>
<span> Entry<K,V> e = <span>new</span> Entry<>(key, value, <span>parent</span>);</span>
<span> <span>if</span> (cmp < <span>0</span>)</span>
<span> <span>parent</span>.left = e;</span>
<span> <span>else</span></span>
<span> <span>parent</span>.right = e;</span>
<span> <span>// 插入节点后的平衡性调整</span></span>
<span> fixAfterInsertion(e);</span>
<span> size++;</span>
<span> modCount++;</span>
<span> <span>return</span> <span>null</span>;</span>
<span>}</span>
对应的几种插入节点修复操作前文「 数据结构与算法笔记（四） 」 已进行了分析 ，为了便于分析和理解代码，这里把图再贴一下（下图为关注节点的父节点是其祖父节点的左子节点的情况，在右边时操作类似）：
case1: 关注节点 a 的叔叔节点为红色
case2: 关注节点为 a， 它的叔叔节点 d 是黑色，a 是其父节点 b 的右子节点
case3: 关注节点是 a，它的叔叔节点 d 是黑色，a 是其父节点 b 的左子节点
插入操作的平衡调整代码如下：
<span><span><span>private</span> <span>void</span> <span>fixAfterInsertion</span>(<span>Entry<K,V> x</span>)</span> {</span>
<span> <span>// 新插入的节点为红色</span></span>
<span> x.color = RED;</span>
<span> <span>// 只有在父节点为红色时需要进行插入修复操作</span></span>
<span> <span>while</span> (x != <span>null</span> && x != root && x.parent.color == RED) {</span>
<span> <span>// 下面两种情况是左右对称的</span></span>
<span> <span>// x 的父节点是它祖父节点的左子节点</span></span>
<span> <span>if</span> (parentOf(x) == leftOf(parentOf(parentOf(x)))) {</span>
<span> <span>// 叔叔节点</span></span>
<span> Entry<K,V> y = rightOf(parentOf(parentOf(x)));</span>
<span> <span>// case1</span></span>
<span> <span>if</span> (colorOf(y) == RED) {</span>
<span> setColor(parentOf(x), BLACK);</span>
<span> setColor(y, BLACK);</span>
<span> setColor(parentOf(parentOf(x)), RED);</span>
<span> x = parentOf(parentOf(x));</span>
<span> } <span>else</span> {</span>
<span> <span>// case2</span></span>
<span> <span>if</span> (x == rightOf(parentOf(x))) {</span>
<span> x = parentOf(x);</span>
<span> rotateLeft(x);</span>
<span> }</span>
<span> <span>// case3</span></span>
<span> setColor(parentOf(x), BLACK);</span>
<span> setColor(parentOf(parentOf(x)), RED);</span>
<span> rotateRight(parentOf(parentOf(x)));</span>
<span> }</span>
<span> } </span>
<span> <span>// x 的父节点是它祖父节点的右子节点（与上面情况对称）</span></span>
<span> <span>else</span> {</span>
<span> Entry<K,V> y = leftOf(parentOf(parentOf(x)));</span>
<span> <span>if</span> (colorOf(y) == RED) {</span>
<span> setColor(parentOf(x), BLACK);</span>
<span> setColor(y, BLACK);</span>
<span> setColor(parentOf(parentOf(x)), RED);</span>
<span> x = parentOf(parentOf(x));</span>
<span> } <span>else</span> {</span>
<span> <span>if</span> (x == leftOf(parentOf(x))) {</span>
<span> x = parentOf(x);</span>
<span> rotateRight(x);</span>
<span> }</span>
<span> setColor(parentOf(x), BLACK);</span>
<span> setColor(parentOf(parentOf(x)), RED);</span>
<span> rotateLeft(parentOf(parentOf(x)));</span>
<span> }</span>
<span> }</span>
<span> }</span>
<span> root.color = BLACK;</span>
<span>}</span>
对称情况下的相应操作不再分析，其原理是类似的。
删除操作
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;
}
内部实现方法如下：
<span><span>/**</span></span>
<span><span> * Delete node p, and then rebalance the tree.</span></span>
<span><span> */</span></span>
<span><span>private</span> void deleteEntry(Entry<K,V> p) {</span>
<span> modCount++;</span>
<span> size--;</span>
<span> <span>// If strictly internal, copy successor's element to p and then make p</span></span>
<span> <span>// point to successor.</span></span>
<span> <span>// 左右子树都不为空，寻找后继节点</span></span>
<span> <span>if</span> (p.left != <span>null</span> && p.right != <span>null</span>) {</span>
<span> Entry<K,V> s = successor(p);</span>
<span> p.key = s.key;</span>
<span> p.value = s.value;</span>
<span> p = s;</span>
<span> } <span>// p has 2 children</span></span>
<span> <span>// Start fixup at replacement node, if it exists.</span></span>
<span> Entry<K,V> replacement = (p.left != <span>null</span> ? p.left : p.right);</span>
<span> <span>if</span> (replacement != <span>null</span>) {</span>
<span> <span>// Link replacement to parent</span></span>
<span> replacement.<span>parent</span> = p.<span>parent</span>;</span>
<span> <span>if</span> (p.<span>parent</span> == <span>null</span>)</span>
<span> root = replacement;</span>
<span> <span>else</span> <span>if</span> (p == p.<span>parent</span>.left)</span>
<span> p.<span>parent</span>.left = replacement;</span>
<span> <span>else</span></span>
<span> p.<span>parent</span>.right = replacement;</span>
<span> <span>// Null out links so they are OK to use by fixAfterDeletion.</span></span>
<span> p.left = p.right = p.<span>parent</span> = <span>null</span>;</span>
<span> <span>// Fix replacement</span></span>
<span> <span>if</span> (p.color == BLACK)</span>
<span> fixAfterDeletion(replacement);</span>
<span> } <span>else</span> <span>if</span> (p.<span>parent</span> == <span>null</span>) { <span>// return if we are the only node.</span></span>
<span> <span>// 只有一个根节点</span></span>
<span> root = <span>null</span>;</span>
<span> } <span>else</span> { <span>// No children. Use self as phantom replacement and unlink.</span></span>
<span> <span>if</span> (p.color == BLACK)</span>
<span> fixAfterDeletion(p);</span>
<span> <span>if</span> (p.<span>parent</span> != <span>null</span>) {</span>
<span> <span>if</span> (p == p.<span>parent</span>.left)</span>
<span> p.<span>parent</span>.left = <span>null</span>;</span>
<span> <span>else</span> <span>if</span> (p == p.<span>parent</span>.right)</span>
<span> p.<span>parent</span>.right = <span>null</span>;</span>
<span> p.<span>parent</span> = <span>null</span>;</span>
<span> }</span>
<span> }</span>
<span>}</span>
几种删除操作情况如下（下图为关注节点为父节点的左子节点的情况，关注节点为父节点的右子节点情况时的操作对称）：
case1: 关注 节点的兄弟节点是红色
case2: 关注 节点的兄弟节点是黑色，且兄弟节点的子节点都是黑色
case3: 关注 节点的兄弟节点是黑色，且左子节点是红色、右子节点是黑色
case4: 关注 节点的兄弟节点是黑色，且右子节点是红色、左子节点是黑色
勘误 ：前文「 数据结构与算法笔记（四） 」对红黑树删除操作第四种情况的分析不够准确，近两天又参考了其他文章及代码，这里的 case4 是目前经分析认为比较准确的（符合 JDK 1.8 源码中 TreeMap 的实现思路）。
PS: 别人的资料也未必都正确，不可全信，包括本文，还是要持有怀疑精神的。
删除操作的平衡调整代码如下：
private void fixAfterDeletion(Entry<K,V> x) {
// x 不为根节点，且颜色为黑色
while (x != root && colorOf(x) == BLACK) {
// x 是父节点的左子节点
if (x == leftOf(parentOf(x))) {
// 兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
// case1 待删除节点的兄弟节点为红色
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
rotateLeft(parentOf(x));
sib = rightOf(parentOf(x));
}
// case2 待删除节点的兄弟节点的子节点都为黑色
if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
setColor(sib, RED);
x = parentOf(x);
} else {
// case3 待删除节点的兄弟节点的左子节点为红色、右子节为黑色
if (colorOf(rightOf(sib)) == BLACK) {
setColor(leftOf(sib), BLACK);
setColor(sib, RED);
rotateRight(sib);
sib = rightOf(parentOf(x));
}
// case4 待删除节点的兄弟节点的左子节点为黑色、右子节为红色
setColor(sib, colorOf(parentOf(x)));
setColor(parentOf(x), BLACK);
setColor(rightOf(sib), BLACK); //??
rotateLeft(parentOf(x));
x = root;
}
}
// x 是父节点的右子节点（对称操作）
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);
}
插入和删除操作相对复杂，容易被绕晕，但其实也是有规律可循的。对比操作的图解，可以更容易分析和理解。
参考文章：
https: //zhuanlan.zhihu.com/p/22800206
这篇文章介绍了红黑树的删除操作，逻辑清晰，推荐阅读。
相关阅读：
JDK源码分析-TreeMap(1)
数据结构与算法笔记（四）
Stay hungry, stay foolish.
正文到此结束
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
