def insert(self, key, value):
if self._root is None:  <EOL><INDENT>self._root = self._new_node(key, value)<EOL>self._root.red = False  <EOL>return<EOL><DEDENT>head = Node()  <EOL>grand_parent = None<EOL>grand_grand_parent = head<EOL>parent = None  <EOL>direction = <NUM_LIT:0><EOL>last = <NUM_LIT:0><EOL>grand_grand_parent.right = self._root<EOL>node = grand_grand_parent.right<EOL>while True:<EOL><INDENT>if node is None:  <EOL><INDENT>node = self._new_node(key, value)<EOL>parent[direction] = node<EOL><DEDENT>elif RBTree.is_red(node.left) and RBTree.is_red(node.right):  <EOL><INDENT>node.red = True<EOL>node.left.red = False<EOL>node.right.red = False<EOL><DEDENT>if RBTree.is_red(node) and RBTree.is_red(parent):<EOL><INDENT>direction2 = <NUM_LIT:1> if grand_grand_parent.right is grand_parent else <NUM_LIT:0><EOL>if node is parent[last]:<EOL><INDENT>grand_grand_parent[direction2] = RBTree.jsw_single(grand_parent, <NUM_LIT:1> - last)<EOL><DEDENT>else:<EOL><INDENT>grand_grand_parent[direction2] = RBTree.jsw_double(grand_parent, <NUM_LIT:1> - last)<EOL><DEDENT><DEDENT>if self._cmp(self._cmp_data, key, node.key) == <NUM_LIT:0>:<EOL><INDENT>node.value = value  <EOL>break<EOL><DEDENT>last = direction<EOL>direction = <NUM_LIT:0> if (self._cmp(self._cmp_data, key, node.key) < <NUM_LIT:0>) else <NUM_LIT:1><EOL>if grand_parent is not None:<EOL><INDENT>grand_grand_parent = grand_parent<EOL><DEDENT>grand_parent = parent<EOL>parent = node<EOL>node = node[direction]<EOL><DEDENT>self._root = head.right  <EOL>self._root.red = False<EOL>
T.insert(key, value) <==> T[key] = value, insert key, value into tree.