private final BinTreeNode < K , V > extract_next ( BinTreeNode < K , V > node ) { BinTreeNode < K , V > prev = node . right ; BinTreeNode < K , V > curr = prev . left ; if ( curr == null ) { node . right = node . right . right ; return prev ; } while ( curr . left != null ) { prev = curr ; curr = curr . left ; } prev . left = curr . right ; return curr ; }
removes it from that subtree and returns it .