愿奴胁下生双翼，随花飞落天尽头。
红黑树
红黑树（Red Black Tree） 是一种自平衡二叉查找树。
1.基本性质
1）每个节点要么是黑的，要么是红的；
2）根节点是黑的；
3）叶节点是黑的；；
4）如果一个节点是红的，他的两个儿子节点都是黑的；
5）对于任一节点而言，其到叶节点树尾端NIL指针的每一条路径都包含相同数目的黑节点。
ps:在红黑树中一般用黑的NIL节点表示叶节点，不包含值，只是标志该分支结束。
Node
继承关系
Node<K,V> implements Map.Entry<K,V>
TreeNode
继承关系
TreeNode<K,V> extends LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>
属性
//红黑树关联关系
TreeNode<K,V> parent;
TreeNode<K,V> left;
TreeNode<K,V> right;
//删除节点的时候，需要断开连接
TreeNode<K,V> prev;
//节点红黑属性
boolean red;
构造函数
TreeNode(int hash, K key, V val, Node<K,V> next) {
//最终调用Node类的构造函数。
super(hash, key, val, next);
}
方法
1.重新平衡的基础方法
假设p为当前节点，pp为p的爸爸，ppr为pp的右孩子，ppl为pp的左孩子。
pr为p的右孩子，pl为p的左孩子，prr为pr的右孩子，prl为pl的左孩子，
方便后面左旋右旋的分析。
//检查当前节点的与父亲和左右孩子以及前后节点关联关系和颜色，然后进行递归其他检查，是否符合要求。
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;
//当前节点的前一个节点不为空,并且前一个节点的后一个节点不等于当前节点。
if (tb != null && tb.next != t)
return false;
//当前节点的后一个节点不为空，并且后一个节点的前一个节点不等于当前节点。
if (tn != null && tn.prev != t)
return false;
//父亲点不为空，并且当前节点既不是父亲的左孩子，也不是右孩子。
if (tp != null && t != tp.left && t != tp.right)
return false;
//当前节点的左孩子不为空，并且（左孩子的父亲不是当前节点或者左孩子的hash大于当前节点的hash。
if (tl != null && (tl.parent != t || tl.hash > t.hash))
return false;
//当前节点的右孩子不为空，并且（右孩子的父亲不是当前节点或者右孩子的hash小于当前节点的hash。
if (tr != null && (tr.parent != t || tr.hash < t.hash))
return false;
//当前节点为红色，并且左孩子不为空，左孩子的颜色为红色，右孩子不为空，右孩子的颜色为红色。
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;
//如果前面所有检查都通过了，返回true。
return true;
}
//把给定节点设为桶中的第一个元素。
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
int n;
if (root != null && tab != null && (n = tab.length) > 0) {
//计算root在数组上的索引位置。
int index = (n - 1) & root.hash;
//获取index位置的第一个树节点。
TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
//index位置的第一个节点不是指定的节点。
if (root != first) {
Node<K,V> rn;
//将root放在index所在的桶的第一个节点。
tab[index] = root;
//root的前一个节点。
TreeNode<K,V> rp = root.prev;
//那么建立前后节点的前后关系。
if ((rn = root.next) != null)
((TreeNode<K,V>)rn).prev = rp;
if (rp != null)
rp.next = rn;
//将root放在first前面，即让root变为桶中第一个节点。
if (first != null)
first.prev = root;
root.next = first;
root.prev = null;
}
//检查节点的前后关系及颜色是否正确。
assert checkInvariants(root);
}
}
//左旋。
//以某个结点作为支点(旋转结点)：
//(1)其右孩子变为支点的的爸爸；
//(2)其右孩子的的左孩子变为支点的的右孩子（右边的左孙子变成了自己的右孩子）。
//root 红黑树的根节点。
//p 旋转的支点。
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> r, pp, rl;
//如果p不为空且pr不为空。
if (p != null && (r = p.right) != null) {
//如果prl不为空。
//那么建立p与prl的父子关系。---（2）
if ((rl = p.right = r.left) != null)
rl.parent = p;
//让pp成为pr的爸爸。
//如果pp不存在，pr就是根节点了，颜色设置为红色。
if ((pp = r.parent = p.parent) == null)
(root = r).red = false;
//如果pp存在，且p是pp的左孩子，那么现在让pr成为pp的左孩子。
else if (pp.left == p)
pp.left = r;
//pp存在，且p是pp的右孩子，那么现在让pr成为pp的右孩子。
else
pp.right = r;
//现在建立p与pr的父子关系。---（1）
r.left = p;
p.parent = r;
}
//返回根节点
return root;
}
//右旋。
//以某个结点作为支点(旋转结点):
//（1）其左子结点变为支点点的父结点；
//（2）左子结点的右子结点变为支点的左子结点。
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
TreeNode<K,V> p) {
TreeNode<K,V> l, pp, lr;
//如果p不为空，且pl不为空。
if (p != null && (l = p.left) != null) {
//将plr存在，那么建立plr与p的父子关系。
if ((lr = p.left = l.right) != null)
//如果plr存在，那么plr的
lr.parent = p;
//如果pp不存在，那么pl就是根节点了，设置颜色为黑色。
if ((pp = l.parent = p.parent) == null)
(root = l).red = false;
//如果pp存在，并且p是pp的右孩子，那么现在将l设置为pp的右孩子。
else if (pp.right == p)
pp.right = l;
//如果pp存在，且p是pp的左孩子，那么现在将pl设置为pp的左孩子。
else
pp.left = l;
//设置pr与p的父子关系。
l.right = p;
p.parent = l;
}
//返回根节点
return root;
}
//插入之后，重新平衡。
//root 根节点。
//x 插入节点。
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//插入节点默认是红色。
x.red = true;
//初始化：
//xp--插入节点的父节点，xpp--xp的父节点，
//xppl--xpp的左孩子，xppr--xpp的右孩子。
for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
//当前节点的父节点不存在。
if ((xp = x.parent) == null) {
//设置颜色为黑色。
x.red = false;
//返回当前节点。
return x;
}
//如果当前节点的父节点存在，且（父节点是黑色或者祖父节点不存在）。
else if (!xp.red || (xpp = xp.parent) == null)
//返回根节点。
return root;
//如果父节点是祖父节点的左孩子
if (xp == (xppl = xpp.left)) {
//叔叔节点存在且叔叔是红色。
if ((xppr = xpp.right) != null && xppr.red) {
//设置叔叔节点为黑色。
xppr.red = false;
//设置父节点为黑色。
xp.red = false;
//设置祖父节点为红色。
xpp.red = true;
//将祖父节点赋值给当前节点。
x = xpp;
}
else {
//当前节点是父节点的右孩子。
if (x == xp.right) {
//以当前节点的父节点为支点左旋。
root = rotateLeft(root, x = xp);
//获取祖父节点。
xpp = (xp = x.parent) == null ? null : xp.parent;
}
//如果父节点不为空
if (xp != null) {
//设置父节点为黑色。
xp.red = false;
//如果祖父节点不为空。
if (xpp != null) {
//设置祖父节点为红色。
xpp.red = true;
//以祖父节点为支点右旋。
root = rotateRight(root, xpp);
}
}
}
}
//如果父节点是祖父节点的右孩子。
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);
}
}
}
}
}
}
//删除节点之后的重新平衡。
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
//初始化：：
//xp--当前节点得父节点，xpl--父节点的的左孩子，xpr--父节点的右孩子。
for (TreeNode<K,V> xp, xpl, xpr;;) {
//如果当前节点为空或者当前节点就是根节点。
if (x == null || x == root)
//返回根节点。
return root;
//父节点为空。
else if ((xp = x.parent) == null) {
//设置当前节点为黑色。
x.red = false;
//返回当前节点。
return x;
}
//如果当前节点为红色。
else if (x.red) {
//设置当前节点为黑色。
x.red = false;
//返回根节点。
return root;
}
//如果当前节点是父节点的左孩子。
else if ((xpl = xp.left) == x) {
//右兄弟节点存在，且颜色为红色。
if ((xpr = xp.right) != null && xpr.red) {
//设置右兄弟节点黑色。
xpr.red = false;
//设置父节点为红色。
xp.red = true;
//以根节点为支点左旋。
root = rotateLeft(root, xp);
//当前节点的父节点不存在，那么右兄弟节点也不存在。
xpr = (xp = x.parent) == null ? null : xp.right;
}
//如果右兄弟不存在。
if (xpr == null)
//将父节点赋值给当前节点。
x = xp;
//如果右兄弟节点存在。
else {
//sl左堂兄，sr右堂兄。
//如果（左堂兄不存在或者左堂兄为黑色）并且（右堂兄不存在或者右堂兄为黑色）。
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
//设置右叔叔节点为红色。
xpr.red = true;
//将父节点赋值给当前节点。
x = xp;
}
else {
//右堂兄不存在，或者右堂兄为黑色。
if (sr == null || !sr.red) {
//左堂兄存在。
if (sl != null)
//设置左堂兄为黑色。
sl.red = false;
//设置右叔叔为红色。
xpr.red = true;
//以右叔叔节点为支点右旋。
root = rotateRight(root, xpr);
//如果父节点不存在，那么右叔叔也不存在。
xpr = (xp = x.parent) == null ?
null : xp.right;
}
//如果右叔叔存在。
if (xpr != null) {
//父节点不存在，那么右叔叔黑色。
xpr.red = (xp == null) ? false : xp.red;
//右堂兄存在。
if ((sr = xpr.right) != null)
//设置右堂兄为黑色。
sr.red = false;
}
//父节点存在。
if (xp != null) {
//设置父节点为黑色。
xp.red = false;
//以父节点为支点左旋。
root = rotateLeft(root, xp);
}
//根节点赋值给当前节点。
x = root;
}
}
}
//如果当前节点是父节点的右孩子。
else {
//如果左叔叔存在，且颜色为红色。
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 {
//sl--左堂兄，sr--右堂兄。
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;
}
}
}
}
}
2.红黑树和链表的相互转换
//将红黑树转化为链表。
final Node<K,V> untreeify(HashMap<K,V> map) {
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);
//如果tl为不存在（首次循环才会走这个分支）。
if (tl == null)
//将该链表节点赋值给hd.
hd = p;
else
//如果tl为存在，那么将新的链表节点作为tl的下一个节点。
//（tl可以理解为链表的当前的最后一个节点）。
tl.next = p;
//将当前节点赋值给tl.
tl = p;
}
//返回桶中的第一个节点。
return hd;
}
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;
}
//将链表转换为红黑树。
//返回红黑树的根节点。
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
//从当前节点开始向后遍历。
for (TreeNode<K,V> x = this, next; x != null; x = next) {
//后一个节点。
next = (TreeNode<K,V>)x.next;
//初始化当前节点的左右孩子都不存在。
x.left = x.right = null;
//根节点不存在。
if (root == null) {
//当前节点的父节点不存在。
x.parent = null;
//设置当前节点为黑色。
x.red = false;
//设置当前节点为根节点。
root = x;
}
//根节点存在。
else {
//当前节点的key.
K k = x.key;
//当前节点的hash.
int h = x.hash;
Class<?> kc = null;
//从根节点开始遍历。
for (TreeNode<K,V> p = root;;) {
int dir, ph;
//遍历的根节点的key.
K pk = p.key;
//如果遍历的根节点hash大于当前节点的hash。
if ((ph = p.hash) > h)
dir = -1;
//如果遍历的根节点hash小于当前节点的hash。
else if (ph < h)
dir = 1;
//comparableClassFor:如果k的类实现了Comparable，
//那么返回k的类，否则返回null。
//compareComparables:如果x匹配kc (k的筛选比较类)，
//则返回k. compareto (x)，否则0。
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
//将遍历根节点赋值给xp。
TreeNode<K,V> xp = 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;
}
}
}
}
//将根节点设置为链表的第一个节点。
moveRootToFront(tab, root);
}
查找指定节点
//使用给定的散列和键从根p开始查找节点。
//kc参数在第一次使用比较键时缓存comparableClassFor(key)。
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
//当前节点。
TreeNode<K,V> p = this;
do {
int ph, dir; K pk;
//pl--左孩子，pr--右孩子。
TreeNode<K,V> pl = p.left, pr = p.right, q;
//当前节点的hash大于指定的hash。
if ((ph = p.hash) > h)
//将左孩子赋值给当前节点。
p = pl;
//当前节点的hash小于指定的hash。
else if (ph < h)
//将右孩子赋值给当前节点。
p = pr;
//如果key相等
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//返回当前节点。
return p;
//如果左孩子不存在。
else if (pl == null)
//将右孩子赋值给当前节点。
p = pr;
//如果右孩子不存在。
else if (pr == null)
//将左孩子赋值给当前节点。
p = pl;
//比较key的类
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;
}
//获取红黑树的根节点。
final TreeNode<K,V> root() {
//从当前节点遍历寻找，直到找到父节点不存在的节点。
for (TreeNode<K,V> r = this, p;;) {
if ((p = r.parent) == null)
return r;
r = p;
}
}
final TreeNode<K,V> getTreeNode(int h, Object k) {
return ((parent != null) ? root() : this).find(h, k, null);
}
插入树节点
//插入树节点。
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;
//从根节点开始遍历。
for (TreeNode<K,V> p = root;;) {
int dir, ph; K pk;
//p的hash大于插入节点的hash。
if ((ph = p.hash) > h)
dir = -1;
//p的hash小于插入节点的hash。
else if (ph < h)
dir = 1;
//p的hash等于插入节点的hash且key值相等。
else if ((pk = p.key) == k || (k != null && k.equals(pk)))
//返回p。
return p;
//比较key的类。
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0) {
if (!searched) {
TreeNode<K,V> q, ch;
searched = true;
//(p的左孩子存在,且找到key为k的节点）或者（p的右孩子存在,且找到key为k的节点）
if (((ch = p.left) != null &&
(q = ch.find(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.find(h, k, kc)) != null))
//返回q。
return q;
}
dir = tieBreakOrder(k, pk);
}
//将p赋值给新建节点的父节点。
TreeNode<K,V> xp = p;
//如果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;
//插入节点之后重新平衡，且将红黑树的根节点设置桶的第一个节点。
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
删除树节点
//删除当前树节点。
//map--map, tab--map的数组,movable--
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
//如果数组为空或者数组长度为0。
if (tab == null || (n = tab.length) == 0)
return;
//计算当前节点的数组下标。
int index = (n - 1) & hash;
//获取index的第一个节点，以第一个节点为root节点。
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
//prev--当前的前一个节点，next--当前节点的下一个节点。
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
//如果前一个节点不存在，那么当前节点就是第一个节点。
//将后一个节点挪到第一个位置。
if (pred == null)
tab[index] = first = succ;
//如果前面节点存在。
else
//建立后一个节点和前一个节点的前后关系。
pred.next = succ;
if (succ != null)
succ.prev = pred;
//如果第一个节点不存在，直接返回。
if (first == null)
return;
//如果根节点的父节点存在，重新获取新的根节点。
if (root.parent != null)
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为当前节点，pl当前节点的左孩子，pr当前节点的右孩子。
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
//当前节点的左孩子和右孩子都存在。
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
//从当前节点的左孙子开始往后查找，直到找到左孩子不存在的节点。
while ((sl = s.left) != null) // find successor
s = sl;
//当前节点的和左孩子为空的节点交换颜色。
boolean c = s.red; s.red = p.red; p.red = c; // swap colors
//sr--左孩子为空的节点的右孩子，pp--当前节点的父节点。
TreeNode<K,V> sr = s.right;
TreeNode<K,V> pp = p.parent;
//如果左孩子为空的节点就是当前节点的前一个节点。
if (s == pr) { // p was s's direct parent
//设置s与当前节点的父子关系。
p.parent = s;
s.right = p;
}
//如果左孩子为空的节点不是当前节点的前一个节点。
else {
TreeNode<K,V> sp = s.parent;
//用s替换删除节点。
if ((p.parent = sp) != null) {
//s是左节点。
if (s == sp.left)
sp.left = p;
//s是右节点。
else
sp.right = p;
}
//建立s与前节点的前一个节点之间的父子关系。
if ((s.right = pr) != null)
pr.parent = s;
}
p.left = null;
//建立当前节点p与sr的父子关系。
if ((p.right = sr) != null)
sr.parent = p;
//建立s与当前节点的左孩子的父子关系。
if ((s.left = pl) != null)
pl.parent = s;
//当前节点的父节点不存在，设置s为根节点。
if ((s.parent = pp) == null)
root = s;
//当前节点的父节点存在，设置s与当前父节点的左右关系。
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
///将左孩子为空的兄弟节点赋值给replacement，否则当前节点赋值给replacement。
if (sr != null)
replacement = sr;
else
replacement = p;
}
//如果当前节点的左孩子存在
else if (pl != null)
//那么replacement为左孩子。
replacement = pl;
//如果当前节点的右孩子存在。
else if (pr != null)
//那么replacement为右孩子。
replacement = pr;
else
//否则，replacement为当前节点。
replacement = p;
//当前节点不是replacement。
if (replacement != p) {
TreeNode<K,V> pp = replacement.parent = p.parent;
//当前节点父节点不存在。
if (pp == null)
//replacement设置为根节点。
root = replacement;
//当前节点是父节点的左孩子。
else if (p == pp.left)
//replacement设置为父节点的左孩子。
pp.left = replacement;
else
//replacement设置为父节点的右孩子。
pp.right = replacement;
//便于GC。
p.left = p.right = p.parent = null;
}
//如果p为红色，那么设置为根节点，否则以执行删除时候的重新平衡。
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//replacement为当前节点,设置相应的字段为空，便于GC。
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)
//将红黑树的根节点设置为索引位置的第一个节点。
moveRootToFront(tab, r);
}
拆分：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
//将树节点分成高节点和低节点，或者如果树节点太少了，将红黑树转化为链表。
//只有resize会调用本方法。
//@param map the map
//@param tab the table for recording bin heads
//@param index table被拆开的索引位置。
//@param bit the bit of hash to split on
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
//将当前节点赋值给b。
TreeNode<K,V> b = this;
//重新建立高节点和低节点集合的关联关系，保持原有的节点的顺序。
//
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+1的倍数。
if ((e.hash & bit) == 0) {
//如果低位的尾结点为空。
if ((e.prev = loTail) == null)
//将当前节点设置为低位链表的第一个节点。
loHead = e;
else
//否则将当前节点添加到低位链表的最后。
loTail.next = e;
//将当前节点设置为新的尾结点
loTail = e;
//低位链表数量加1。
++lc;
}
//否则，这个节点应该加入高位链表。
else {
//如果高位链表的尾结点为空。
if ((e.prev = hiTail) == null)
//将当前节点设置高位的第一个节点。
hiHead = e;
else
//否则添加到高位链表的末尾。
hiTail.next = e;
//将当前节点设置为新的尾结点
hiTail = e;
//低位链表数量加1。
++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 {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
