final void deleteTreeNode(TreeNode p){
  TreeNode next=(TreeNode)p.next;
  TreeNode pred=p.prev;
  if (pred == null)   first=next;
 else   pred.next=next;
  if (next != null)   next.prev=pred;
  TreeNode replacement;
  TreeNode pl=p.left;
  TreeNode pr=p.right;
  if (pl != null && pr != null) {
    TreeNode s=pr, sl;
    while ((sl=s.left) != null)     s=sl;
    boolean c=s.red;
    s.red=p.red;
    p.red=c;
    TreeNode sr=s.right;
    TreeNode pp=p.parent;
    if (s == pr) {
      p.parent=s;
      s.right=p;
    }
 else {
      TreeNode 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)     root=s;
 else     if (p == pp.left)     pp.left=s;
 else     pp.right=s;
    replacement=sr;
  }
 else   replacement=(pl != null) ? pl : pr;
  TreeNode pp=p.parent;
  if (replacement == null) {
    if (pp == null) {
      root=null;
      return;
    }
    replacement=p;
  }
 else {
    replacement.parent=pp;
    if (pp == null)     root=replacement;
 else     if (p == pp.left)     pp.left=replacement;
 else     pp.right=replacement;
    p.left=p.right=p.parent=null;
  }
  if (!p.red) {
    TreeNode x=replacement;
    while (x != null) {
      TreeNode xp, xpl;
      if (x.red || (xp=x.parent) == null) {
        x.red=false;
        break;
      }
      if (x == (xpl=xp.left)) {
        TreeNode sib=xp.right;
        if (sib != null && sib.red) {
          sib.red=false;
          xp.red=true;
          rotateLeft(xp);
          sib=(xp=x.parent) == null ? null : xp.right;
        }
        if (sib == null)         x=xp;
 else {
          TreeNode sl=sib.left, sr=sib.right;
          if ((sr == null || !sr.red) && (sl == null || !sl.red)) {
            sib.red=true;
            x=xp;
          }
 else {
            if (sr == null || !sr.red) {
              if (sl != null)               sl.red=false;
              sib.red=true;
              rotateRight(sib);
              sib=(xp=x.parent) == null ? null : xp.right;
            }
            if (sib != null) {
              sib.red=(xp == null) ? false : xp.red;
              if ((sr=sib.right) != null)               sr.red=false;
            }
            if (xp != null) {
              xp.red=false;
              rotateLeft(xp);
            }
            x=root;
          }
        }
      }
 else {
        TreeNode sib=xpl;
        if (sib != null && sib.red) {
          sib.red=false;
          xp.red=true;
          rotateRight(xp);
          sib=(xp=x.parent) == null ? null : xp.left;
        }
        if (sib == null)         x=xp;
 else {
          TreeNode sl=sib.left, sr=sib.right;
          if ((sl == null || !sl.red) && (sr == null || !sr.red)) {
            sib.red=true;
            x=xp;
          }
 else {
            if (sl == null || !sl.red) {
              if (sr != null)               sr.red=false;
              sib.red=true;
              rotateLeft(sib);
              sib=(xp=x.parent) == null ? null : xp.left;
            }
            if (sib != null) {
              sib.red=(xp == null) ? false : xp.red;
              if ((sl=sib.left) != null)               sl.red=false;
            }
            if (xp != null) {
              xp.red=false;
              rotateRight(xp);
            }
            x=root;
          }
        }
      }
    }
  }
  if (p == replacement && (pp=p.parent) != null) {
    if (p == pp.left)     pp.left=null;
 else     if (p == pp.right)     pp.right=null;
    p.parent=null;
  }
}

final void deleteTreeNode ( TreeNode p ) { TreeNode next = ( TreeNode ) p . next ; TreeNode pred = p . prev ; if ( pred == null ) first = next ; else pred . next = next ; if ( next != null ) next . prev = pred ; TreeNode replacement ; TreeNode pl = p . left ; TreeNode pr = p . right ; if ( pl != null && pr != null ) { TreeNode s = pr , sl ; while ( ( sl = s . left ) != null ) s = sl ; boolean c = s . red ; s . red = p . red ; p . red = c ; TreeNode sr = s . right ; TreeNode pp = p . parent ; if ( s == pr ) { p . parent = s ; s . right = p ; } else { TreeNode 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 ) root = s ; else if ( p == pp . left ) pp . left = s ; else pp . right = s ; replacement = sr ; } else replacement = ( pl != null ) ? pl : pr ; TreeNode pp = p . parent ; if ( replacement == null ) { if ( pp == null ) { root = null ; return ; } replacement = p ; } else { replacement . parent = pp ; if ( pp == null ) root = replacement ; else if ( p == pp . left ) pp . left = replacement ; else pp . right = replacement ; p . left = p . right = p . parent = null ; } if ( ! p . red ) { TreeNode x = replacement ; while ( x != null ) { TreeNode xp , xpl ; if ( x . red || ( xp = x . parent ) == null ) { x . red = false ; break ; } if ( x == ( xpl = xp . left ) ) { TreeNode sib = xp . right ; if ( sib != null && sib . red ) { sib . red = false ; xp . red = true ; rotateLeft ( xp ) ; sib = ( xp = x . parent ) == null ? null : xp . right ; } if ( sib == null ) x = xp ; else { TreeNode sl = sib . left , sr = sib . right ; if ( ( sr == null || ! sr . red ) && ( sl == null || ! sl . red ) ) { sib . red = true ; x = xp ; } else { if ( sr == null || ! sr . red ) { if ( sl != null ) sl . red = false ; sib . red = true ; rotateRight ( sib ) ; sib = ( xp = x . parent ) == null ? null : xp . right ; } if ( sib != null ) { sib . red = ( xp == null ) ? false : xp . red ; if ( ( sr = sib . right ) != null ) sr . red = false ; } if ( xp != null ) { xp . red = false ; rotateLeft ( xp ) ; } x = root ; } } } else { TreeNode sib = xpl ; if ( sib != null && sib . red ) { sib . red = false ; xp . red = true ; rotateRight ( xp ) ; sib = ( xp = x . parent ) == null ? null : xp . left ; } if ( sib == null ) x = xp ; else { TreeNode sl = sib . left , sr = sib . right ; if ( ( sl == null || ! sl . red ) && ( sr == null || ! sr . red ) ) { sib . red = true ; x = xp ; } else { if ( sl == null || ! sl . red ) { if ( sr != null ) sr . red = false ; sib . red = true ; rotateLeft ( sib ) ; sib = ( xp = x . parent ) == null ? null : xp . left ; } if ( sib != null ) { sib . red = ( xp == null ) ? false : xp . red ; if ( ( sl = sib . left ) != null ) sl . red = false ; } if ( xp != null ) { xp . red = false ; rotateRight ( xp ) ; } x = root ; } } } } } if ( p == replacement && ( pp = p . parent ) != null ) { if ( p == pp . left ) pp . left = null ; else if ( p == pp . right ) pp . right = null ; p . parent = null ; } }
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 of lock . so instead we swap the tree linkages .
