def insert(self, key):
        new_node = RBNode(key)
        new_node.left = self.__EXT
        new_node.right = self.__EXT

        cur = self.__root
        if not cur:
            self.__root = new_node
            # 루트 노드는 BLACK
            self.__root.color = "BLACK"
            return

        while True:
            parent = cur
            if key < cur.key:
                cur = cur.left
                if cur == self.__EXT:
                    parent.left = new_node
                    # 노드의 parent 설정
                    new_node.parent = parent
                    break
            else:
                cur = cur.right
                if cur == self.__EXT:
                    parent.right = new_node
                    # 노드의 parent 설정
                    new_node.parent = parent
                    break
        # 노드 삽입 후 처리
        self.__insert_fix(new_node)