Joins two trees `t1` and `t1` with an intermediate key-value pair

    CommandLine:
        python -m utool.experimental.euler_tour_tree_avl avl_join

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> self = EulerTourTree(['a', 'b', 'c', 'b', 'd', 'b', 'a'])
        >>> other = EulerTourTree(['E', 'F', 'G', 'F', 'E'])
        >>> node = Node(value='Q')
        >>> root = avl_join(self.root, other.root, node)
        >>> new = EulerTourTree(root=root)
        >>> print('new = %r' % (new,))
        >>> ut.quit_if_noshow()
        >>> self.print_tree()
        >>> other.print_tree()
        >>> new.print_tree()

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> self = EulerTourTree(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'])
        >>> other = EulerTourTree(['X'])
        >>> node = Node(value='Q')
        >>> root = avl_join(self.root, other.root, node)
        >>> new = EulerTourTree(root=root)
        >>> print('new = %r' % (new,))
        >>> ut.quit_if_noshow()
        >>> ut.qtensure()
        >>> #self.show_nx(fnum=1)
        >>> #other.show_nx(fnum=2)
        >>> new.show_nx()

    Running Time:
        O(abs(r(t1) - r(t2)))
        O(abs(height(t1) - height(t2)))

def avl_join(t1, t2, node):
    """
    Joins two trees `t1` and `t1` with an intermediate key-value pair

    CommandLine:
        python -m utool.experimental.euler_tour_tree_avl avl_join

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> self = EulerTourTree(['a', 'b', 'c', 'b', 'd', 'b', 'a'])
        >>> other = EulerTourTree(['E', 'F', 'G', 'F', 'E'])
        >>> node = Node(value='Q')
        >>> root = avl_join(self.root, other.root, node)
        >>> new = EulerTourTree(root=root)
        >>> print('new = %r' % (new,))
        >>> ut.quit_if_noshow()
        >>> self.print_tree()
        >>> other.print_tree()
        >>> new.print_tree()

    Example:
        >>> # DISABLE_DOCTEST
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> self = EulerTourTree(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K'])
        >>> other = EulerTourTree(['X'])
        >>> node = Node(value='Q')
        >>> root = avl_join(self.root, other.root, node)
        >>> new = EulerTourTree(root=root)
        >>> print('new = %r' % (new,))
        >>> ut.quit_if_noshow()
        >>> ut.qtensure()
        >>> #self.show_nx(fnum=1)
        >>> #other.show_nx(fnum=2)
        >>> new.show_nx()

    Running Time:
        O(abs(r(t1) - r(t2)))
        O(abs(height(t1) - height(t2)))
    """
    if DEBUG_JOIN:
        print('-- JOIN node=%r' % (node,))

    if t1 is None and t2 is None:
        if DEBUG_JOIN:
            print('Join Case 1')
        top = node
    elif t1 is None:
        # FIXME keep track of count if possible
        if DEBUG_JOIN:
            print('Join Case 2')
        top = avl_insert_dir(t2, node, 0)
    elif t2 is None:
        if DEBUG_JOIN:
            print('Join Case 3')
        top = avl_insert_dir(t1, node, 1)
    else:
        h1 = height(t1)
        h2 = height(t2)
        if h1 > h2 + 1:
            if DEBUG_JOIN:
                print('Join Case 4')
            top = avl_join_dir_recursive(t1, t2, node, 1)
            if DEBUG_JOIN:
                ascii_tree(t1, 'top')
        elif h2 > h1 + 1:
            if DEBUG_JOIN:
                print('Join Case 5')
                ascii_tree(t1)
                ascii_tree(t2)

            top = avl_join_dir_recursive(t1, t2, node, 0)
            if DEBUG_JOIN:
                ascii_tree(top)
        else:
            if DEBUG_JOIN:
                print('Join Case 6')
            # Insert at the top of the tree
            top = avl_new_top(t1, t2, node, 0)
    return top