def avl_insert_dir(root, new_node, direction=1):
    """
    Inserts a single node all the way to the left (direction=1) or right (direction=1)

    CommandLine:
        python -m utool.experimental.euler_tour_tree_avl avl_insert_dir --show
        python -m utool.experimental.euler_tour_tree_avl avl_insert_dir

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> import utool as ut
        >>> root = Node(value='A')
        >>> new_node = Node(value='B')
        >>> new_root = avl_insert_dir(root, new_node, direction=1)
        >>> new_root = avl_insert_dir(root, Node(value='Z'), direction=1)
        >>> EulerTourTree(root=new_root)._assert_nodes()
        >>> for v in ut.chr_range(5, base='C'):
        >>>     new_root = avl_insert_dir(new_root, Node(value=v), direction=1)
        >>>     self = EulerTourTree(root=new_root)
        >>>     self._assert_nodes()
        >>> new = EulerTourTree(root=new_root)
        >>> print(new)
        >>> ut.quit_if_noshow()
        >>> ut.qtensure()
        >>> new.show_nx(edge_labels=True)
        >>> ut.show_if_requested()
        >>> #ascii_tree(root)
        >>> #print(result)
    """
    if root is None:
        return new_node
    assert new_node.parent is None, str((new_node, new_node.parent))
    assert new_node.left is None
    assert new_node.right is None
    assert root.parent is None

    node_stack = []  # node stack
    # dir_stack = array('I')  # direction stack
    done = False
    top = 0
    # Move all the way to the right/left in tree1
    node = root
    # search for an empty link, save path
    while True:
        # Always move to the right
        # dir_stack.append(direction)
        node_stack.append(node)
        if node[direction] is None:
            break
        node = node[direction]
    extreme_node = node

    # Insert a new node at the bottom of the tree
    extreme_node.set_child(direction, new_node)
    new_root = root

    # Walk back up the search path
    # (which for joining orderless structures was always right)
    other_side = 1 - direction
    top = len(node_stack) - 1
    while (top >= 0) and not done:
        # direction = dir_stack[top]
        # other_side = 1 - direction
        top_node = node_stack[top]
        left_height = height(top_node[direction])
        right_height = height(top_node[other_side])

        # Terminate or rebalance as necessary
        if left_height - right_height == 0:
            done = True
        if left_height - right_height >= 2:
            a = top_node[direction][direction]
            b = top_node[direction][other_side]

            # Determine which rotation is required
            if height(a) >= height(b):
                node_stack[top] = avl_rotate_single(top_node, other_side)
            else:
                node_stack[top] = avl_rotate_double(top_node, other_side)

            # Fix parent
            if top != 0:
                # d_ = dir_stack[top - 1]
                d_ = direction
                node_stack[top - 1].set_child(d_, node_stack[top])
            else:
                new_root = node_stack[0]
                new_root.parent = None
            done = True

        # Update balance factors
        top_node = node_stack[top]
        left_height = height(top_node[direction])
        right_height = height(top_node[other_side])

        top_node.balance = max(left_height, right_height) + 1
        top -= 1
    assert new_root.parent is None
    return new_root
def avl_insert_dir ( root , new_node , direction = 1 ) : if root is None : return new_node assert new_node . parent is None , str ( ( new_node , new_node . parent ) ) assert new_node . left is None assert new_node . right is None assert root . parent is None node_stack = [ ] done = False top = 0 node = root while True : node_stack . append ( node ) if node [ direction ] is None : break node = node [ direction ] extreme_node = node extreme_node . set_child ( direction , new_node ) new_root = root other_side = 1 - direction top = len ( node_stack ) - 1 while ( top >= 0 ) and not done : top_node = node_stack [ top ] left_height = height ( top_node [ direction ] ) right_height = height ( top_node [ other_side ] ) if left_height - right_height == 0 : done = True if left_height - right_height >= 2 : a = top_node [ direction ] [ direction ] b = top_node [ direction ] [ other_side ] if height ( a ) >= height ( b ) : node_stack [ top ] = avl_rotate_single ( top_node , other_side ) else : node_stack [ top ] = avl_rotate_double ( top_node , other_side ) if top != 0 : d_ = direction node_stack [ top - 1 ] . set_child ( d_ , node_stack [ top ] ) else : new_root = node_stack [ 0 ] new_root . parent = None done = True top_node = node_stack [ top ] left_height = height ( top_node [ direction ] ) right_height = height ( top_node [ other_side ] ) top_node . balance = max ( left_height , right_height ) + 1 top -= 1 assert new_root . parent is None return new_root
Inserts a single node all the way to the left (direction=1) or right (direction=1)

    CommandLine:
        python -m utool.experimental.euler_tour_tree_avl avl_insert_dir --show
        python -m utool.experimental.euler_tour_tree_avl avl_insert_dir

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> import utool as ut
        >>> root = Node(value='A')
        >>> new_node = Node(value='B')
        >>> new_root = avl_insert_dir(root, new_node, direction=1)
        >>> new_root = avl_insert_dir(root, Node(value='Z'), direction=1)
        >>> EulerTourTree(root=new_root)._assert_nodes()
        >>> for v in ut.chr_range(5, base='C'):
        >>>     new_root = avl_insert_dir(new_root, Node(value=v), direction=1)
        >>>     self = EulerTourTree(root=new_root)
        >>>     self._assert_nodes()
        >>> new = EulerTourTree(root=new_root)
        >>> print(new)
        >>> ut.quit_if_noshow()
        >>> ut.qtensure()
        >>> new.show_nx(edge_labels=True)
        >>> ut.show_if_requested()
        >>> #ascii_tree(root)
        >>> #print(result)