Insert a value into a tree rooted at the given node, and return
        whether this was an insertion or update.

        Balances the tree during insertion.

        An update is performed instead of an insertion if a value in the tree
        compares equal to the new value.

def insert(self, value, key):
        """
        Insert a value into a tree rooted at the given node, and return
        whether this was an insertion or update.

        Balances the tree during insertion.

        An update is performed instead of an insertion if a value in the tree
        compares equal to the new value.
        """

        # Base case: Insertion into the empty tree is just creating a new node
        # with no children.
        if self is NULL:
            return Node(value, NULL, NULL, True), True

        # Recursive case: Insertion into a non-empty tree is insertion into
        # whichever of the two sides is correctly compared.
        direction = cmp(key(value), key(self.value))
        if direction < 0:
            left, insertion = self.left.insert(value, key)
            self = self._replace(left=left)
        elif direction > 0:
            right, insertion = self.right.insert(value, key)
            self = self._replace(right=right)
        elif direction == 0:
            # Exact hit on an existing node (this node, in fact). In this
            # case, perform an update.
            self = self._replace(value=value)
            insertion = False

        # And balance on the way back up.
        return self.balance(), insertion