O(log(n))

    Args:
        root (Node): tree root
        node (Node): node to split at

    Returns:
        puple: (tl, tr, node)
            tl contains all keys in the tree less than node
            tr contains all keys in the tree greater than node
            node is the node we split out

    CommandLine:
        python -m utool.experimental.euler_tour_tree_avl avl_split

    Example:
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> self = EulerTourTree(ut.chr_range(10))
        >>> self.print_tree()
        >>> node = self.get_node(5)
        >>> part1, part2, bnode = avl_split(self.root, node)
        >>> ascii_tree(part1)
        >>> ascii_tree(part2)
        >>> ascii_tree(bnode)

    Example:
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> test_avl_split(verbose=2)

def avl_split(root, node):
    """
    O(log(n))

    Args:
        root (Node): tree root
        node (Node): node to split at

    Returns:
        puple: (tl, tr, node)
            tl contains all keys in the tree less than node
            tr contains all keys in the tree greater than node
            node is the node we split out

    CommandLine:
        python -m utool.experimental.euler_tour_tree_avl avl_split

    Example:
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> self = EulerTourTree(ut.chr_range(10))
        >>> self.print_tree()
        >>> node = self.get_node(5)
        >>> part1, part2, bnode = avl_split(self.root, node)
        >>> ascii_tree(part1)
        >>> ascii_tree(part2)
        >>> ascii_tree(bnode)

    Example:
        >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
        >>> test_avl_split(verbose=2)
    """
    DEBUG_SPLIT = 0

    # Get the backtrace to the root
    rpath = backtrace_root(node)
    if len(rpath) > 0:
        assert rpath[-1][0] is root
    if DEBUG_SPLIT:
        print('======== SPLIT (PY)')
        print('rpath = %s' % (rpath,))
        print('node = %s' % (node,))

    # We start by knowing where the node is
    # This is the base case of the recursive function
    bnode, part1, part2 = avl_release_kids(node)
    assert bnode is node
    if DEBUG_SPLIT:
        print('bnode = %s' % (bnode,))
        print(' * part1 = %s' % (part1,))
        print(' * part2 = %s' % (part2,))
    avl_release_parent(bnode)

    # We have split out the node we care about.
    # Now, we need to recombine the tree in an ordered fashion

    # Retrace the the stack that would have been
    # generated by the old recursive key-based split
    for count, (node, direction) in enumerate(rpath):
        if DEBUG_SPLIT:
            print('+--- Iter {}'.format(count))
            print(' * node = %s' % (node,))
            print(' * direction = %r' % (direction,))
        node, left, right = avl_release_kids(node)
        avl_release_parent(node)
        if DEBUG_SPLIT:
            print(' * left = %s' % (left,))
            print(' * right = %s' % (right,))
        # At `node` we would have decided to go `direction`
        if direction == 0:
            # left is case 1
            if DEBUG_SPLIT:
                print(' * Case 1')
                print(' * Join %s + %s + %s' % (part2, node, right))
            new_right = avl_join(part2, right, node)
            part1 = part1
            part2 = new_right
        elif direction == 1:
            # right is case 1
            if DEBUG_SPLIT:
                print(' * Case 2')
                print(' * Join %s + %s + %s' % (left, node, part1))
            new_left = avl_join(left, part1, node)
            part1 = new_left
            part2 = part2
        else:
            raise AssertionError('impossible state')
        if DEBUG_SPLIT:
            print('     * part1 = %s' % (part1,))
            print('     * part2 = %s' % (part2,))
            print('+--- End Iter {}'.format(count))
    if DEBUG_SPLIT:
        print('RETURN')
        print(' * part1 = %s' % (part1,))
        print(' * part2 = %s' % (part2,))
        print(' * bnode = %s' % (bnode,))
    return (part1, part2, bnode)