An Algorithm of Binary Tree Encoding with Minimum Redundancy

This paper proposes an algorithm of binary trees encoding and decoding with minimum redundancy, i. e. with bit sequences of minimal possible length. We performed recursive computation of trees indices using Catalan numbers. Moreover, we give the algorithm complexity estimations. The developed method allows us to construct a binary tree on the basis of unique index of its structure and number of nodes without explicitly enumerating all possible tree structures. The minimal length of the bit sequence makes it possible to optimize trees with the fixed nodes number using genetic algorithms.

References

[1] Korvyakov V.P. Method of neuro-fuzzy estimation of graphical user interface usability. Vestn. Mosk. Gos. Tekh. Univ. im. N.E. Baumana, Priborostr. [Herald of the Bauman Moscow State Tech. Univ., Instrum. Eng.], 2016, no. 5, pp. 61-74 (in Russ.). DOI: 10.18698/0236-3933-2016-5-61-74

[2] Knuth D.E. The art of computer programming. Vol. 1. Fundamental Algorithms. Reading, Massachusetts: Addison-Wesley, 1997. 650 p.

[3] Davis T. Catalan numbers. geometer.org: website. Available at: http://www.geometer.org/mathcircles/catalan.pdf (accessed 17.08.2016).

[4] Bege A., Kasa Z. Coding objects related to Catalan numbers. Studia Universitatis Babes-Bolyai. Informatica, 2001, vol. 46, no. 1, pp. 31-40. Available at: http://www.cs.ubbcluj.ro/~studia-i/2001-1/3-Kasa.pdf

[5] Flajolet P., Sedgewick R. Analytic combinatorics. Cambridge University Press, 2009. 826 p.

[6] Farzan A., Munro J.I. A uniform paradigm to succinctly encode various families of trees. Algorithmica, 2014, vol. 68, no. 1, pp. 16-40. DOI: 10.1007/s00453-012-9664-0 Available at: http://link.springer.com/article/10.1007%2Fs00453-012-9664-0

[7] Davoodi P., Raman R., Satti S.R. On succinct representations of binary trees. arXiv.org: Cornell University Library. Available at: http://arxiv.org/abs/1410.4963 (accessed 29.09.2016).

[8] Makinen E. A survey on binary tree coding. The Computer Journal, 1991, vol. 34, no. 5, pp. 438-443. DOI: 10.1093/comjnl/34.5.438 Available at: https://academic.oup.com/comjnl/article-abstract/34/5/438/553944/A-Survey-on-Binary-Tree-Codings?redirectedFrom=fulltext

[9] Cormen T.H., Leiserson Ch.E., Rivest R.L., Stein C. Introduction to algorithms. MIT Press, 2009. 235 p.

[10] Catalantree - Binary trees decoding/encoding with Catalan numbers based algorithm. GitHub: website. Available at: https://github.com/HapKoM/catalantree (accessed 24.08.2016).

[11] Gansner E., Koutsofios E., North E. Drawing graphs with dot. Graphviz: website. Available at: http://www.graphviz.org/Documentation/dotguide.pdf (accessed 24.08.2016).

[12] Knuth D.E. The art of computer programming. Vol. 4. Fascicle 4: Generating all trees-history of combinatorial generation. Upper Saddle River, New Jersey, Addison-Wesley, 2011. 883 p.