CHM-红黑树
- putTreeVal
/**
* Finds or adds a node.
* @return null if added
*/
final TreeNode<K,V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
boolean searched = false;
for (TreeNode<K,V> p = root;;) { //以根节点为当前节点
int dir, ph; K pk;
if (p == null) {
first = root = new TreeNode<K,V>(h, k, v, null, null); //根节点为空，新建一个节点作为根节点，返回
break;
}
else if ((ph = p.hash) > h) //当前节点hash ph>h，则新节点应该在左侧，dir=-1
dir = -1;
else if (ph < h)
dir = 1; //当前节点 ph<h，则新节点应该在右侧，dir=1
else if ((pk = p.key) == k || (pk != null && k.equals(pk))) //当前节点与新节点的key==或equals，则无需新建节点，直接返回当前节点
return p;
else if ((kc == null && //其他情况：hash相等，但key不一样
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) { //key 未实现comparable接口，或key compare==0（dir重新赋值）
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
if (((ch = p.left) != null &&
(q = ch.findTreeNode(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.findTreeNode(h, k, kc)) != null))
return q; //往左或往右查找，若找到与k相同key的节点，则返回
}
dir = tieBreakOrder(k, pk); //未找到，比较k和pk的identityHashCode大小，给dir重新赋值
}
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) { //根据dir，往左或往右移动，并继续循环遍历，直至叶子节点，即 p==null
TreeNode<K,V> x, f = first;
first = x = new TreeNode<K,V>(h, k, v, f, xp); //新建节点x，并将first节点指向新建节点x
if (f != null) //将原来的first.prev指向新节点x
f.prev = x;
if (dir <= 0)
xp.left = x; //x为左节点
else
xp.right = x; //x为右节点
if (!xp.red)
x.red = true; //若父节点为黑色，当前新建节点涂为红色，直接插入即可
else {
lockRoot(); //否则需要平衡调整，此过程需要对根节点加锁
try {
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
assert checkInvariants(root);
return null;
}
- balanceInsertion
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;;) {
if ((xp = x.parent) == null) { //1、父节点为空，则将当前节点涂黑，并设为根节点，返回
x.red = false;
return x;
}
else if (!xp.red || (xpp = xp.parent) == null) //2、父节点为黑色或父节点为根节点（祖父节点为空），无需调整，返回。
return root;
if (xp == (xppl = xpp.left)) { //父节点是左节点
if ((xppr = xpp.right) != null && xppr.red) { //3、父节点是红色，叔节点也是红色
xppr.red = false; //3-1、涂色：父节点、叔节点涂黑，祖父节点涂红
xp.red = false;
xpp.red = true;
x = xpp; //3-2、将祖父节点选为当前节点x=xpp，继续递归上溯调整
}
else { //4.1、父节点是红色，叔节点是黑色，父节点是左节点
if (x == xp.right) { //4.1.1 调整：当前节点是左节点的才需要，调整到同一侧（都为左节点）
root = rotateLeft(root, x = xp); // 左旋：以父节点为支点左旋，目的是将x、xp、xpp全部都调整到左侧节点，此时链路为：xp <- x <- xpp
// 重选：x=xp，以最左侧节点为当前节点（即以父节点为当前节点）
xpp = (xp = x.parent) == null ? null : xp.parent; //重新给xp, xpp赋值
}
if (xp != null) {
xp.red = false; //4.1.2 涂色和平衡
if (xpp != null) {
xpp.red = true; // 涂色：父节点涂黑，祖父节点涂红：x:red, xp：black, xpp:red，此时链路为：x <- xp <- xpp
root = rotateRight(root, xpp); // 平衡：以祖父节点为支点右旋，目的是将x、xp、xpp三个节点重新平衡，此时链路为：x <- xp -> xpp
//注意：这一步右旋后不改变当前节点，进行下一次循环时父节点已经涂黑了xp:black，将跳出循环
}
}
}
}
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);
}
}
}
}
}
}
balanceInsertion
当前插入节点默认涂红
1、父节点为空，则将当前节点涂黑，并设为根节点，返回。
2、父节点为黑色或父节点为根节点（祖父节点为空），无需调整，返回。
3、父节点是红色，叔节点也是红色
涂色：父节点、叔节点涂黑，祖父节点涂红
重选：将祖父节点选为当前节点x=xpp
原理：父节点和叔节点都是红色，说明以xpp为根的这棵子树下面的子孙是平衡的。所以，就先涂颜色：当前节点是红色，把父节点涂黑，为了保持平衡叔节点需要一起涂黑；
然后，将祖父节点选为当前节点并涂红（因为之前的当前节点即新加的节点默认是红色的），进行递归上溯调整
4、父节点是红色，叔节点是黑色
4.1、父节点是左节点
调整：当前节点是右节点的才需要
左旋：以父节点为支点左旋，目的是将x、xp、xpp全部都调整到左侧，此时链路为：xp <- x <- xpp
重选：以最左侧节点为当前节点（即以父节点为当前节点x=xp），以新的x重新给xp、xpp赋值，此时链路为：x <- xp <- xpp
涂色和平衡
涂色：父节点涂黑，祖父节点涂红：x:red, xp：black, xpp:red，此时链路为：x <- xp <- xpp
右旋：以祖父节点为支点右旋，目的是将x、xp、xpp三个节点重新平衡，此时链路为：x <- xp -> xpp
注意：这一步右旋后不改变当前节点，进行下一次循环时父节点已经涂黑了xp:black，将跳出循环
4.2、父节点是右节点
调整：当前节点是左节点的才需要
右旋：以父节点为支点右旋，目的是将x、xp、xpp全部都调整到右侧，此时链路为：xpp -> x-> xp
重选：以最右侧节点为当前节点（即以父节点为当前节点x=xp），以新的x重新给xp、xpp赋值，此时链路为：xpp -> xp -> x
涂色和平衡
涂色：父节点涂黑，祖父节点涂红：x:red, xp：black, xpp:red，此时链路为：xpp -> xp -> x
左旋：以祖父节点为支点左旋，目的是将x、xp、xpp三个节点重新平衡，此时链路为：xpp <- xp -> x
注意：这一步左旋后不改变当前节点，进行下一次循环时父节点已经涂黑了xp:black，将跳出循环
原理：父节点和叔节点颜色不一致，x节点插入后就有可能造成以xpp为根的子树不平衡，需要调整。
调整策略就是：先将x、xp、xpp拉到同一侧（都为左节点或都为右节点），以最下方节点（左侧为最左，右测为最右）为当前节点，将当前的父节点涂黑，祖父涂红并以祖父为支点旋转平衡。
调整后：链路为：x <- xp -> xpp 或 xpp <- xp -> x，颜色都是 红 - 黑 - 红，子树根节点是xp，调整后子树是平衡的且子树的根节点是黑色的。然后再以x节点继续循环，将走到第2步，结束调整。
