Transformations between tree permutations and inversion tables

摘要

Associated with each permutation P = [x(1),x(2), … ,x(N)] of N (ordered) objects is its inversion table I(P) = {y(1),y(2), … ,y(N)}, a sequence of non-negative integers such that y(1) = 0 and, for i 1, y(i) is the number of terms in {x(1), x(2), … ,x(i-1)} which are greater than or follow the term x(i).

rn

A tree permutation is a permutation whose inversion table {y(1), … ,y(N)} has the property that y(i+1) - y(i) is less than 2 for i = 1, 2, … , N-1; such an inversion table is called a 2-inversion table. Tree permutations of {1, 2, … , N} are used to represent binary trees having N nodes. O(N) time algorithms are given for converting tree permutations into their associated 2-inversion tables and vice-versa.