共计 14947 个字符，预计需要花费 38 分钟才能阅读完成。
前面几篇文章已经讲解过 HashMap 内部实现以及红黑树的基础知识，今天这篇文章就讲解之前 HashMap 中未讲解的红黑树操作部分，如果没了解红黑树，请去阅读前面的两篇文章，能更好的理解本章所讲解的红黑树源码操作，全文默认读者已经了解红黑树的相关知识，接下来，就以 HashMap.TreeNode 来说明红黑树的源码操作。
前言
jdk 版本：1.8
以 HashMap.TreeNode 为例是因为之前 HashMap 的红黑树操作在文章省略了，这里进行一个解释，其实源码里并不是只有这个地方用红黑树结构，但是总体上都大同小异，故只说明这一部分就好，举一反三的能力相信各位都应该拥有。
类定义
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>继承 LinkedHashMap.Entry，追溯源头可以到 HashMap.Node，下面图展示了对应的结构关系：
属性
/**
* 父节点
*/
TreeNode<K,V> parent; // red-black tree links
/**
* 左子节点
*/
TreeNode<K,V> left;
/**
* 右子节点
*/
TreeNode<K,V> right;
/**
* 指向前一个节点
*/
TreeNode<K,V> prev; // needed to unlink next upon deletion
/**
* 是否是红色节点
*/
boolean red;以上的属性都是为了满足红黑树特性而设置
构造方法
/**
* 构造方法直接调用的父类方法
* 最终还是 HashMap.Node 的构造方法，调用代码下面也列出来了
*/
TreeNode(int hash, K key, V val, Node<K,V> next) {super(hash, key, val, next);
}
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
static class Entry<K,V> extends HashMap.Node<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);
}
}
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}Node 和 TreeNode 相同的构造方法
重要方法
root
实现上非常简单，不断向上遍历，找到父节点为空的节点即为根节点
/**
* 返回根节点 TreeNode
*/
final TreeNode<K,V> root() {for (TreeNode<K,V> r = this, p;;) {if ((p = r.parent) == null)
return r;
r = p;
}
}moveRootToFront
从注释中也能看出当前方法的含义，确保根节点是 bin 桶（数组 tab 的其中一个元素）中的第一个节点, 如果不是，则进行操作，将根节点放到 tab 数组上，这个跟 HashMap 结构有关，数组（链表 + 红黑树），在进行树化，结构调整时，根节点可能会变化，原有数组 tab 对应索引指向的树节点需要进行改变，指向新的根节点, 这里注意下，移动时不是修改红黑树是修改的链表结构，prev 和 next 属性
/**
* Ensures that the given root is the first node of its bin.
*/
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
// 找到当前树所在的 bin 桶位置（即数组 tab 的位置）int index = (n - 1) & root.hash;
// 将 tab[index] 的树节点记录下来为 first
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
// root 没有落在 tab 数组上，修改为 root 在 tab 数组上
if (root != first) {
Node<K,V> rn;
// 这里即替换掉 tab[index] 指向的原有节点，可以理解成现在指向 root 节点
tab[index] = root;
// rp 为 root 指向的前一个节点
TreeNode<K,V> rp = root.prev;
// rn 为 root 的后一个节点
// 将 root 前后节点关联
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
// first 和 root 节点进行关联，first 的前一个节点为 root
if (first != null)
first.prev = root;
// 修改 root 的链表属性
root.next = first;
root.prev = null;
}
// 检查红黑树一致性
assert checkInvariants(root);
}
}find
从当前节点开始使用给定的 hash 和 key 查找到对应的节点，只会判断当前节点为根节点的局部树结构。这里复习下整个 HashMap 查找过程，通过 (length – 1) & hash 判断 bin 桶位置（数组中的位置），这里不是 hash 值相等，注意再判断该位置处是什么类型，链表还是红黑树，链表类型，循环 next 遍历，直到 key 值相等。红黑树类型 递归左右子树遍历，直到 key 值相等。
/**
* Finds the node starting at root p with the given hash and key.
* The kc argument caches comparableClassFor(key) upon first use
* comparing keys.
* kc：key class
*/
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
TreeNode<K,V> p = this;
do {
// ph:p 的 hash 值
int ph, dir; K pk;
TreeNode<K,V> pl = p.left, pr = p.right, q;
// 查找节点 hash 值小于 p 的 hash 值，搜索左子树
if ((ph = p.hash) > h)
p = pl;
// 查找节点 hash 值大于 p 的 hash 值，搜索右子树
else if (ph < h)
p = pr;
// key 值相同，说明就是此 p 节点
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
// 若 hash 相等但 key 不等，向左右子树非空的一侧移动
else if (pl == null)
p = pr;
else if (pr == null)
p = pl;
// 左右两边都不为空
// 判断 kc 是否是 k 实现的可比较的类，是就比较 k 和 pk 的值，k<pk 向左子树移动否则向右子树移动
// hash 相等，key 不等，使用 key 实现的 compareTo 判断大小
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
// 上面所有情况依旧不能判断左右，就先递归判断右子树，看是否匹配上，匹配上就赋右子树，否则左子树
else if ((q = pr.find(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
return null;
}tieBreakOrder
比较两个对象的大小，返回值只能大于 0 或小于 0，不能为 0，因为需要插入节点是放在左子树还是右子树，这里在两个对象都不为空时，先比较两个对象的类名按字符串规则比较，如果类名比较不出来或者为空则调用 native 方法去比较 hashcode 值，相等时返回 -1
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}tieBreakOrder
比较两个对象的大小，返回值只能大于 0 或小于 0，不能为 0，因为需要插入节点是放在左子树还是右子树，这里在两个对象都不为空时，先比较两个对象的类名按字符串规则比较，如果类名比较不出来或者为空则调用 native 方法去比较 hashcode 值，相等时返回 -1
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}treeify
以当前 TreeNode 为初始节点，循环处理链表上的每个节点，每次插入树节点都要进行平衡处理，保证红黑树的平衡。
/**
* Forms tree of the nodes linked from this node.
* @return root of tree
*/
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
// this 当前 TreeNode, 一般应该以树的根节点为初始值，根据链表进行遍历
for (TreeNode<K,V> x = this, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
// 首次 root 为空 当前节点先设置为 root 节点颜色为黑色
if (root == null) {
x.parent = null;
x.red = false;
root = x;
}
// root 节点设置之后开始将链表节点依次插入处理，x=x.next 插入 root 为根节点的红黑树，循环处理
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 比较 hash 值判断处于左右子树哪侧
if ((ph = p.hash) > h)
// 节点处于 p 左子树下
dir = -1;
else if (ph < h)
// 节点处于 p 右子树下
dir = 1;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
// hash 值相等根据 compareTo 判断，判断不出来继续执行 tieBreakOrder 判断
dir = tieBreakOrder(k, pk);
// x 的父节点设置为 xp
TreeNode<K,V> xp = p;
// 左右节点为空，说明可以将新增节点插入
// 非空，继续循环子树，p 指向左子树或右子树，继续循环判断直到为空的节点
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 插入后需进行平衡保证红黑树特性
root = balanceInsertion(root, x);
break;
}
}
}
}
// root 位置可能会在调整中变更，这里需调用确保根节点落在 tab 数组上
moveRootToFront(tab, root);
}untreeify
将树转换为链表结构，将 TreeNode 转化为 Node，改变 next 指向即可
/**
* Returns a list of non-TreeNodes replacing those linked from
* this node.
*/
final Node<K,V> untreeify(HashMap<K,V> map) {
// hd 是链表首节点，tl 是链表尾节点
Node<K,V> hd = null, tl = null;
for (Node<K,V> q = this; q != null; q = q.next) {Node<K,V> p = map.replacementNode(q, null);
if (tl == null)
hd = p;
else
tl.next = p;
tl = p;
}
return hd;
}
Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) {return new Node<>(p.hash, p.key, p.value, next);
}putTreeVal
在红黑树结构中的 putVal 操作，先判断节点应该存在的位置，循环判断左右子树，找到应该存在的位置。若该位置为空，相当于原本无值，插入节点，然后进行平衡，桶位置调整。若该位置有值且相等，则直接返回，不需要插入操作。
/**
* Tree version of putVal.
*/
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
// 获取根节点
TreeNode<K,V> root = (parent != null) ? root() : this;
// 循环遍历，类似 find 方法
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
return p;
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {if (!searched) {
// 递归左右子树进行查找是否已经存在
// 只需判断一次即可，第二次不再执行
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
return q;
}
// 上面都比较不出来，通过这个方法比较出来
dir = tieBreakOrder(k, pk);
}
// 判断当前插入位置是否为空，为空才插入，非空则继续判断，根据 dir 判断是左还是右子树
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
Node<K,V> xpn = xp.next;
TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
if (dir <= 0)
xp.left = x;
else
xp.right = x;
xp.next = x;
x.parent = x.prev = xp;
if (xpn != null)
((TreeNode<K,V>)xpn).prev = x;
// balanceInsertion 插入调整平衡
// moveRootToFront 确保 root 节点落在 tab 数组上为首节点
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}removeTreeNode
删除树节点操作，movable：判断是否需要调整 root 节点（放置在 tab 上），在 HashMap 里 removeNode 方法中使用，对应的删除节点进行调用，具体自行查看源码部分。其实，想下，删除操作相当于将链表节点之间的关联重新梳理，修正两部分，第一部分是链表的关系修正，第二部分是树的关系修正，然后自平衡操作即可。
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,boolean movable) {
int n;
// 判断非空
if (tab == null || (n = tab.length) == 0)
return;
// 计算当前树节点所在的桶的位置（tab 索引位置）int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
// succ 指向当前删除节点的后一个节点，pred 指向当前删除节点的前一个节点
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
if (pred == null)
// 前一个节点为空，说明删除的节点为根节点，first 和 tab[index] 需指向删除节点的后一个节点
tab[index] = first = succ;
else
// 前一个节点不为空，则前一个节点的后一个节点为 succ(删除之后的关联)
pred.next = succ;
if (succ != null)
// 后一个节点不为空，则后一个节点的前一个节点为 pred，构建关联
succ.prev = pred;
if (first == null)
// first 为空则表明当前桶内无节点，直接 return
return;
if (root.parent != null)
// 目前的 root 节点有父类，需要调整
root = root.root();
if (root == null || root.right == null ||
(rl = root.left) == null || rl.left == null) {
// 根自身或者左右儿子其中一个为空或左子树的子树为空需转换为链表结构
// 考虑到红黑树特性，这几种情况下，节点较少，进行树向链表的转化
tab[index] = first.untreeify(map); // too small
return;
}
// p 指向删除的节点
// 上面修正链表的关系，下面修正树中的关系
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// 删除节点的左右子树都不为空，参考红黑树删除 4 种情况
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
while ((sl = s.left) != null) // find successor
// 寻找右子树中最左的叶结点作为后继节点，s 指向后继节点
s = sl;
// 交换后继节点和删除节点的颜色，从这里开始在后继节点上进行删除处理
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
if (s == pr) { // p was s's direct parent
// s 是 p 的右儿子，直接父子关系，交换 p 和 s 的位置
// 改变两节点的指向，相当于交换值
p.parent = s;
s.right = p;
}
else {
TreeNode<K,V> sp = s.parent;
// 删除节点的父节点指向其后继节点的父节点
if ((p.parent = sp) != null) {
// 判断 s 是左子节点还是右子节点，s 父节点一侧指向删除节点 p
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
// s 右节点指向原本 p 的右节点，不为空，原 p 右子节点的父节点指向 s
pr.parent = s;
}
// 修改 p 的左节点为空，因为现在 p 已经在后继节点上
p.left = null;
// 两个 if 是调整 p 和 s 交换后节点的指向关系
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
// p 的父亲成为 s 的父亲，为空说明是根节点，root 指向 s
root = s;
else if (p == pp.left)
// p 的父亲的左儿子原为 p，现为 s
pp.left = s;
else
// 否则右儿子为 s
pp.right = s;
// 若 s 结点有右儿子（s 没有左儿子，因为 s 是后继节点），则 replacement 为这个右儿子否则为 p
// replacement 相当于 p 和后继节点 s 交换后，删除 s 位置取代其位置的节点，参考红黑树删除过程理解
if (sr != null)
replacement = sr;
else
replacement = p;
}
// 删除节点的左右子树一侧为空，参考红黑树删除 4 种情况
// 若 p 的左右儿子为空，则 replacement 为非空的一方，否则为 p 自己
else if (pl != null)
replacement = pl;
else if (pr != null)
replacement = pr;
else
replacement = p;
// replacement 不为 p，即不为叶子节点（相当于之前所讲的红黑树中有两个 NIL 节点的节点）// 处理连接关系
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
if (pp == null)
root = replacement;
else if (p == pp.left)
pp.left = replacement;
else
pp.right = replacement;
// 移除 p 节点
p.left = p.right = p.parent = null;
}
// 红黑树自平衡调节，如果为红色，则不需要进行调整，否则需要自平衡调整，后面会对这个方法进行分析
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// 后继节点无子节点，直接移除 p 节点即能保持平衡
if (replacement == p) { // detach
TreeNode<K,V> pp = p.parent;
p.parent = null;
if (pp != null) {if (p == pp.left)
pp.left = null;
else if (p == pp.right)
pp.right = null;
}
}
if (movable)
// 调整 root 使其落在 tab 数组上
moveRootToFront(tab, r);
}split
拆分，在 HashMap.resize 方法中调用 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap)。在扩容之后，红黑树和链表因为扩容的原因导致原本在一个数组元素下的 Node 节点分为高低位两部分（参考 HashMap.resize 链表部分的改变，是相同的），请查看 HashMap 的文章自行回顾，低位树即当前位置，高位树则在新扩容的 tab 上
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
TreeNode<K,V> b = this;
// Relink into lo and hi lists, preserving order
// 分成高位树和低位树，头尾节点先声明
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
int lc = 0, hc = 0;
// 循环处理节点
for (TreeNode<K,V> e = b, next; e != null; e = next) {next = (TreeNode<K,V>)e.next;
e.next = null;
// 这里 bit 代表扩容的二进制位（数值是扩容前的容量大小），不明白的也请参考之前的 HashMap 讲解文章
if ((e.hash & bit) == 0) {
// 0 说明在低位树，即原位置
if ((e.prev = loTail) == null)
// 首节点设置
loHead = e;
else
// 链表 next 设置
loTail.next = e;
loTail = e;
++lc;
}
else {
// 同上，主要是在高位树上处理
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 对高低位树进行处理，将数组节点指向树根节点或者链表首节点
if (loHead != null) {if (lc <= UNTREEIFY_THRESHOLD)
// 拆分之后节点小于非树化阈值，转成链表结构
tab[index] = loHead.untreeify(map);
else {tab[index] = loHead;
// 高位树为空则表示节点全部留在了低位树，不需要进行树化操作，已经树化过了
if (hiHead != null) // (else is already treeified)
loHead.treeify(tab);
}
}
if (hiHead != null) {if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
// 高位所处的位置为原本位置 + 旧数组的大小即 bit
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}rotateLeft
左旋操作，参考红黑树讲解中的图来理解，自己动手画一画也能明白，右旋操作类似，不再多说
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
// r 代表 M 的右子节点 N，先决条件，p(M),r(N) 不能为空
if (p != null && (r = p.right) != null) {
// r 的左子节点成为 p 的右子节点，即 B 成为 M 的右子节点
if ((rl = p.right = r.left) != null)
// r 的左子节点父节点指向 p, 即修改 B 父节点指向 M
rl.parent = p;
// p 的父节点成为 r 的父节点，即 N 父节点为原 M 的父节点
if ((pp = r.parent = p.parent) == null)
// r 的父节点为空，则 r 为 root 节点，设置为黑色，即 N 父节点为空，N 设置为根节点
(root = r).red = false;
// 原 p 节点是左子树，即 M 是左子树
else if (pp.left == p)
// 现调整后修改 N 父节点左子指向 N
pp.left = r;
else
// r 的父节点的右子节点需重设, 即调整后修改 N 父节点右子指向 N
pp.right = r;
// p 和 r 的位置关系修改，即 M 与 N 的关系重设
r.left = p;
p.parent = r;
}
return root;
}balanceInsertion
插入节点之后进行平衡调整，x 为新添加的节点，root 为树的根节点，返回根节点。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
// 根据红黑树属性插入的节点默认设置为红色
x.red = true;
// 通过循环进行调整, 从叶子到根节点进行局部调整
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
// x 的父节点为空，说明 x 节点为根节点，将颜色置为黑即可
// 符合插入节点第一种情况
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// x 父节点为黑色或者 x 的祖父节点为空
// 符合插入节点第二种情况
else if (!xp.red || (xpp = xp.parent) == null)
return root;
// 下面情况中 x 的颜色都为红色，因为上边已经判断过黑色
// x 的父节点为 x 祖父节点的左儿子，插入情况下三四种情况需要区分左还是右
if (xp == (xppl = xpp.left)) {
// x 祖父右儿子，即 x 的叔叔不为空，且为红色
// 符合插入节点第三种情况
if ((xppr = xpp.right) != null && xppr.red) {
// x 的叔叔修改为黑色
xppr.red = false;
// x 的父节点修改为黑色
xp.red = false;
// x 的祖父节点修改为红色
xpp.red = true;
// x 指向 x 的祖父节点，以祖父节点循环继续向上调整，相当于 xpp 是插入节点
x = xpp;
}
else {
// x 的叔叔是黑色且 x 是右儿子，相当于在树的“内部”// 符合插入节点第四种情况的第一种状态
if (x == xp.right) {
// 以 x 父节点进行左旋
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 这里处理第二种状态，相当于在树的“外部”if (xp != null) {
// x 的父节点改为黑色，x 的祖父节点改为红色后对 x 的祖父节点进行右旋转
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateRight(root, xpp);
}
}
}
}
// x 的父节点为 x 祖父节点的右儿子
// 下面跟上边类似，对称关系
else {if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
}
else {if (x == xp.left) {root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}balanceDeletion
删除节点后自平衡操作，x 是删除节点的替换节点，注意下
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,TreeNode<K,V> x) {
// 循环操作，平衡局部之后继续判断调整
for (TreeNode<K,V> xp, xpl, xpr;;) {
// 删除节点为空或 x 为根节点直接返回，平衡调整完毕 x =root
if (x == null || x == root)
return root;
// 删除后 x 父节点为空，说明 x 为根节点，x 置为黑色，红黑树平衡
// 参考红黑树删除文章中的 3 种情况中的第一种情况，整棵树的根节点需要将根节点置黑
else if ((xp = x.parent) == null) {
// xp 为空 x 为根节点，x 置为黑色
x.red = false;
return x;
}
// x 为红色，原节点必为黑色，变色操作即可满足红黑树特性达到平衡
// 参考红黑树删除文章中的 3 种情况中的第二种情况
else if (x.red) {
x.red = false;
return root;
}
// 区分 x 为左子节点还是右子节点
else if ((xpl = xp.left) == x) {
// x 的叔叔为红色
// 符合 3 种情况中的第三种情况中的第二种情况
if ((xpr = xp.right) != null && xpr.red) {
// 先进行变色，然后进行左旋操作，xpr 指向 xp 新的右子
xpr.red = false;
xp.red = true;
root = rotateLeft(root, xp);
xpr = (xp = x.parent) == null ? null : xp.right;
}
// x 的兄弟为空
if (xpr == null)
// x 指向 x 的父节点，继续以 x 父节点调整平衡
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
// 符合 3 种情况中的第三种情况中的第三种情况
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// sr，sl 两个兄弟都是黑色，x 的兄弟设置为红色，x 指向 x 的父节点继续向上循环调整平衡
xpr.red = true;
x = xp;
}
else {
// 符合 3 种情况中的第三种情况中的第五种情况
if (sr == null || !sr.red) {
// sr 为空或者为黑色
if (sl != null)
// sl 非空说明为红色，设置为黑色
sl.red = false;
// x 的兄弟设置为红色
xpr.red = true;
// 右旋
root = rotateRight(root, xpr);
xpr = (xp = x.parent) == null ?
null : xp.right;
}
// 符合 3 种情况中的第三种情况中的第六种情况
if (xpr != null) {
// xpr 颜色设置
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
// xpr 右孩子设置为黑色
sr.red = false;
}
if (xp != null) {
xp.red = false;
// 左旋操作
root = rotateLeft(root, xp);
}
x = root;
}
}
}
// 和上边是对称操作
else { // symmetric
if (xpl != null && xpl.red) {
xpl.red = false;
xp.red = true;
root = rotateRight(root, xp);
xpl = (xp = x.parent) == null ? null : xp.left;
}
if (xpl == null)
x = xp;
else {
TreeNode<K,V> sl = xpl.left, sr = xpl.right;
if ((sl == null || !sl.red) &&
(sr == null || !sr.red)) {
xpl.red = true;
x = xp;
}
else {if (sl == null || !sl.red) {if (sr != null)
sr.red = false;
xpl.red = true;
root = rotateLeft(root, xpl);
xpl = (xp = x.parent) == null ?
null : xp.left;
}
if (xpl != null) {xpl.red = (xp == null) ? false : xp.red;
if ((sl = xpl.left) != null)
sl.red = false;
}
if (xp != null) {
xp.red = false;
root = rotateRight(root, xp);
}
x = root;
}
}
}
}
}checkInvariants
对整棵树进行红黑树一致性的检查 目前仅在检查 root 是否落在 table 上时调用，满足红黑树的特性以及节点指向的正确性
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {
TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
tb = t.prev, tn = (TreeNode<K,V>)t.next;
// t 的前一个节点的后一个节点应为 t
if (tb != null && tb.next != t)
return false;
// tn 的后一个节点的前一个节点应为 t
if (tn != null && tn.prev != t)
return false;
// t 的父节点的左子节点或右子节点应为 t
if (tp != null && t != tp.left && t != tp.right)
return false;
// t 的左子节点的父节点应为 t 并且 t 的左子节点 hash 值小于 t 的 hash 值
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
// t 的右子节点的父节点应为 t 并且 t 的右子节点 hash 值大于 t 的 hash 值
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
// t 和 t 的子节点不能同时是红色，红黑树特性
if (t.red && tl != null && tl.red && tr != null && tr.red)
return false;
// 左子节点递归检查
if (tl != null && !checkInvariants(tl))
return false;
// 右子节点递归检查
if (tr != null && !checkInvariants(tr))
return false;
return true;
}总结
至此，关于 TreeNode 的代码讲解部分已经完成，类似的源码 TreeMap 等使用红黑树结构的类基本操作都是类似源码，可以自行查看，重要的部分在于插入和删除是如何做到的，在之后如何进行自平衡操作的，希望对各位读者有所帮助
正文完
