- /**
- * Removes the given node, that must be present before this call.
- * This is messier than typical red-black deletion code because we
- * cannot swap the contents of an interior node with a leaf
- * successor that is pinned by "next" pointers that are accessible
- * independently during traversal. So instead we swap the tree
- * linkages. If the current tree appears to have too few nodes,
- * the bin is converted back to a plain bin. (The test triggers
- * somewhere between 2 and 6 nodes, depending on tree structure).
- * 移除给定的结点, 这个方法相比一般的红黑树删除更加杂乱, 因为我们无法交换内部结点的内容他们被 next 指针给限制了, 这个指针是在遍历的时候独立的.
- * 因此我们交换树的连接. 如果当前的树结点太少, 需要转换为线性链表, 通常这个值设定为 2-6 个结点
- */
- 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;//index = hash mod n
- TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
- TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;//succ 指向要删除结点的后一个点, pred 指向要删除结点的前一个
- if (pred == null)
- tab[index] = first = succ;// 若要删除的结点的前一个为空, 则 first 和 tab[index] 都指向要删除结点的后一个结点
- else
- pred.next = succ;// 若要删除结点的前驱非空, 则前一个结点的 next 指针指向该结点的后驱
- if (succ != null)
- succ.prev = pred;// 后驱结点不为空时, 后驱结点的前置指针设为删除结点的前置结点
- if (first == null)
- 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); // 根自身或者左右儿子其中一个为空说明结点数过少 (不超过 2) 转为线性表并结束
- return;
- }
- TreeNode<K,V> p = this, pl = left, pr = right, replacement;//p 指向要删除的结点
- if (pl != null && pr != null) {
- TreeNode<K,V> s = pr, sl;
- while ((sl = s.left) != null) // 删除结点的左右儿子都不为空时, 寻找右子树中最左的叶结点作为后继, s 指向这个后继结点
- s = sl;
- boolean c = s.red; s.red = p.red; p.red = c; // 交换后继结点和要删除结点的颜色
- TreeNode<K,V> sr = s.right;
- TreeNode<K,V> pp = p.parent;
- if (s == pr) {
- p.parent = s;//p 是 s 的直接右儿子, 交换 p 和 s 的位置
- s.right = p;
- }
- else {
- TreeNode<K,V> sp = s.parent;
- if ((p.parent = sp) != null) {
- if (s == sp.left)
- sp.left = p;//p 放到 s 原本的位置
- else
- sp.right = p;
- }
- if ((s.right = pr) != null)
- pr.parent = s;//s 放到 p 原本的位置
- }
- p.left = null;
- if ((p.right = sr) != null)
- sr.parent = p;//s 原本的右子树成为 p 的右子树
- if ((s.left = pl) != null)
- pl.parent = s;//s 原本的左子树成为 p 的左子树
- if ((s.parent = pp) == null)
- root = s;// 若 p 原本是根则新的根是 s
- else if (p == pp.left)
- pp.left = s;// 若 p 是某个结点的左儿子, 则 s 成为该结点的左儿子
- else
- pp.right = s;// 若 p 是某个结点的右儿子, 则 s 成为该结点的右儿子
- if (sr != null)// 若 s 结点有右儿子 (s 一定没有左儿子), 则 replacement 为这个右儿子否则为 p
- replacement = sr;
- else
- replacement = p;
- }
- else if (pl != null)// 若 p 的左右儿子有一方为 null, 则 replacement 为非空的一方, 否则为 p 自己
- replacement = pl;
- else if (pr != null)
- replacement = pr;
- else
- replacement = p;
- if (replacement != p) {//p 有儿子或者 s 有儿子
- TreeNode<K,V> pp = replacement.parent = p.parent;
- if (pp == null)// 用 replacement 来替换 p
- root = replacement;
- else if (p == pp.left)
- pp.left = replacement;
- else
- pp.right = replacement;
- p.left = p.right = p.parent = null;// 移除 p 结点
- }
- // 以 replacement 为中心, 进行红黑树性质的修复, replacement 可能为 s 的右儿子或者 p 的儿子或者 p 自己
- TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
- if (replacement == p) { //p 没有儿子或者 s 没有儿子, 直接移除 p
- 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);// 整理根结点
- }
来源: https://www.cnblogs.com/graywind/p/9471756.html