Notes:
            ● Pick any occurrence of the new root r.
            ● Split the tour into A and B, where B is the
            part of the tour before r.
            ● Delete the first node of A and append r.
            ● Concatenate B and A.

            To change the root of T from r to s:
                Let os denote any occurrence of s.
                Splice out the first part of the sequence ending with the
                occurrence before or,
                remove its first occurrence (or), and
                tack this on to the end of the sequence which now begins with os.
                Add a new occurrence os to the end.

        CommandLine:
            python -m utool.experimental.euler_tour_tree_avl reroot

        Example:
            >>> # DISABLE_DOCTEST
            >>> import networkx as nx
            >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
            >>> edges = [
            >>>     ('R', 'A'), ('R', 'B'),
            >>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
            >>>     ('B', 'F'), ('B', 'G'),
            >>> ]
            >>> edges = list(nx.balanced_tree(2, 2).edges())
            >>> tour = euler_tour(nx.Graph(edges))
            >>> self = EulerTourTree(tour)
            >>> print('old_tour = %r' % (self,))
            >>> nodes = list(self._traverse_nodes())
            >>> self.first_lookup = {node.value: node for node in nodes[::-1]}
            >>> self.last_lookup = {node.value: node for node in nodes}
            >>> new_root_val = list(self)[445 % (len(tour) - 1)]
            >>> new_root_val = 5
            >>> print('new_root_val = %r' % (new_root_val,))
            >>> first_node = self.first_lookup[new_root_val]
            >>> last_node = self.last_lookup[new_root_val]
            >>> self.reroot(first_node, last_node)
            >>> print('new_tour = %r' % (self,))
            >>> ut.quit_if_noshow()
            >>> ut.show_if_requested()

def reroot(self, first_node, last_node):
        """
        Notes:
            ● Pick any occurrence of the new root r.
            ● Split the tour into A and B, where B is the
            part of the tour before r.
            ● Delete the first node of A and append r.
            ● Concatenate B and A.

            To change the root of T from r to s:
                Let os denote any occurrence of s.
                Splice out the first part of the sequence ending with the
                occurrence before or,
                remove its first occurrence (or), and
                tack this on to the end of the sequence which now begins with os.
                Add a new occurrence os to the end.

        CommandLine:
            python -m utool.experimental.euler_tour_tree_avl reroot

        Example:
            >>> # DISABLE_DOCTEST
            >>> import networkx as nx
            >>> from utool.experimental.euler_tour_tree_avl import *  # NOQA
            >>> edges = [
            >>>     ('R', 'A'), ('R', 'B'),
            >>>     ('B', 'C'), ('C', 'D'), ('C', 'E'),
            >>>     ('B', 'F'), ('B', 'G'),
            >>> ]
            >>> edges = list(nx.balanced_tree(2, 2).edges())
            >>> tour = euler_tour(nx.Graph(edges))
            >>> self = EulerTourTree(tour)
            >>> print('old_tour = %r' % (self,))
            >>> nodes = list(self._traverse_nodes())
            >>> self.first_lookup = {node.value: node for node in nodes[::-1]}
            >>> self.last_lookup = {node.value: node for node in nodes}
            >>> new_root_val = list(self)[445 % (len(tour) - 1)]
            >>> new_root_val = 5
            >>> print('new_root_val = %r' % (new_root_val,))
            >>> first_node = self.first_lookup[new_root_val]
            >>> last_node = self.last_lookup[new_root_val]
            >>> self.reroot(first_node, last_node)
            >>> print('new_tour = %r' % (self,))
            >>> ut.quit_if_noshow()
            >>> ut.show_if_requested()
        """
        min_elem = self.min_elem()
        if min_elem  == first_node.value:
            print('Already rooted there')
            return
        # tour = list(self)
        # print('tour     = %r' % (tour,))
        # B is the part before R
        # A is the part after R (with first element removed)
        B, A, first_node = avl_split(self.root, first_node)
        print('Splice out first part of sequence ending before os')
        print('B = %r' % ([] if B is None else list(B),))
        print('Remove its first occurrence or')
        B, old_root = (B, B) if B is None else avl_split_first(B)
        print('B = %r' % ([] if B is None else list(B),))
        print('The rest of the sequence now begins with os')
        A = avl_insert_dir(A, first_node, 0)
        print('A = %r' % (list(A),))
        print('Tack the first part onto the end')
        EulerTourTree(root=A)._assert_nodes('A')
        EulerTourTree(root=B)._assert_nodes('B')
        C = avl_join2(A, B)
        EulerTourTree(root=C)._assert_nodes('C')
        print('C = %r' % (list(C),))
        print('Add a new occurrence os to the end')
        new_last = Node(value=last_node.value)
        C = avl_insert_dir(C, new_last, 1)
        print('C = %r' % (list(C),))

        EulerTourTree(root=B)._assert_nodes()
        EulerTourTree(root=A)._assert_nodes()
        # EulerTourTree(root=first_node)._assert_nodes()

        # EulerTourTree(root=B).print_tree()
        # EulerTourTree(root=A).print_tree()
        # EulerTourTree(root=first_node).print_tree()

        # B = avl_insert_dir(B, new_last, 1)
        # print('B = %r' % ([] if B is None else list(B),))
        # print('A = %r' % (list(A),))

        # EulerTourTree(root=A).print_tree()

        # old_tour_parts = [S1, R, S2]
        # old_tour = ut.flatten([list(p) for p in old_tour_parts if p])
        # print('old_tour = %r' % (old_tour,))
        # assert tour == old_tour
        # new_tour_parts = [A, B]
        # new_tour = ut.flatten([list(p) for p in new_tour_parts if p])
        print('new_tour = %r' % (list(C)))
        self.root = C

        # TODO: fix lookups
        self.last_lookup[new_last.value] = new_last

        nodes = list(self._traverse_nodes())
        new_first_lookup = {node.value: node for node in nodes[::-1]}
        new_last_lookup = {node.value: node for node in nodes[::1]}

        for key in new_last_lookup.keys():
            old_last = self.last_lookup[key]
            new_last = new_last_lookup[key]
            if old_last is not new_last:
                print('key=%r needs LAST_DICT update' % (key,))

        for key in new_last_lookup.keys():
            old_first = self.first_lookup[key]
            new_first = new_first_lookup[key]
            if old_first is not new_first:
                print('key=%r needs FIRST_DICT update' % (key,))