def insert(self, value, key):
<EOL>if self is NULL:<EOL><INDENT>return Node(value, NULL, NULL, True), True<EOL><DEDENT>direction = cmp(key(value), key(self.value))<EOL>if direction < <NUM_LIT:0>:<EOL><INDENT>left, insertion = self.left.insert(value, key)<EOL>self = self._replace(left=left)<EOL><DEDENT>elif direction > <NUM_LIT:0>:<EOL><INDENT>right, insertion = self.right.insert(value, key)<EOL>self = self._replace(right=right)<EOL><DEDENT>elif direction == <NUM_LIT:0>:<EOL><INDENT>self = self._replace(value=value)<EOL>insertion = False<EOL><DEDENT>return self.balance(), insertion<EOL>
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.