Balance a node.

        The balance is inductive and relies on all subtrees being balanced
        recursively or by construction. If the subtrees are not balanced, then
        this will not fix them.

def balance(self):
        """
        Balance a node.

        The balance is inductive and relies on all subtrees being balanced
        recursively or by construction. If the subtrees are not balanced, then
        this will not fix them.
        """

        # Always lean left with red nodes.
        if self.right.red:
            self = self.rotate_left()

        # Never permit red nodes to have red children. Note that if the left-hand
        # node is NULL, it will short-circuit and fail this test, so we don't have
        # to worry about a dereference here.
        if self.left.red and self.left.left.red:
            self = self.rotate_right()

        # Finally, move red children on both sides up to the next level, reducing
        # the total redness.
        if self.left.red and self.right.red:
            self = self.flip()

        return self