public void removeKey ( int key ) { if ( key == first . value ) { removeMin ( ) ; return ; } if ( key == last . value ) { removeMax ( ) ; return ; } // if both children of root are black, set root to red if ( ( root . left == null || ! root . left . red ) && ( root . right == null || ! root . right . red ) ) root . red = true ; root = removeKey ( root , key ) ; if ( root != null ) root . red = false ; }
Remove the given key . The key MUST exists else the tree won t be valid anymore .