private void doRedBlackDelete ( final Node < K , V > deletedNode ) { for ( int index = FIRST_INDEX ; index < NUMBER_OF_INDICES ; index ++ ) { // if deleted node has both left and children, swap with // the next greater node if ( ( deletedNode . getLeft ( index ) != null ) && ( deletedNode . getRight ( index ) != null ) ) { swapPosition ( nextGreater ( deletedNode , index ) , deletedNode , index ) ; } Node < K , V > replacement = ( ( deletedNode . getLeft ( index ) != null ) ? deletedNode . getLeft ( index ) : deletedNode . getRight ( index ) ) ; if ( replacement != null ) { replacement . setParent ( deletedNode . getParent ( index ) , index ) ; if ( deletedNode . getParent ( index ) == null ) { rootNode [ index ] = replacement ; } else if ( deletedNode == deletedNode . getParent ( index ) . getLeft ( index ) ) { deletedNode . getParent ( index ) . setLeft ( replacement , index ) ; } else { deletedNode . getParent ( index ) . setRight ( replacement , index ) ; } deletedNode . setLeft ( null , index ) ; deletedNode . setRight ( null , index ) ; deletedNode . setParent ( null , index ) ; if ( isBlack ( deletedNode , index ) ) { doRedBlackDeleteFixup ( replacement , index ) ; } } else { // replacement is null if ( deletedNode . getParent ( index ) == null ) { // empty tree rootNode [ index ] = null ; } else { // deleted node had no children if ( isBlack ( deletedNode , index ) ) { doRedBlackDeleteFixup ( deletedNode , index ) ; } if ( deletedNode . getParent ( index ) != null ) { if ( deletedNode == deletedNode . getParent ( index ) . getLeft ( index ) ) { deletedNode . getParent ( index ) . setLeft ( null , index ) ; } else { deletedNode . getParent ( index ) . setRight ( null , index ) ; } deletedNode . setParent ( null , index ) ; } } } } shrink ( ) ; }
complicated red - black delete stuff . Based on Sun s TreeMap implementation though it s barely recognizable any more