TreeMap插入
public V put(K key, V value) {
Entry<K,V> t = root;
// root为null，新建节点设置为root
if (t == null) {
compare(key, key); // type (and possibly null) check
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
int cmp;
Entry<K,V> parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
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 {
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);
}
// 插入节点
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
// 插入修正
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
private void fixAfterInsertion(Entry<K,V> x) {
// 因创建的新节点默认是黑色，这里要改成红色
x.color = RED;
// 节点为null或root或父节点为黑色时，不再循环(此处x其实不会为null)
while (x != null && x != root && x.parent.color == RED) {
// 循环内，父节点一定是红色，祖父节点一定是黑色
// 当前节点的父节点是左节点时
if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
// y指向叔叔节点
Entry<K,V> y = rightOf(parentOf(parentOf(x)));
// 叔叔节点为红色
if (colorOf(y) == RED) {
// 祖父节点与父节点和叔叔节点交换颜色
setColor(parentOf(x), BLACK);
setColor(y, BLACK);
setColor(parentOf(parentOf(x)), RED);
// 祖父节点变红色后，需以祖父节点为当前节点继续判断是否有两个红色节点相连的情况
x = parentOf(parentOf(x));
// 叔叔节点为黑色(包含为null叶子节点的情况)
} else {
// 当前节点是父节点的右子节点
if (x == rightOf(parentOf(x))) {
// 以父节点为支点左旋
x = parentOf(x);
rotateLeft(x);
}
// 父节点置为黑色，祖父节点置为红色，并右旋
setColor(parentOf(x), BLACK);
setColor(parentOf(parentOf(x)), RED);
rotateRight(parentOf(parentOf(x)));
// 变色加右旋后，已满足条件，不需继续循环
}
// 当前节点的父节点是右节点时，镜像处理即可
} else {
...
}
}
// 最后将root设置为黑色
root.color = BLACK;
}
TreeMap删除
public V remove(Object key) {
// 先查找
Entry<K,V> p = getEntry(key);
if (p == null)
return null;
V oldValue = p.value;
// 找到了，再删除
deleteEntry(p);
return oldValue;
}
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
// If strictly internal, copy successor's element to p and then make p
// point to successor.
// 有两个子节点，则需转化
if (p.left != null && p.right != null) {
// 找后继节点
Entry<K,V> s = successor(p);
// 将后继节点的key和value赋值给当前节点
p.key = s.key;
p.value = s.value;
// p指向后继节点，即为交换当前节点和后继节点，转化为只有一个子节点和没有子节点的情况
p = s;
} // p has 2 children
// Start fixup at replacement node, if it exists.
// 只有一个子节点replacement指向子节点，没有子节点replacement为null
Entry<K,V> replacement = (p.left != null ? p.left : p.right);
// replacement不为null，即为有一个子节点，此时只有一种情况，p为黑色，replacement为红色
if (replacement != null) {
// Link replacement to parent
// replacement连接父节点
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;
// Null out links so they are OK to use by fixAfterDeletion.
// 清除当前节点的连接
p.left = p.right = p.parent = null;
// Fix replacement
// 此处其实p一定是黑色，只需将replacement置为黑色
if (p.color == BLACK)
fixAfterDeletion(replacement);
} else if (p.parent == null) { // return if we are the only node.
// p原为root节点
root = null;
} else { // No children. Use self as phantom replacement and unlink.
// 没有子节点时，当前节点是黑色，需要调整
if (p.color == BLACK)
fixAfterDeletion(p);
// 最后删除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;
}
}
}
private void fixAfterDeletion(Entry<K,V> x) {
// 节点为黑色，非root时，才要循环
while (x != root && colorOf(x) == BLACK) {
// x是左节点
if (x == leftOf(parentOf(x))) {
// sib指向兄弟节点
Entry<K,V> sib = rightOf(parentOf(x));
// 兄弟节点是红色时
if (colorOf(sib) == RED) {
setColor(sib, BLACK);
setColor(parentOf(x), RED);
// 左旋，转化成兄弟节点为黑色的情况
rotateLeft(parentOf(x));
// sib指向新的兄弟节点，继续按其他情况处理
sib = rightOf(parentOf(x));
}
// 兄弟节点的两个子节点都是黑色时，包括子节点为null的情况，隐含信息：兄弟节点也为黑色
if (colorOf(leftOf(sib)) == BLACK &&
colorOf(rightOf(sib)) == BLACK) {
// 相当于将节点和兄弟节点都变红色，x指向父节点，当父节点是红色时，退出循环并变为黑色，父节点是黑色时，则再循环处理
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退出循环
x = root;
}
// x是右节点，镜像处理
} else { // symmetric
...
}
}
setColor(x, BLACK);
}
HashMap插入
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;
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) {
// comparableClassFor是判断k所属类是否实现了Comparable接口，实现了则返回k所属类
// compareComparables是用Comparable接口的方法比较k和pk两个对象
// 没实现Comparable接口，则用tieBreakOrder方法来判断，或者实现了Comparable接口但是判断结果等于0，还是用tieBreakOrder方法来判断
if (!searched) {
// 第一次进入这个else if分支的时候，会去当前节点左右子树都找一遍，找到了返回节点，整个循环只会找一次
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;
}
// hash值和Comparable接口的方法（如果有的话）都对比相等，但是key不相等时，用System.identityHashCode()来进行对比
dir = tieBreakOrder(k, pk);
}
// 上面是查找，找到了会返回节点，到方法外面设置新值，没找到往下继续
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;
// 调整红黑树，并调整双向链表
moveRootToFront(tab, balanceInsertion(root, x));
return null;
}
}
}
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;;) {
// 父节点为null，说明当前节点是根节点，置为红色，并返回当前节点
if ((xp = x.parent) == null) {
x.red = false;
return x;
}
// 父节点是黑色，或父节点是根节点，返回root
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);
// x，xp，xpp重新赋值
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 {
...
}
}
}
HashMap删除
final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
boolean movable) {
int n;
// 数组为空，肯定无红黑树，直接返回
if (tab == null || (n = tab.length) == 0)
return;
// 计算数组中的下标
int index = (n - 1) & hash;
TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
// 从双向链表中删除当前节点
if (pred == null)
// 当前节点在双向链表的头部，先将tab[index]和first指向双向链表的第二个节点
tab[index] = first = succ;
else
// 当前节点不是双向链表的头部，将前面节点的next指向后面节点
pred.next = succ;
if (succ != null)
// 后面节点不是null，即为当前节点不是尾节点，后面节点的prev指向前面节点
succ.prev = pred;
if (first == null)
// first为null直接返回，只有两种情况，tab[index]一开始为空或从双向链表中删除头节点后tab[index]为空，即为双向链表一开始就是空的，或删除当前节点后为空链表
return;
if (root.parent != null)
// root重新定位到红黑树的根节点（如果当前节点是根节点，上面操作后tab[index]不再指向根节点 tab[index] = first = succ;）
root = root.root();
if (root == null
|| (movable
&& (root.right == null
|| (rl = root.left) == null
|| rl.left == null))) {
// root为null，或root右孩子为null，或root左孩子为null，或root左孩子的左孩子为null，此处未用到去树化阈值UNTREEIFY_THRESHOLD
// 双链表转单链表，即为红黑树转单链表
tab[index] = first.untreeify(map); // too small
return;
}
TreeNode<K,V> p = this, pl = left, pr = right, replacement;
// 当前节点有两个子节点时
if (pl != null && pr != null) {
TreeNode<K,V> s = pr, sl;
// 找到后继节点s
while ((sl = s.left) != null) // find successor
s = sl;
// p和s交换颜色
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;
// p和s交换位置
if (s == pr) { // p was s's direct parent
// 两者相邻时，父子关系转换
p.parent = s;
s.right = p;
}
else {
// 两者不相邻，交换各自的关系
TreeNode<K,V> sp = s.parent;
if ((p.parent = sp) != null) {
if (s == sp.left)
sp.left = p;
else
sp.right = p;
}
if ((s.right = pr) != null)
pr.parent = s;
}
// sl肯定是null，因此需将p.left置为null
p.left = null;
if ((p.right = sr) != null)
sr.parent = p;
if ((s.left = pl) != null)
pl.parent = s;
if ((s.parent = pp) == null)
// p没有父节点时，将root指向s
root = s;
else if (p == pp.left)
pp.left = s;
else
pp.right = s;
if (sr != null)
// 交换后p的子节点不为空，replacement指向子节点
replacement = sr;
else
// 子节点为空，replacement指向p
replacement = p;
}
// 右子节点为空，左子节点不为空，replacement指向左子节点
else if (pl != null)
replacement = pl;
// 左子节点为空，右子节点不为空，replacement指向右子节点
else if (pr != null)
replacement = pr;
// 子节点为空，replacement指向p
else
replacement = p;
if (replacement != p) {
// p有子节点，先删除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.left = p.right = p.parent = null;
}
// 平衡操作
TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
// p没有子节点，先平衡操作，再删除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)
moveRootToFront(tab, r);
}
static <K,V> TreeNode<K,V> balanceDeletion(TreeNode<K,V> root,
TreeNode<K,V> x) {
for (TreeNode<K,V> xp, xpl, xpr;;) {
// 当前节点为null 或 root 直接返回 root
if (x == null || x == root)
return root;
else if ((xp = x.parent) == null) {
// 父节点为null，当前节点置为黑色，返回当前节点
x.red = false;
return x;
}
else if (x.red) {
// 当前节点是红色时，置为黑色，返回root
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;
}
// 兄弟节点为null，以父节点为当前节点重新处理(会有这种情况吗？原始的单子节点的情况下，节点颜色必定是红色，上面已拦截，其他情况也不会转换为这种情况)
if (xpr == null)
x = xp;
else {
TreeNode<K,V> sl = xpr.left, sr = xpr.right;
// 两个侄子节点都不为红色时，隐含信息：兄弟节点为黑色
if ((sr == null || !sr.red) &&
(sl == null || !sl.red)) {
// 将黑色借给父节点，再以父节点为当前节点继续，此处可能去到else if (x.red)分支
xpr.red = true;
x = xp;
}
// 有一个侄子节点为红色的情况
else {
// 右侄子不为红色时，隐含信息：左侄子为红色
if (sr == null || !sr.red) {
// 此处多余判断，sl == null 会进入上面分支，sl一定为红色
if (sl != null)
sl.red = false;
xpr.red = true;
// 右旋，转化成右侄子为红色的情况
root = rotateRight(root, xpr);
// xpr指向新的兄弟节点
xpr = (xp = x.parent) == null ?
null : xp.right;
}
// 兄弟节点不为null时，其实兄弟节点在这里不会为null，xp父节点也不会为null，sr右侄子也不会为null，且一定是红色
if (xpr != null) {
xpr.red = (xp == null) ? false : xp.red;
if ((sr = xpr.right) != null)
// 将父节点的颜色给兄弟节点，将右侄子的颜色设置成黑色
sr.red = false;
}
// xp不会为null
if (xp != null) {
// 父节点设置为黑色，左旋
xp.red = false;
root = rotateLeft(root, xp);
}
x = root;
}
}
}
// 当前节点时右节点时，镜像处理
else {
...
}
}
}
