docs: 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