code: def insert(self, key, value):
          
          if self._root is None:  # Empty tree case
              self._root = self._new_node(key, value)
              self._root.red = False  # make root black
              return
  
          head = Node()  # False tree root
          grand_parent = None
          grand_grand_parent = head
          parent = None  # parent
          direction = 0
          last = 0
  
          # Set up helpers
          grand_grand_parent.right = self._root
          node = grand_grand_parent.right
          # Search down the tree
          while True:
              if node is None:  # Insert new node at the bottom
                  node = self._new_node(key, value)
                  parent[direction] = node
              elif RBTree.is_red(node.left) and RBTree.is_red(node.right):  # Color flip
                  node.red = True
                  node.left.red = False
                  node.right.red = False
  
              # Fix red violation
              if RBTree.is_red(node) and RBTree.is_red(parent):
                  direction2 = 1 if grand_grand_parent.right is grand_parent else 0
                  if node is parent[last]:
                      grand_grand_parent[direction2] = RBTree.jsw_single(grand_parent, 1 - last)
                  else:
                      grand_grand_parent[direction2] = RBTree.jsw_double(grand_parent, 1 - last)
  
              # Stop if found
              if self._cmp(self._cmp_data, key, node.key) == 0:
                  node.value = value  # set new value for key
                  break
  
              last = direction
              direction = 0 if (self._cmp(self._cmp_data, key, node.key) < 0) else 1
              # Update helpers
              if grand_parent is not None:
                  grand_grand_parent = grand_parent
              grand_parent = parent
              parent = node
              node = node[direction]
  
          self._root = head.right  # Update root
          self._root.red = False
docs: T.insert(key, value) <==> T[key] = value, insert key, value into tree.