Delete a value from a tree.

def delete(self, value, key):
        """
        Delete a value from a tree.
        """

        # Base case: The empty tree cannot possibly have the desired value.
        if self is NULL:
            raise KeyError(value)

        direction = cmp(key(value), key(self.value))

        # Because we lean to the left, the left case stands alone.
        if direction < 0:
            if (not self.left.red and
                self.left is not NULL and
                not self.left.left.red):
                self = self.move_red_left()
            # Delete towards the left.
            left = self.left.delete(value, key)
            self = self._replace(left=left)
        else:
            # If we currently lean to the left, lean to the right for now.
            if self.left.red:
                self = self.rotate_right()

            # Best case: The node on our right (which we just rotated there) is a
            # red link and also we were just holding the node to delete. In that
            # case, we just rotated NULL into our current node, and the node to
            # the right is the lone matching node to delete.
            if direction == 0 and self.right is NULL:
                return NULL

            # No? Okay. Move more reds to the right so that we can continue to
            # traverse in that direction. At *this* spot, we do have to confirm
            # that node.right is not NULL...
            if (not self.right.red and
                self.right is not NULL and
                not self.right.left.red):
                self = self.move_red_right()

            if direction > 0:
                # Delete towards the right.
                right = self.right.delete(value, key)
                self = self._replace(right=right)
            else:
                # Annoying case: The current node was the node to delete all
                # along! Use a right-handed minimum deletion. First find the
                # replacement value to rebuild the current node with, then delete
                # the replacement value from the right-side tree. Finally, create
                # the new node with the old value replaced and the replaced value
                # deleted.
                rnode = self.right
                while rnode is not NULL:
                    rnode = rnode.left

                right, replacement = self.right.delete_min()
                self = self._replace(value=replacement, right=right)

        return self.balance()