boolean (TreeNode<V> p) { TreeNode<V> next = (TreeNode<V>)p.next; TreeNode<V> pred = p.prev; // unlink traversal pointers TreeNode<V> r, rl; if (pred == null) { first = next; } else { pred.next = next; } if (next != null) { next.prev = pred; } if (first == null) { root = null; return true; } if ((r = root) == null || r.right == null || // too small (rl = r.left) == null || rl.left == null) { return true; } lockRoot(); try { TreeNode<V> replacement; TreeNode<V> pl = p.left; TreeNode<V> pr = p.right; if (pl != null && pr != null) { TreeNode<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 TreeNode<V> sr = s.right; TreeNode<V> pp = p.parent; if (s == pr) { // p was s's direct parent p.parent = s; s.right = p; } else { TreeNode<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; } } p.left = null; if ((p.right = sr) != null) { sr.parent = p; } if ((s.left = pl) != null) { pl.parent = s; } if ((s.parent = pp) == null) { r = s; } else if (p == pp.left) { pp.left = s; } else { pp.right = s; } if (sr != null) { replacement = sr; } else { replacement = p; } } else if (pl != null) { replacement = pl; } else if (pr != null) { replacement = pr; } else { replacement = p; } if (replacement != p) { TreeNode<V> pp = replacement.parent = p.parent; if (pp == null) { r = replacement; } else if (p == pp.left) { pp.left = replacement; } else { pp.right = replacement; } p.left = p.right = p.parent = null; } root = (p.red) ? r : balanceDeletion(r, replacement); if (p == replacement) { // detach pointers TreeNode<V> pp; if ((pp = p.parent) != null) { if (p == pp.left) { pp.left = null; } else if (p == pp.right) { pp.right = null; } p.parent = null; } } } finally { unlockRoot(); } assert checkInvariants(root); return false; }