Transformations between tree permutations and inversion tables

ABSTRACT

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). 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.

REFERENCES

• 1: Gary D. Knott, A numbering system for binary trees, Communications of the ACM, v.20 n.2, p.113-115, Feb. 1977 [doi>10.1145/359423.359434]
• 2: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 3: E. Mäkinen, A survey on binary tree codings, The Computer Journal, v.34 n.5, p.438-443, Oct. 1991 [doi>10.1093/comjnl/34.5.438]
• 4: Martin, Harold W., Kiltinen, john O. and McNeill, Robert W., The representation and enumeration of ordered K-ary trees, Proceedings of ICCI'89, Toronto, North Holland, (1989).
• 5: H. W. Martin , B. J. Orr, A random binary tree generator, Proceedings of the 17th conference on ACM Annual Computer Science Conference, p.33-38, February 21-23, 1989, Louisville, Kentucky [doi>10.1145/75427.75429]
• 6: M~rtin, Harold W., Transformations between permutations and inversion tables, submitted for publication.
• 7: Martin, Harold W., Climbing ordered trees, submitted for publication.
• 8: Harry F. Smith, Data structures: form and function, Harcourt Brace & Co., Orlando, FL, 1987
• 9: D Stanton , D White, Constructive combinatorics, Springer-Verlag New York, Inc., New York, NY, 1986

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Permutations and combinations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

General Terms:
Algorithms