def delete(self, value, key):
<EOL>if self is NULL:<EOL><INDENT>raise KeyError(value)<EOL><DEDENT>direction = cmp(key(value), key(self.value))<EOL>if direction < <NUM_LIT:0>:<EOL><INDENT>if (not self.left.red and<EOL>self.left is not NULL and<EOL>not self.left.left.red):<EOL><INDENT>self = self.move_red_left()<EOL><DEDENT>left = self.left.delete(value, key)<EOL>self = self._replace(left=left)<EOL><DEDENT>else:<EOL><INDENT>if self.left.red:<EOL><INDENT>self = self.rotate_right()<EOL><DEDENT>if direction == <NUM_LIT:0> and self.right is NULL:<EOL><INDENT>return NULL<EOL><DEDENT>if (not self.right.red and<EOL>self.right is not NULL and<EOL>not self.right.left.red):<EOL><INDENT>self = self.move_red_right()<EOL><DEDENT>if direction > <NUM_LIT:0>:<EOL><INDENT>right = self.right.delete(value, key)<EOL>self = self._replace(right=right)<EOL><DEDENT>else:<EOL><INDENT>rnode = self.right<EOL>while rnode is not NULL:<EOL><INDENT>rnode = rnode.left<EOL><DEDENT>right, replacement = self.right.delete_min()<EOL>self = self._replace(value=replacement, right=right)<EOL><DEDENT><DEDENT>return self.balance()<EOL>
Delete a value from a tree.